La machine de Turing — Les fondations théoriques de l'informatique

Découverte

Explication technique

1. Définition formelle — La machine de Turing se compose de : (a) un ruban infini divisé en cases, chacune contenant un symbole d'un alphabet fini (incluant le symbole blanc □), (b) une tête de lecture/écriture capable de lire le symbole courant, d'écrire un symbole, et de déplacer le ruban d'une case à gauche ou à droite, (c) un registre d'état contenant l'état courant parmi un ensemble fini Q = {q₁, q₂, ..., qₙ}, et (d) une table de transition δ : Q × Σ → Q × Σ × {L, R} qui détermine, pour chaque couple (état, symbole lu), le nouvel état, le symbole à écrire, et la direction du déplacement.

2. Machine universelle — Turing démontre qu'il existe une machine de Turing particulière U (la machine universelle) capable de simuler toute autre machine de Turing M : il suffit d'encoder la table de transition de M sur le ruban de U. La machine universelle lit cette description et l'exécute pas à pas. Ce concept est exactement le principe de l'ordinateur à programme enregistré : la même machine exécute n'importe quel programme.

3. Le problème de l'arrêt — Turing prouve par diagonalisation (inspirée de Cantor) qu'il n'existe aucune machine de Turing capable de décider, pour toute machine M et toute entrée x, si M s'arrête ou boucle indéfiniment sur x. La preuve : supposons qu'une telle machine H existe ; on construit une machine D qui, sur l'entrée M, exécute H(M, M) et fait l'inverse (boucle si H dit « s'arrête », s'arrête si H dit « boucle »). Que fait D(D) ? Contradiction. Donc H ne peut pas exister.

4. Thèse de Church-Turing — Turing et Church arrivent indépendamment au même résultat : toute fonction calculable peut être calculée par une machine de Turing. Ce n'est pas un théorème (il ne peut être prouvé formellement), mais une thèse empirique : aucun modèle de calcul conçu depuis 1936 (lambda-calcul, automates cellulaires, machines quantiques) n'a calculé une fonction que la machine de Turing ne peut pas calculer. Seul le temps de calcul diffère.

Pourquoi ça a fonctionné

Le contexte : en 1928, David Hilbert pose l'Entscheidungsproblem — existe-t-il une procédure mécanique pour déterminer la vérité ou la fausseté de toute proposition mathématique ? Pour répondre, Turing devait d'abord formaliser ce qu'est une « procédure mécanique ». Sa machine abstraite — d'une simplicité radicale (ruban, tête, états, table) — capture l'essence de tout calcul effectif. La simplicité du modèle est sa force : tout ce qui peut être ajouté (plusieurs rubans, mémoire à accès aléatoire, parallélisme) ne fait que changer la vitesse, pas la classe de fonctions calculables.

Le résultat négatif (l'indécidabilité) est aussi fondamental que le résultat positif (la calculabilité). Il trace une frontière absolue : certains problèmes sont mathématiquement prouvés insolubles par toute machine, présente ou future.

Chaîne causale

Hilbert pose l'Entscheidungsproblem (1928) → Gödel prouve l'incomplétude (1931) → Church définit le lambda-calcul (1936) → Turing formalise la machine abstraite et prouve l'indécidabilité (1936) → Turing déchiffre Enigma à Bletchley Park avec la Bombe (1939–1945) → von Neumann conçoit l'architecture à programme enregistré EDVAC (1945) → premiers ordinateurs (ENIAC 1945, Manchester Baby 1948) → Turing propose le test d'intelligence artificielle (1950) → langages de programmation (Fortran 1957, LISP 1958) → théorie de la complexité NP-complétude (Cook, 1971)

Anecdote

L'article de Turing a failli ne jamais être publié : quand il l'a soumis en mai 1936, il a appris que Church venait de publier un résultat équivalent via le lambda-calcul (avril 1936). Son conférencier et mentor à Cambridge, M.H.A. Newman — son directeur de thèse sera Alonzo Church, à Princeton —, l'a convaincu de maintenir la publication car le modèle de la machine — concret, mécanique, visualisable — était fondamentalement plus intuitif que le formalisme abstrait de Church. Newman avait raison : c'est la machine de Turing, pas le lambda-calcul, qui a inspiré directement la construction des premiers ordinateurs.

Limites et controverses

Les statistiques de parts de marché et d'adoption varient selon les méthodologies de mesure (enquêtes, analyses de trafic, déclarations des éditeurs). Les chiffres présentés sont des ordres de grandeur issus de sources spécialisées. L'histoire de l'informatique fait l'objet de controverses de priorité non exhaustivement couvertes ici.

Sources

Références vérifiées lors de l'audit factuel d'août 2026 : ce sont les pages
contre lesquelles les affirmations de ce bulletin ont été confrontées.

1. On Computable Numbers, with an Application to the Entscheidungsproblem (fac-similé)
2. The Annotated Turing (contexte et chronologie) — Princeton University Press
3. Apple reveals M3 Ultra (184 milliards de transistors) — Apple Newsroom