Problème de l’arrêt
Texte dit sur scène après le bug d’Alan sur le paradoxe du menteur
Le texte
L’idée était de tester Alan sur des contradiction et des paradoxe. Dès qu’un paradoxe le faisait planté, on lui apprenait à le reconnaitre et la prochaine fois qu’il y serait confronté il faudrait qu’il s’interdise d’y réfléchir. C’était un travail fastidieu car impossible à automatiser. Impossible au sens propre. Alan Turing lui même a démontré en 1936 qu’il ne peut pas exister de programme capable de dire si un autre programme va rentre dans une boucle infini ou non. C’est ce qu’on appelle le problème de l’arrêt. Fabien adorait la démonstration de Turing (très courte et élégante). Il s’entrainait pendant des heures à la faire le plus rapidement possible.
Ces quelques lignes prouve qu’il y a une limite que les machines ne peuvent pas dépasser.
La démonstration du Théorème de l’arrêt
retour à la liste des textes à lire, textes théoriques, petites histoires