Une machine de Turing est un modèle théorique d’ordinateur, une sorte de machine imaginaire réduite à l’essentiel, conçue pour capturer ce qu’est fondamentalement un calcul. On se la représente comme un ruban de papier infiniment long, divisé en cases pouvant chacune contenir un symbole, que parcourt une tête de lecture capable de lire le symbole sous elle, de l’effacer ou d’en écrire un autre, puis de se déplacer d’une case vers la gauche ou vers la droite. La machine suit un jeu de règles très simples qui, selon le symbole lu et son état interne du moment, lui dictent quoi écrire, dans quel sens bouger et dans quel état passer ensuite. Malgré cette extrême simplicité, un tel dispositif suffit à effectuer n’importe quel calcul qu’un ordinateur moderne peut réaliser.
Ce modèle a été inventé par Alan Turing en 1936, non pas pour construire une machine réelle, mais pour donner une définition rigoureuse de l’idée intuitive de calcul mécanique. Turing cherchait à répondre à une question posée par les logiciens de son époque sur les limites du raisonnement automatique, et il eut l’idée d’imiter par abstraction ce que fait un être humain qui calcule à la main, en suivant pas à pas des instructions notées sur du papier. Sa machine, dépouillée à l’extrême, s’est révélée d’une puissance étonnante: toute procédure que l’on peut décrire mécaniquement peut être exécutée par une machine de Turing, ce qui en a fait la référence pour définir ce qui est calculable.
L’importance de cette invention est difficile à surestimer. La machine de Turing est devenue le socle théorique de toute l’informatique, le modèle auquel on rapporte la puissance de tout langage de programmation ou de tout ordinateur, dont on dit qu’ils sont Turing-complets lorsqu’ils savent faire tout ce qu’elle sait faire. Elle sert d’étalon pour distinguer le calculable de l’incalculable, et c’est en raisonnant sur elle qu’on démontre l’indécidabilité de nombreux problèmes. Turing lui-même prolongea cette réflexion en imaginant une machine universelle, capable de simuler n’importe quelle autre en lisant sa description, préfigurant ainsi l’idée d’ordinateur programmable qui allait révolutionner le monde quelques années plus tard.
Laisser un commentaire