Sujet : Les mots incompressibles et le théorème d'incomplétude de Gödel.
Contact: Andrei Romashchenko, Alexander Shen

G.Chaitin a remarqué que l'idée de compression algorithmique de données 
peut être utilisée pour donner une preuve alternative du théorème 
d'incomplétude de Gödel. En effet, presque tout les mots binaires sont 
incompressibles : soit X est un mot de taille N, alors il n'existe pas de 
programme beaucoup plus court que N qui puisse générer X. D'un autre côté, 
bien que les propositions formelles qui expriment les assertions  
"le mot X est incompressible" soient typiquement justes, elles sont presque 
toutes non-prouvables. 

Dans le cadre de ce stage nous proposons d'estimer la taille de mot X 
pour lequel la proposition "X est incompressible" est non-prouvables, 
pour quelques systèmes formels spécifiques. Nous proposons également 
d'étudier la connection entre cette variation du théorème d'incomplétude 
et le théorème classique de récursion de Kleene.