Les machines de Turing expliquées

En 1936, avant que les ordinateurs électroniques n'existent, le mathématicien Alan Turing, âgé de 24 ans, s'est demandé ce que signifie, pour un calcul, être mécanique. Sa réponse fut une machine imaginaire si simple qu'elle pourrait difficilement faire moins : elle lit et écrit des symboles sur un ruban, une case à la fois, selon une table de règles fixe. Cette machine s'est révélée définir le calcul lui-même, et elle a montré que certaines questions ne pourront jamais recevoir de réponse d'aucun ordinateur.

Un ruban de cases contenant des 1 et des cases vides, avec une tête de lecture-écriture au-dessus d'une case, étiquetée avec son état
Un ruban de cases contenant des 1 et des cases vides, avec une tête de lecture-écriture au-dessus d'une case, étiquetée avec son état

La question de Turing

En 1928, David Hilbert a demandé s'il existe une procédure mécanique qui décide, pour tout énoncé mathématique, s'il peut être démontré : c'est l'Entscheidungsproblem. Pour y répondre, il fallait dire exactement ce qu'est une procédure mécanique. Dans son article de 1936, On Computable Numbers, Turing a imaginé un employé travaillant avec un crayon et du papier, et a réduit ce travail à ses plus petites étapes : regarder un symbole, le modifier, passer à un symbole voisin et se souvenir un peu de ce que l'on était en train de faire. Le résultat fut la machine de Turing.

Une machine Bombe (à gauche) et un portrait d’Alan Turing (à droite)
Une machine Bombe (à gauche) et un portrait d’Alan Turing (à droite)

La machine

Une machine de Turing possède un ruban divisé en cases, infini dans les deux sens, chaque case contenant un symbole, généralement le symbole vide. Une tête est posée sur une case et la machine se trouve dans l'un d'un nombre fini d'états. Une table de règles donne, pour chaque état et chaque symbole que la tête peut lire, le symbole à écrire, la direction du déplacement et l'état suivant. La machine applique une règle par étape. Lorsqu'elle entre dans un état d'arrêt, elle s'arrête, et ce qui reste sur le ruban est sa réponse.

Des programmes en tables de règles

Chaque table de règles est un programme. Pour ajouter 1 à un nombre binaire, la machine se rend à l'extrémité droite du nombre, puis se déplace vers la gauche en changeant les 1 en 0 jusqu'à trouver un 0 ou une case vide, qu'elle change en 1. Pour vérifier si un mot est un palindrome, elle efface le premier symbole, le mémorise dans son état, court jusqu'à l'autre extrémité et vérifie que le dernier symbole correspond, puis recommence. Les longs programmes, comme ceux qui multiplient ou trient, sont construits à partir des mêmes quelques types de règles.

La machine universelle

L'idée la plus importante de Turing fut que la table de règles elle-même peut être écrite sur le ruban. Une machine de Turing universelle lit la description de n'importe quelle autre machine et son entrée, puis l'imite étape par étape. Une seule machine fixe peut donc exécuter tous les programmes : c'est le principe de tout ordinateur à programme enregistré, où le logiciel n'est que des données en mémoire. Tout système capable d'imiter une machine de Turing universelle est dit Turing-complet, y compris tous les langages de programmation, le jeu de la vie de Conway et l'automate cellulaire Rule 110.

La thèse de Church-Turing

La même année, Alonzo Church a décrit le calcul avec son lambda-calcul, et les deux définitions se sont révélées calculer exactement les mêmes fonctions. Il en est allé de même pour tous les modèles ultérieurs, des machines à registres aux processeurs modernes. La thèse de Church-Turing affirme que tout ce qui peut être calculé par une procédure pas à pas peut être calculé par une machine de Turing. Elle ne peut pas être démontrée, car « procédure pas à pas » est une notion informelle, mais aucun contre-exemple n'a jamais été trouvé.

Le problème de l'arrêt

Turing a ensuite montré que certaines questions n'ont pas de réponse mécanique. Supposons qu'une machine puisse décider, pour tout programme et toute entrée, si ce programme finit par s'arrêter. Construisons un nouveau programme qui interroge ce décideur à son propre sujet puis fait le contraire : si on lui dit qu'il s'arrête, il boucle indéfiniment, et si on lui dit qu'il boucle, il s'arrête. Les deux réponses sont fausses, donc le décideur ne peut pas exister. Le problème de l'arrêt est indécidable, et avec lui l'Entscheidungsproblem : aucun algorithme ne peut trancher toutes les questions mathématiques.

Castors affairés

En 1962, Tibor Radó a transformé le problème de l'arrêt en jeu : parmi toutes les machines à n états et aux symboles 0 et 1 qui s'arrêtent lorsqu'elles démarrent sur un ruban vide, laquelle écrit le plus de 1, et combien d'étapes une telle machine peut-elle effectuer ? Ces nombres, les valeurs du castor affairé, croissent plus vite que toute fonction calculable, car un moyen de les calculer résoudrait le problème de l'arrêt. Les valeurs connues sont 6, 21 et 107 étapes pour deux, trois et quatre états ; pour cinq états, la machine championne de Heiner Marxen et Jürgen Buntrock effectue 47 176 870 étapes, une valeur démontrée en 2024 par la collaboration en ligne bbchallenge grâce à une preuve vérifiée par ordinateur. Pour six états, on connaît des machines qui tournent pendant plus d'étapes qu'on ne peut en écrire en notation ordinaire.

À vous de jouer

Ouvrez le simulateur de machine de Turing pour exécuter huit programmes prêts à l'emploi ou écrire les vôtres. Suivez la tête étape par étape et voyez quelle règle se déclenche, observez le compteur qui ne s'arrête jamais, vérifiez des palindromes et lancez les castors affairés : les 107 étapes de la championne à quatre états tiennent dans le diagramme, et les 47 millions d'étapes de la championne à cinq états prennent quelques secondes à la vitesse Très rapide.

Questions fréquemment posées

La machine de Turing a-t-elle déjà été construite ?

Pas telle que Turing l'a décrite, puisque son ruban est infini, mais l'idée a vite été suivie de véritables ordinateurs à programme enregistré, que Turing lui-même a contribué à concevoir après la Seconde Guerre mondiale. Des amateurs ont depuis construit des modèles fonctionnels en bois, en LEGO et même dans le jeu de la vie, tous avec un ruban fini, ce qui suffit pour tout calcul qui se termine.

Quelle est la différence entre les nombres d'étapes 14 et 21 pour trois états ?

Il existe deux questions du castor affairé : le plus grand nombre de 1 écrits et le plus grand nombre d'étapes effectuées. Pour trois états, la machine du simulateur écrit le maximum de six 1 en 14 étapes, tandis qu'une autre machine à trois états effectue le maximum de 21 étapes mais ne laisse que cinq 1. Pour deux, quatre et cinq états, une même machine gagne sur les deux plans.

Turing-complet signifie-t-il puissant ?

Cela signifie capable de calculer tout ce qui est calculable, avec assez de temps et de mémoire, ce qui ne dit rien de la vitesse. Une machine de Turing a besoin de nombreuses étapes pour une arithmétique simple, et certains systèmes sont Turing-complets presque par accident, comme des jeux de cartes, des formules de tableur et la redstone de Minecraft.

Pourquoi un ordinateur ne peut-il pas simplement exécuter un programme pour voir s'il s'arrête ?

L'exécuter montre qu'un programme s'arrête, s'il s'arrête, mais s'il ne s'est pas encore arrêté, on ne peut pas savoir s'il ne s'arrêtera jamais ou s'il lui faut simplement plus de temps. La preuve de Turing montre qu'aucune méthode plus astucieuse ne fonctionne pour tous les programmes, même si, pour beaucoup de programmes particuliers, la question peut être résolue.

Prêt à l'essayer ?

Ouvrez PictorX dans votre navigateur – aucune installation, aucune carte de crédit requise pour démarrer.

Ouvrir le simulateur de machine de Turing