A Turing machine is an abstract computational model that manipulates symbols on a tape.Formellement, la machine de Turing se compose d'une bande infinie divisée en cellules, chacune contenant un symbole d'un alphabet fini ; d'un dispositif de commande avec une mémoire d'états finie ; et d'une tête capable de lire, écrire et se déplacer d'une cellule. La fonction de transition détermine, en fonction de l'état actuel et du symbole lu, un nouveau symbole, la direction du déplacement (G/D) et le nouvel état. La machine commence à travailler avec un mot d'entrée sur la bande et peut s'arrêter dans un état acceptant ou rejetant, ou bien se retrouver dans une boucle infinie. Une machine de Turing universelle peut simuler n'importe quelle autre machine en utilisant sa description – une préfiguration du concept d'ordinateur programmable.
En 1936, Alan Turing, en résolvant l'Entscheidungsproblem (problème de la décision) de David Hilbert, a introduit le concept de « a-machine » (machine automatique) dans l'article « On Computable Numbers ». Son but était de formaliser la notion intuitive d'algorithme. Indépendamment, Alonzo Church est arrivé à la notion équivalente du lambda-calcul. La thèse de Church-Turing affirme que tout processus intuitivement calculable est réalisable sur une machine de Turing. En 1945, John von Neumann a utilisé ce modèle dans l'architecture de l'EDVAC – prototype des ordinateurs modernes. En 1985, David Deutsch a proposé la machine de Turing quantique, ouvrant la voie au calcul quantique.
La machine de Turing calcule en manipulant des chaînes de symboles. Du point de vue algorithmique, elle est équivalente à un langage de programmation avec un seul tableau de longueur infinie. Propriétés clés : existence d'une machine universelle (interpréteur), indécidabilité du problème de l'arrêt (on ne peut pas déterminer algorithmiquement si une machine arbitraire s'arrêtera sur une entrée donnée), théorème de récursion (une machine peut obtenir sa propre description). En théorie de la complexité, on considère les machines à oracle (avec information supplémentaire) et les machines probabilistes (avec générateur de bits aléatoires). Les machines de Turing quantiques opèrent sur des états dans un espace de Hilbert et utilisent des transformations unitaires ; elles ne contredisent pas la thèse de Church-Turing, mais peuvent apporter une accélération exponentielle pour certaines tâches.
Tout programme informatique – de la calculatrice à l'assistant IA – se résume à des instructions que la machine de Turing peut exécuter. Toute la théorie du calcul repose sur elle.
La plus simple machine de Turing universelle, imaginée par Marvin Minsky, n'utilise que 7 états et 4 symboles – et pourtant elle est capable de calculer tout ce que peut un supercalculateur puissant, bien qu'incroyablement lentement.










