Vous voulez savoir si un algorithme peut résoudre un problème, ou pourquoi certains programmes ne terminent jamais. La machine de Turing d’Alan Turing sert à formaliser ce genre de question, à condition de ne pas la confondre avec un ordinateur réel.
Une machine abstraite pour décrire les calculs et leurs limites
- Ruban : une mémoire divisée en cases contenant des symboles.
- Règles : à chaque étape, la machine lit, écrit, change d’état et déplace sa tête.
- Calculabilité : le modèle permet de définir quels problèmes peuvent être résolus par un algorithme.
- Limite : un programme peut ne jamais s’arrêter, et aucun algorithme général ne détecte tous ces cas.
Un ruban, une tête et des règles suffisent à décrire un calcul
Imaginez une bande de papier découpée en cases, avec une tête qui lit une case à la fois. À chaque étape, une instruction lui indique quel symbole écrire, dans quel état passer et vers où se déplacer. Le modèle est volontairement dépouillé : il ne cherche pas à reproduire les composants d’un ordinateur, mais la logique d’un calcul mécanique.
Une machine comprend donc un ensemble d’états, un alphabet de symboles et une table de transitions. Une transition peut se lire ainsi : « si l’état courant est q et le symbole lu est 1, écris 1, déplace-toi à droite et reste dans l’état q ». Une fois la table fixée, le comportement est déterminé par l’entrée et l’état initial.
Un exemple unaire montre chaque étape sans détour
Pour incrémenter un nombre écrit en unaire, chaque « 1 » représente une unité : l’entrée 111 signifie trois. La machine avance sur les cases contenant 1, puis, lorsqu’elle rencontre une case vide, elle y écrit 1 et s’arrête. Le résultat 1111 représente quatre.
Cette petite procédure contient déjà les ingrédients d’un algorithme : une entrée, une règle répétée, une condition d’arrêt et une sortie. La case vide joue ici le rôle de repère : sans elle, la machine ne saurait pas où se termine la suite de 1.
| Situation | Ce que fait la machine | Résultat |
|---|---|---|
| Elle lit 1 | Elle conserve 1 et avance à droite | La recherche de la fin continue |
| Elle lit une case vide | Elle écrit 1 et passe à l’état d’arrêt | Un symbole est ajouté |
La notation exacte des états varie selon les cours, mais la procédure reste la même. Je trouve cet exemple plus parlant qu’une définition formelle seule, parce qu’on voit précisément où l’algorithme s’arrête.
La machine universelle explique le lien entre programme et données
Dans son article On Computable Numbers, with an Application to the Entscheidungsproblem, Turing décrit aussi une machine universelle. Son principe : une seule machine peut lire la description d’une autre machine et simuler son fonctionnement sur une entrée donnée.
C’est l’idée d’un programme traité comme une donnée. Un interpréteur moderne en offre une analogie utile : il lit des instructions encodées et en reproduit l’exécution. L’analogie ne signifie pas que l’article de Turing décrit les ordinateurs actuels dans leurs détails matériels ; il formalise plutôt une idée générale du calcul programmable.
On parle de machine de Turing « universelle » lorsqu’elle peut simuler toute machine de Turing convenablement encodée. Cette universalité concerne les calculs réalisables, pas leur vitesse : une simulation peut demander davantage d’étapes ou de mémoire que le calcul simulé.
Un programme qui boucle révèle une limite de la calculabilité
Pour un programme donné, la question « va-t-il s’arrêter sur cette entrée ? » semble simple. Pourtant, il n’existe pas de procédure générale qui réponde correctement à cette question pour tous les programmes et toutes les entrées. C’est le problème de l’arrêt, résultat central de la théorie de la calculabilité.
La nuance compte : on peut analyser beaucoup de programmes particuliers, et certains outils détectent des boucles dans des cas précis. La limite porte sur un détecteur universel infaillible. La Stanford Encyclopedia of Philosophy expose le modèle et ses frontières ; elle aide à distinguer un problème difficile à résoudre d’un problème pour lequel aucune méthode générale ne peut toujours fournir la réponse.
| Situation | Cause ou conséquence | Que faire |
|---|---|---|
| Le programme s’arrête sur l’entrée testée | Une exécution finie est observée, sans preuve sur toutes les entrées | Tester d’autres entrées ou démontrer une propriété plus générale |
| Le programme continue sans fin | Il peut boucler ou chercher une condition qui ne survient jamais | Examiner les transitions et les conditions d’arrêt |
| Vous cherchez un outil qui prédit tous les arrêts | Le problème de l’arrêt exclut un décideur général parfait | Définir un domaine restreint ou accepter une analyse incomplète |
La thèse de Church-Turing n’est pas une preuve que tout est calculable
Une confusion fréquente consiste à dire que Turing a prouvé qu’un ordinateur peut calculer n’importe quoi. Le résultat est bien plus circonscrit : le modèle formalise la notion de procédure effective et montre aussi des limites, comme l’indécidabilité du problème de l’arrêt. La thèse de Church-Turing affirme que les fonctions calculables par une méthode effective correspondent à celles calculables par une machine de Turing ; c’est une thèse sur la formalisation du calcul, pas un théorème disant que tout problème a une solution algorithmique.
La distinction est utile en programmation. Si un problème paraît insoluble, il faut déterminer s’il est simplement trop coûteux en temps ou en mémoire, ou s’il est indécidable au sens théorique. Dans le premier cas, une meilleure méthode peut suffire ; dans le second, aucune optimisation ne donnera un algorithme général exact.
La machine de Turing sert de boussole, pas de plan d’ordinateur
Pour comprendre un algorithme, imaginez sa mémoire comme un ruban, ses instructions comme une table de transitions et son exécution comme une suite d’étapes. Ce schéma permet de poser une question plus profonde que « mon code fonctionne-t-il ? » : le problème peut-il être résolu par une procédure finie dans tous les cas visés ?
La réponse n’indique pas combien de secondes prendra un programme réel, ni quelle quantité de mémoire il consommera. Elle trace la frontière de ce qui est calculable, tandis que l’analyse de complexité étudie le coût des solutions qui existent.