Chaitin cherche à déterminer le Kième bit d' un programme à N bits. Pouvez vous m' expliquer ?

Question

http://www.cs.auckland.ac.nz/CDMTCS/chaitin/paris.html

Answer 1

Il s'agit pour lui d'appliquer son équation - dérivée des travaux de Hilbert et de Gödel, ainsi que de Turing, et s'appuyant sur un théorème d'Edouard Lucas, à la démontration de l'indécidabilité de l'arrêt d'un programme choisi au hasard en utilisant une équation diophantienne (ne contenant que des nombres entiers entre 0 et 1) de 17 000 variables qu'il a générée aux fins de cette démonstration.

Plus généralement, son propos est d'introduire en mathématiques pures ce que les physiciens quanticiens ont introduit en physique élémentaire, à savoir le rôle fondamental du hasard et de l'imprévisibilité.

L'article sur Chaïtin est très intéressant. Merci de le joindre en communication.

Answer 2

attends, je finis de lire, il est bien l'article, mais long.
c'est compliqué. Chaitlin ne cherche pas a calculer le Kieme bit d'un programme a N bit, mais le Nieme bit d'un nombre (omega).
Ce nombre omega doit etre approché a une certaine precision, et K est un parametre decrivant cette precision.
Le probleme, c'est qu'etant donné le bit N qu'on cherche, il n'est pas possible de savoir quelle approximation K il faut avoir pour pouvoir repondre a la question.

Comme il y a moyen de transformer ce probleme en la question :
"telle equation diophantienne admet elle un nombre fini ou infini de solution ? ", cela permet d'affirmer qu'on ne peut pas creer de programme de calcul permettant de repondre a la question quelque soit l'equation diophantienne consideree. (a chaque bit de omega correspondra une nouvelle equation diophantienne et le programme de calcul devant etre de taille toujours plus grand pour calculer ce bit, il devra egalement l'etre pour repondre a la question sur le nombre de solution de l'equation)

j'espere avoir bien compris.