La machine de Turing est l’un des concepts les plus importants de l’informatique théorique. Pourtant, elle ne ressemble presque pas à un ordinateur moderne : pas d’écran, pas de processeur, pas de clavier et, dans sa forme théorique, pas même de limite réelle à sa mémoire.
Imaginée par Alan Turing en 1936, elle répond à une question beaucoup plus fondamentale : qu’est-ce qu’un calcul ?
Pour y répondre, Turing imagine une machine volontairement minimale, capable de lire et d’écrire des symboles sur un ruban en suivant une série de règles précises.
Malgré cette simplicité extrême, le modèle est suffisamment puissant pour représenter tout calcul pouvant être effectué par un algorithme, selon la conception classique de la calculabilité.
La machine de Turing ne constitue donc pas seulement une curiosité historique. Elle permet de comprendre ce qu’est un algorithme, ce qu’un ordinateur peut théoriquement calculer et, surtout, pourquoi certains problèmes resteront impossibles à résoudre automatiquement, quelle que soit la puissance des machines futures.
Pourquoi fallait-il définir le calcul ?
Au début du XXe siècle, les mathématiciens cherchent à formaliser les fondements de leur discipline.
Une question importante concerne l’existence de procédures systématiques permettant de résoudre des problèmes mathématiques.
Le mathématicien allemand David Hilbert formule notamment l’Entscheidungsproblem, ou « problème de la décision ».
De manière simplifiée, la question est la suivante : peut-on concevoir une procédure mécanique qui permette de déterminer, pour n’importe quelle proposition formulée dans un système logique donné, si elle est démontrable ?
Mais cette question en cache une autre.
Que signifie exactement « suivre une procédure mécanique » ?
Aujourd’hui, nous parlerions naturellement d’un algorithme exécuté par un ordinateur.
En 1936, l’ordinateur électronique programmable n’existe pas encore.
Il faut donc définir mathématiquement ce qu’est une procédure de calcul indépendamment de toute machine réelle.
C’est précisément ce que va faire Alan Turing.
Pour replacer cette découverte dans son parcours, la biographie d’Alan Turing revient sur ses travaux en logique, son rôle pendant la Seconde Guerre mondiale et ses contributions aux premiers ordinateurs.
Une machine volontairement très simple
Une machine de Turing classique possède quelques éléments seulement :
un ruban divisé en cases ;
un ensemble limité de symboles ;
une tête de lecture-écriture ;
un ensemble fini d’états ;
une table de règles de transition.
À chaque étape, la machine observe le symbole situé sous sa tête de lecture.
En fonction de ce symbole et de son état actuel, une règle lui indique ce qu’elle doit faire.
Elle peut :
écrire un symbole dans la case actuelle ;
déplacer sa tête d’une case vers la gauche ou vers la droite ;
changer d’état ;
éventuellement s’arrêter.
Puis le processus recommence.
Une succession extrêmement simple d’actions élémentaires peut ainsi produire un calcul complexe.
Le ruban : une mémoire théoriquement illimitée
Le ruban est généralement représenté comme une longue succession de cases.
Chaque case peut contenir un symbole appartenant à un alphabet défini à l’avance.
Dans le modèle théorique classique, le ruban est considéré comme suffisamment grand — souvent idéalement illimité — pour que la machine ne manque jamais de mémoire pendant le calcul étudié.
Cela ne signifie évidemment pas qu’un véritable ordinateur puisse disposer d’une mémoire infinie.
Cette hypothèse sert à séparer deux questions différentes :
un problème est-il théoriquement calculable ?
dispose-t-on de suffisamment de ressources physiques pour effectuer réellement le calcul ?
La machine de Turing s’intéresse principalement à la première.
La tête de lecture-écriture
La tête est la partie active de la machine.
Elle examine une seule case du ruban à la fois.
Elle peut lire le symbole présent, le remplacer éventuellement par un autre, puis se déplacer.
Cette limitation est volontaire.
La machine n’a pas besoin d’observer tout le ruban simultanément.
Elle effectue son travail par une succession d’opérations locales extrêmement simples.
C’est justement ce minimalisme qui rend le modèle si intéressant : si une machine aussi élémentaire peut représenter des calculs très complexes, alors il devient possible d’étudier le calcul lui-même sans dépendre de la technologie utilisée pour construire un ordinateur.
Les états : la mémoire interne de la machine
En plus du contenu du ruban, la machine possède un état courant.
On peut imaginer des états nommés :
q0, q1, q2, etc.
L’état indique dans quelle phase du traitement se trouve la machine.
Une règle peut par exemple dire :
Si la machine est dans l’état q0 et lit le symbole 1, elle écrit 0, se déplace vers la droite et passe dans l’état q1.
Une autre règle décrira ce qu’elle doit faire lorsqu’elle se trouve dans q1.
Le comportement complet de la machine est donc déterminé par la combinaison de trois éléments :
état courant + symbole lu + règle de transition.
Un exemple simple : ajouter 1 à un nombre
Prenons une représentation volontairement simple.
Supposons qu’un nombre entier soit écrit en unaire : le nombre 4 est représenté par quatre symboles 1.
1111
Nous voulons construire une machine qui ajoute 1.
Le programme peut être extrêmement simple :
tant que la tête lit 1, elle se déplace vers la droite ;
lorsqu’elle rencontre une case vide, elle écrit 1 ;
elle s’arrête.
Le ruban devient :
11111
La machine vient de calculer :
4 + 1 = 5
Évidemment, aucun ordinateur moderne n’effectuerait une addition de cette manière.
L’objectif n’est pas l’efficacité.
L’exemple montre qu’un calcul peut être décomposé en une succession de règles mécaniques parfaitement déterminées.
Une machine de Turing est-elle un véritable ordinateur ?
Pas au sens habituel.
La machine de Turing est avant tout un objet mathématique.
Turing ne cherchait pas en 1936 à proposer le plan industriel d’un ordinateur à construire.
Il voulait disposer d’un modèle suffisamment précis pour raisonner sur les procédures calculables.
Des machines physiques inspirées du modèle peuvent être construites à des fins pédagogiques, mais elles ne constituent pas l’objectif initial du concept.
C’est une différence importante avec des projets historiques comme la machine analytique de Charles Babbage, qui était conçue comme une véritable machine mécanique programmable.
De Babbage à Turing : deux façons de penser une machine générale
Au XIXe siècle, Charles Babbage imagine avec sa machine analytique un dispositif capable d’effectuer différents calculs selon les instructions qui lui sont fournies.
Des cartes perforées devaient notamment permettre de représenter certaines opérations et données.
Babbage raisonne principalement en ingénieur et en inventeur : comment construire une machine générale capable d’exécuter différents calculs ?
Turing pose une question plus abstraite :
qu’est-ce qu’une machine de calcul peut faire en principe ?
Les deux approches sont différentes, mais elles participent à une même évolution intellectuelle : séparer progressivement la machine physique des instructions qui déterminent son comportement.
La machine universelle
L’une des idées les plus puissantes de Turing est celle de la machine universelle.
Imaginons plusieurs machines de Turing.
La première effectue une addition.
Une deuxième compare deux nombres.
Une troisième réalise une autre procédure.
À première vue, chaque tâche pourrait nécessiter sa propre machine et sa propre table de règles.
Turing montre cependant qu’une machine particulière peut recevoir sur son ruban :
la description d’une autre machine ;
les données sur lesquelles cette machine doit travailler.
Elle peut alors simuler le fonctionnement de la machine décrite.
C’est la machine de Turing universelle.
Une machine, plusieurs programmes
Cette idée paraît aujourd’hui naturelle parce que nous utilisons quotidiennement des ordinateurs généralistes.
Le même ordinateur peut :
afficher une page web ;
modifier une photographie ;
exécuter un jeu ;
traiter un fichier CSV ;
compiler du code ;
lire une vidéo.
Nous ne reconstruisons pas physiquement l’ordinateur pour chaque tâche.
Nous changeons le programme.
L’idée de machine universelle formalise précisément cette séparation entre le dispositif capable d’effectuer des calculs et la description du calcul à effectuer.
C’est l’une des raisons pour lesquelles les travaux de Turing occupent une place aussi importante dans l’histoire conceptuelle de l’ordinateur.
Machine universelle et architecture de von Neumann : ce n’est pas la même chose
La machine universelle de Turing est parfois assimilée directement à l’architecture des ordinateurs modernes.
Il faut nuancer.
La machine de Turing universelle est un modèle mathématique montrant qu’une machine peut simuler d’autres machines lorsqu’on lui fournit leur description.
L’architecture de von Neumann décrit quant à elle une organisation pratique des ordinateurs électroniques dans laquelle instructions et données peuvent être conservées en mémoire.
Les deux idées possèdent une parenté intellectuelle évidente : dans les deux cas, une même machine physique peut exécuter différents programmes.
Mais elles répondent à des objectifs différents.
Turing étudie la calculabilité.
Von Neumann et les équipes qui développent les premiers ordinateurs électroniques s’intéressent notamment à leur architecture et leur réalisation pratique.
Qu’est-ce qu’un problème calculable ?
Grâce à son modèle, Turing peut donner un sens précis à la notion de calcul.
De manière simplifiée, un problème est considéré comme calculable s’il existe une machine de Turing capable de produire le résultat attendu en suivant un nombre fini d’étapes pour les entrées concernées.
Cette définition permet de transformer une intuition — « il existe sûrement une méthode pour résoudre ce problème » — en une question mathématique.
Peut-on construire une procédure précise ?
Peut-elle être décrite par des règles mécaniques ?
La machine finira-t-elle par produire une réponse ?
Ces questions sont au cœur de la théorie de la calculabilité.
Tous les problèmes ne sont pas calculables
L’un des enseignements les plus importants de Turing est contre-intuitif :
il existe des problèmes qu’aucun algorithme ne peut résoudre dans tous les cas.
Ce n’est pas une limitation temporaire liée aux ordinateurs des années 1930.
Ce n’est pas non plus un problème que l’on résoudra simplement avec des processeurs plus rapides ou davantage de mémoire.
Certaines impossibilités sont inhérentes à la logique du calcul elle-même.
Le meilleur exemple est le problème de l’arrêt.
Le problème de l’arrêt
Imaginons que nous voulions créer un programme appelé HALT.
Nous lui donnons :
un programme quelconque ;
les données fournies à ce programme.
HALT doit répondre à une question :
ce programme finira-t-il par s’arrêter ou tournera-t-il indéfiniment ?
Pour certains programmes, la réponse est facile.
afficher("Bonjour")terminer
Celui-ci s’arrête.
Pour d’autres :
tant que vrai: continuer
celui-ci boucle volontairement.
Mais nous voulons que HALT fonctionne pour absolument tous les programmes possibles et toutes leurs entrées.
Turing démontre qu’un tel algorithme universel ne peut pas exister.
Pourquoi le problème de l’arrêt est-il si important ?
Le résultat révèle une limite fondamentale de l’automatisation.
On pourrait imaginer qu’avec suffisamment de puissance informatique, un outil serait capable d’analyser n’importe quel programme et de prédire parfaitement son comportement.
Ce n’est pas possible dans le cas général.
Cela ne signifie pas que les outils d’analyse de code sont inutiles.
Ils peuvent détecter énormément de problèmes, reconnaître certains types de boucles ou prouver des propriétés pour des catégories particulières de programmes.
Mais aucun outil ne peut résoudre parfaitement le problème de l’arrêt pour tous les programmes possibles.
La différence entre « très difficile » et « impossible en général » est fondamentale.
Une limite indépendante de la puissance matérielle
Supposons que les ordinateurs deviennent un milliard de fois plus rapides.
Le problème de l’arrêt reste indécidable.
Supposons que nous disposions d’une quantité gigantesque de mémoire.
Le problème reste indécidable.
Supposons même un ordinateur idéal, sans les contraintes technologiques de nos machines actuelles.
Le résultat reste identique.
La théorie de la calculabilité montre donc qu’il existe au moins trois types de limites en informatique :
les limites de temps ;
les limites de mémoire ;
les limites de calculabilité.
Les deux premières concernent les ressources nécessaires.
La troisième concerne l’existence même d’un algorithme capable de résoudre le problème.
Calculabilité et complexité : deux questions différentes
Ces notions sont parfois confondues.
La calculabilité demande :
Existe-t-il un algorithme capable de résoudre ce problème ?
La complexité algorithmique demande plutôt :
Si cet algorithme existe, combien de temps ou de mémoire nécessite-t-il ?
Un problème peut donc être parfaitement calculable mais extrêmement coûteux à résoudre.
À l’inverse, un problème indécidable n’a tout simplement pas d’algorithme général fournissant toujours la bonne réponse.
Cette distinction structure encore aujourd’hui une grande partie de l’informatique théorique.
Alonzo Church et le lambda-calcul
Turing n’est pas le seul chercheur à travailler sur ces questions.
Le logicien américain Alonzo Church développe le lambda-calcul, un autre formalisme permettant de représenter des calculs.
Les approches de Church et de Turing sont très différentes en apparence.
Pourtant, elles caractérisent la même classe de fonctions calculables.
Cette convergence est particulièrement importante.
Deux modèles construits indépendamment et reposant sur des principes différents aboutissent à une notion équivalente de ce qui peut être calculé.
La thèse de Church-Turing
Cette convergence conduit à ce que l’on appelle aujourd’hui la thèse de Church-Turing.
Sous une forme simplifiée :
Tout calcul réalisable par une procédure effective peut être effectué par une machine de Turing.
Il faut être précis : il s’agit d’une thèse, pas d’un théorème mathématique ordinaire.
Pourquoi ?
Parce que l’expression « procédure effective » désigne initialement une notion intuitive.
On ne peut pas démontrer mathématiquement qu’un concept formel correspond à toutes les méthodes intuitivement imaginables sans avoir auparavant défini ce concept.
La force de la thèse vient notamment du fait que de nombreux modèles de calcul développés depuis se révèlent équivalents en puissance de calcul.
Un ordinateur moderne est-il une machine de Turing ?
Un ordinateur réel n’est pas littéralement une machine de Turing.
Sa mémoire est limitée.
Il possède une architecture beaucoup plus complexe.
Il exécute plusieurs niveaux de logiciels, utilise des processeurs, des caches, des périphériques et parfois plusieurs cœurs en parallèle.
Cependant, pour étudier ce qui est calculable en principe, les ordinateurs généralistes classiques sont généralement considérés comme équivalents au modèle de Turing, sous réserve de disposer des ressources nécessaires.
Autrement dit, changer de processeur ou de langage de programmation peut rendre un calcul beaucoup plus rapide, mais cela ne permet pas soudainement de résoudre une classe de problèmes que la machine de Turing serait incapable de calculer.
Le langage de programmation change-t-il ce qui est calculable ?
Python, Java, C, JavaScript ou C++ offrent des syntaxes et des abstractions très différentes.
Certains langages sont plus pratiques pour certaines tâches.
Mais un langage de programmation généraliste dit Turing-complet peut, en théorie et avec suffisamment de ressources, exprimer tout calcul réalisable par une machine de Turing.
Cela ne signifie pas que tous les langages sont équivalents en pratique.
La lisibilité, les performances, les bibliothèques, la sécurité et l’écosystème changent énormément.
La puissance théorique de calcul n’est qu’une dimension parmi beaucoup d’autres.
Qu’est-ce que la Turing-complétude ?
On dit généralement qu’un système est Turing-complet lorsqu’il possède suffisamment de capacités pour simuler une machine de Turing universelle, sous les hypothèses théoriques habituelles de mémoire disponible.
Cette expression apparaît souvent à propos :
des langages de programmation ;
de certaines machines virtuelles ;
de systèmes de réécriture ;
parfois même de logiciels ou de jeux dans lesquels des utilisateurs parviennent à construire des mécanismes de calcul.
Être Turing-complet ne signifie pas qu’un système est rapide, pratique ou conçu pour programmer.
Cela signifie essentiellement qu’il possède une puissance d’expression suffisante pour représenter des calculs généraux.
Une machine extrêmement simple peut donc être universelle
C’est probablement l’un des aspects les plus fascinants du modèle.
Il n’est pas nécessaire de disposer de centaines d’instructions différentes pour obtenir une machine universelle.
Des variantes extrêmement simples des machines de Turing peuvent suffire.
Cette observation a profondément influencé notre manière de penser les ordinateurs.
La complexité des logiciels modernes ne vient pas nécessairement d’une infinité d’opérations fondamentales.
Des comportements extrêmement sophistiqués peuvent émerger de la combinaison répétée d’un petit ensemble d’opérations élémentaires.
Les données et les instructions deviennent de l’information
Dans une machine universelle, la description de la machine à simuler est elle-même représentée sous forme de symboles.
Autrement dit, les instructions deviennent des données que la machine peut lire.
Cette idée est extrêmement importante dans l’histoire de l’informatique.
Elle rappelle également une transformation plus générale : textes, nombres, images, programmes ou instructions peuvent tous être représentés sous une forme manipulable par une machine.
L’article consacré à la théorie de l’information explore une autre facette de cette abstraction, notamment la manière dont l’information peut être mesurée et codée.
La machine de Turing ne décrit pas les performances d’un ordinateur
Une confusion fréquente consiste à croire que le modèle permet de comparer directement les performances des machines.
Ce n’est pas son rôle principal.
Une machine de Turing peut effectuer un calcul de manière incroyablement lente par rapport à un véritable ordinateur.
Le modèle cherche surtout à répondre à la question :
ce calcul peut-il être effectué par une procédure algorithmique ?
Pour savoir si une solution est utilisable en pratique, il faut ensuite étudier sa complexité, les algorithmes disponibles et l’architecture réelle de la machine.
Calculabilité et performance sont donc deux niveaux d’analyse distincts.
Et les ordinateurs quantiques ?
L’informatique quantique est parfois présentée comme une technologie qui dépasserait les limites de Turing.
Les ordinateurs quantiques peuvent effectivement offrir des avantages considérables pour certaines catégories de problèmes.
Ils utilisent des principes physiques très différents des ordinateurs classiques.
Mais dans le cadre théorique habituel, ils ne rendent pas calculables les problèmes qui sont fondamentalement non calculables au sens de Turing.
Ils peuvent changer l’efficacité avec laquelle certains calculs sont effectués, pas nécessairement la frontière fondamentale entre calculable et non calculable.
Cette distinction est essentielle lorsqu’on parle des limites futures de l’informatique.
Pourquoi enseigne-t-on encore la machine de Turing ?
À première vue, apprendre le fonctionnement d’un ruban abstrait en 2026 peut sembler éloigné du développement logiciel moderne.
Pourtant, le modèle permet de comprendre plusieurs idées fondamentales :
ce qu’est réellement un algorithme ;
la différence entre programme et machine ;
la notion de calcul universel ;
l’existence de problèmes indécidables ;
la différence entre calculabilité et complexité ;
les fondements théoriques des langages de programmation.
La machine de Turing joue en informatique un rôle comparable à celui de certains modèles idéalisés en physique.
Elle simplifie volontairement la réalité pour rendre visibles les principes fondamentaux.
De la machine de Turing aux ordinateurs modernes
La machine de Turing de 1936 n’est pas directement l’architecture de nos ordinateurs.
Mais elle participe à une évolution intellectuelle majeure.
Au XIXe siècle, Babbage imagine une machine mécanique programmable.
Les cartes perforées montrent qu’instructions et données peuvent être représentées sur un support externe.
Turing formalise ensuite l’idée d’une machine universelle capable d’exécuter n’importe quel calcul algorithmique décrit convenablement.
Dans les années 1940, les premiers ordinateurs électroniques à programme enregistré transforment progressivement ces idées en systèmes physiques.
L’architecture de von Neumann devient alors l’un des modèles les plus influents pour organiser concrètement processeur, mémoire, données et instructions.
Ces étapes ne constituent pas une ligne droite et de nombreux chercheurs y ont contribué, mais elles montrent comment une question abstraite sur la nature du calcul a fini par rejoindre la construction des ordinateurs.
Un héritage toujours présent
Presque quatre-vingt-dix ans après l’article de Turing, son modèle reste au cœur de l’informatique théorique.
Chaque fois que l’on demande :
si un problème peut être automatisé ;
si un programme peut analyser parfaitement tous les autres programmes ;
si un langage peut exprimer des calculs généraux ;
quelles sont les limites intrinsèques des algorithmes ;
on retrouve, directement ou indirectement, les questions posées par la théorie de la calculabilité.
Les ordinateurs ont changé de manière spectaculaire.
Les transistors ont remplacé les dispositifs électromécaniques.
Les mémoires contiennent des milliards d’octets.
Des réseaux relient des milliards de machines.
Les systèmes d’intelligence artificielle traitent des volumes de données inimaginables à l’époque de Turing.
Mais davantage de puissance ne supprime pas les limites mathématiques du calcul.
C’est peut-être l’héritage le plus profond de la machine de Turing.
À retenir
La machine de Turing est un modèle mathématique du calcul proposé par Alan Turing en 1936.
Elle repose sur quelques éléments simples : un ruban, une tête de lecture-écriture, des symboles, des états et des règles de transition.
Sa simplicité permet d’isoler l’essentiel : une procédure algorithmique peut être décrite comme une succession d’opérations mécaniques précises.
L’idée de machine universelle montre qu’une seule machine peut simuler de nombreuses autres machines lorsqu’elle reçoit leur description comme donnée. Cette notion annonce conceptuellement la séparation moderne entre matériel et logiciel.
Mais Turing montre également que la puissance du calcul possède des limites fondamentales.
Le problème de l’arrêt démontre qu’il n’existe pas d’algorithme universel capable de déterminer pour tous les programmes s’ils finiront par s’arrêter.
La machine de Turing nous apprend donc deux choses apparemment opposées :
une machine très simple peut effectuer une immense variété de calculs, mais aucune machine algorithmique ne peut tout calculer.
C’est cette double découverte qui en fait encore aujourd’hui l’un des concepts fondamentaux de l’informatique.
Questions fréquentes
Qui a inventé la machine de Turing ?
Le modèle a été proposé par le mathématicien britannique Alan Turing dans son article de 1936 On Computable Numbers, with an Application to the Entscheidungsproblem.
Une machine de Turing a-t-elle réellement été construite ?
Le concept original est un modèle mathématique, pas le plan d’un ordinateur destiné à être construit. Des versions physiques ont depuis été réalisées à des fins pédagogiques ou expérimentales.
À quoi sert une machine de Turing ?
Elle sert principalement à formaliser la notion d’algorithme et à étudier quels problèmes sont calculables ou non.
Qu’est-ce qu’une machine de Turing universelle ?
C’est une machine de Turing capable de simuler n’importe quelle autre machine de Turing lorsque sa description et ses données lui sont fournies sous une forme appropriée.
Qu’est-ce que le problème de l’arrêt ?
Il consiste à déterminer si un programme donné finira par s’arrêter ou continuera indéfiniment. Turing a montré qu’il n’existe pas d’algorithme général capable de répondre correctement à cette question pour tous les programmes et toutes les entrées.
Un ordinateur moderne est-il une machine de Turing ?
Pas littéralement. Un ordinateur réel possède une mémoire finie et une architecture beaucoup plus complexe. Mais pour étudier la calculabilité, les ordinateurs généralistes classiques sont modélisés comme ayant une puissance de calcul équivalente à celle d’une machine de Turing.
Que signifie « Turing-complet » ?
Un système Turing-complet possède, en théorie, les mécanismes nécessaires pour simuler une machine de Turing universelle, à condition de disposer de suffisamment de temps et de mémoire.
Un ordinateur quantique peut-il résoudre le problème de l’arrêt ?
Non, pas dans le cadre standard de la théorie de la calculabilité. L’informatique quantique peut accélérer certains calculs, mais elle ne rend pas automatiquement calculables les problèmes indécidables au sens de Turing.
Découvrez Alan Turing, ses travaux sur la calculabilité, son rôle à Bletchley Park, ses projets d’ordinateur et sa contribution fondatrice à l’intelligence artificielle.
Découvrez l’architecture de la machine analytique de Charles Babbage : magasin, moulin, cartes perforées, boucles et principes d’un ordinateur programmable.
