Comment fonctionne une machine de Turing ?
Voir le site interstice
Site INRIA-interstices-machine de Turing
Un simulateur de machine de Turing (attention c'est le ruban qui se déplace ):
Source : INRIA-interstices-machine de Turing
Explications sur le simulateur
Vidéo 1
Vidéo 2
Source :
Un prototype programmable pour concrétiser la machine de Turing
Différents tableaux de transition
Pour les curieux : la notion en logique de paradoxe.
Intéressez vous à la proposition suivante :"je suis un menteur".
Si je dis que je suis un menteur alors ce que je dis est faux, donc je ne mens pas. Mais j'ai donc menti en disant que je suis un menteur.
Maintenant, considérons que ce que je dis est faux. On peut donc dire que je ne mens pas. Si je ne mens pas alors l'affirmation "je suis un menteur" est vraie. Donc je mens, ce qui contredit mon hypothèse de départ.
Ce paradoxe du menteur serait attribué à Epiménide le Crétois (VIIème siècle av J-C).
On parle dans ce cas d'autoréférence. Une phrase ou une formule fait référence à elle même. Cette notion a beaucoup d'applications en mathématiques, philosophie et en programmation. Un énoncé contenant une autoréférence est parfois paradoxal.
En 1931, Kurt Gödel, pour démontrer son théorème d'incomplétude, utilise un énoncé inspiré de ce paradoxe.