Machine de Turing - comprendre le calcul et ses limites

Une machine de Turing d'Alan, un appareil de chiffrement historique, exposé dans un musée.

Publié le

7 nov. 2026

Table des matières

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.

SituationCe que fait la machineRésultat
Elle lit 1Elle conserve 1 et avance à droiteLa recherche de la fin continue
Elle lit une case videElle écrit 1 et passe à l’état d’arrêtUn 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.

SituationCause ou conséquenceQue faire
Le programme s’arrête sur l’entrée testéeUne exécution finie est observée, sans preuve sur toutes les entréesTester d’autres entrées ou démontrer une propriété plus générale
Le programme continue sans finIl peut boucler ou chercher une condition qui ne survient jamaisExaminer les transitions et les conditions d’arrêt
Vous cherchez un outil qui prédit tous les arrêtsLe problème de l’arrêt exclut un décideur général parfaitDé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.

Questions fréquentes

Elle avance sur les cases contenant 1 en les conservant, jusqu’à rencontrer une case vide. Elle y écrit alors un nouveau 1 et passe à l’état d’arrêt : l’entrée 111 devient ainsi 1111.

La machine utilise un ruban divisé en cases, un alphabet de symboles, un ensemble d’états et une table de transitions. Pour chaque situation, une règle indique le symbole à écrire, le nouvel état et le déplacement de la tête, vers la gauche ou la droite.

Une machine universelle peut lire la description correctement encodée d’une autre machine et simuler son fonctionnement sur une entrée. Elle formalise ainsi l’idée d’un programme traité comme une donnée, même si la simulation peut demander davantage d’étapes ou de mémoire.

Le problème de l’arrêt montre qu’il n’existe aucun procédé général capable de déterminer correctement, pour tous les programmes et toutes les entrées, si l’exécution se terminera. Des analyses restent possibles sur des cas particuliers, mais elles ne constituent pas un détecteur universel infaillible.

Évaluer l'article

Note: 5.00 Nombre de votes: 2

Tags:

machine de turing calculabilité problème de l’arrêt indécidabilité thèse de church-turing

Partager l'article

Écrire un commentaire