mathématiques

machine de Turing

A Turing machine is an abstract computational model that manipulates symbols on a tape.
4 articles liés · 1 qui a travaillé ici

Description

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.

Histoire

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.

Comment ça marche

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.

En pratique

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.

Anecdote

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.

Concept graph →

Articles liés · 16

Quatre chefs d'orchestre pour l'orchestre cellulaire : comment l'épithélium choisit sa fluidité
L'épithélium tapisse nos organes comme un carrelage recouvre le sol. Au repos, les cellules se tiennent les unes aux autres et le tissu est élastique. Mais pendant le développement de l'embryon, la cicatrisation d'une plaie ou la croissance d'une tumeur, cette couche se met à couler comme du miel épais. Qu'est-ce qui déclenche exactement ce ramollissement ?
Restauration du Z3 : les cliquetis des relais ressuscitent un ordinateur disparu
Berlin, décembre 1943. L'éclair d'une bombe, et le Z3, premier ordinateur entièrement automatique et programmable de l'histoire, disparaît dans les flammes. Son créateur, Konrad Zuse, ne tente même pas de reconstruire la machine : après la guerre, il bâtit de nouveaux ordinateurs.
Un orchestre sans chef : le gang élastique pour l'inférence de LLM
Sept cœurs sont figés devant une barrière invisible. Le huitième s'attarde sur un processus étranger — et toute l'inférence de grands modèles de langage se bloque. Voilà le principal conflit de la vie commune entre les tâches d'apprentissage automatique et les processus ordinaires sur un même processeur.
Le seuil 2 : comment une règle en caoutchouc résiste à une moyenne infinie
2 — le seuil au-delà duquel une suite docile risque de perdre sa structure. Au lieu de l'échelle uniforme habituelle — une règle en caoutchouc à l'élasticité inégale. C'est ainsi que sont faits les espaces d'Orlicz : des espaces de Banach de suites où chaque échelle a sa propre rigidité, décrite par une fonction de Young convexe (une sorte de ressort).
Un ordinateur chimique dans une éprouvette
Dans une éprouvette, des molécules flottent. Leur quantité — disons, la concentration d'une certaine protéine — devient le signal d'entrée. Et à la sortie, on ne veut pas juste une solution trouble, mais une réponse claire du genre « oui » ou « non ». Les auteurs de l'étude construisent une chaîne chimique qui fait exactement cela.
L'écriture sans alphabet : comment le cerveau dessine des lettres qu'il n'a jamais vues
La main trace dans l'air le mot « maman » — des arcs et des bâtons familiers. Le cerveau, lui, ne fait pas défiler la photo de chaque lettre. Il déclenche une chaîne de mouvements simples. Des neuro-ingénieurs ont testé cette idée : l'écriture mentale n'est pas une galerie d'images toutes faites, mais un jeu de construction à partir des mêmes « briques » motrices.
Comment empêcher les moteurs moléculaires de patiner
À l'intérieur de chaque cellule, la vie grouille : de minuscules machines protéiques transportent sans relâche des cargaisons, lisent les gènes et corrigent les erreurs. Mais leur travail est loin d'être parfait : elles « patinent » sans arrêt, font des pas en arrière ou se retrouvent coincées dans des cycles inutiles.
Régler un moteur moléculaire sans se casser la tête
Une usine où des centaines de minuscules chaînes de montage tournent sans arrêt. Chaque chaîne est un moteur moléculaire qui convertit un carburant chimique en mouvement. Pour que le moteur aille plus vite ou dans la bonne direction, l'ingénieur modifie les réglages — la forme des pièces, la force des interactions.
L'intelligence artificielle trace la voie vers des puces optiques
Le faisceau d'un laser se divise en des dizaines de filaments ténus, traverse un verre dépoli, puis se reconstitue en un point unique. Voilà à quoi ressemble la paillasse sur laquelle s'est installé le programme. On ne lui a donné aucune consigne, seulement un objectif général : comprendre comment la lumière se modifie en traversant un milieu diffusant, et trouver quelque chose de nouveau.
Physique atomique2026-04-241 minarXiv:2604.22406express
Pièges à atomes : comment les remplir à ras bord
Une pince optique est un faisceau laser qui maintient un atome en un point précis, comme des doigts tiennent un petit pois. De ces pinces, on assemble des réseaux entiers d'atomes – la base des futurs ordinateurs quantiques. Mais il y a un problème : tous les pièges ne capturent pas un atome.
Une machine qui ne se gêne plus elle-même
Un orchestre où chaque musicien joue sa partition mais n'entend que son voisin. Qu'un seul se trompe, et une vague d'erreurs déferle sur toute la salle. C'est ainsi que fonctionnent les machines d'Ising, des dispositifs spécialisés dans la résolution de problèmes où il faut trouver la meilleure option parmi une multitude.
Physique quantique2026-04-151 minarXiv:2604.13872express
La danse des ions : naissance des tourbillons quantiques
Dans un piège à champs, des scientifiques ont assemblé un cristal de 150 ions à température extrêmement basse. Chaque ion se comporte comme un minuscule aimant capable de s'orienter dans toutes les directions.
Des idées que personne n'a cherchées
La science ressemble à une ville où les rues sont tracées par les habitants eux-mêmes. Là où des sentiers sont déjà battus, on construit de nouvelles maisons, tandis que les terrains vagues restent ignorés — non pas parce qu'on ne peut pas y bâtir, mais parce que personne n'y va.
Méthodologie2026-02-191 minarXiv:2602.17772express
Le cerveau imprime tout seul : comment des paires d'électrodes accélèrent la lecture des pensées
Une personne regarde un écran où des lettres clignotent. Elle ne bouge ni la main ni l'œil – elle note seulement mentalement le symbole souhaité. Des capteurs sur la tête captent les faibles ondes électriques du cerveau, et l'ordinateur comprend quelle lettre la personne a choisie.
Supraconductivité2026-01-101 minarXiv:2601.06632express
Mémoire supraconductrice : un interrupteur qui n'oublie rien
La mémoire informatique ordinaire consomme constamment de l'énergie pour ne pas oublier ce qu'elle a enregistré. Un supraconducteur pourrait stocker des données sans perte, mais il est difficile de le faire basculer. Dans ces travaux, le supraconducteur est pris en sandwich entre deux isolateurs magnétiques.
Résonance tunnel : quand les diodes apprennent à voir
En 1974, des physiciens ont décrit pour la première fois un dispositif dans lequel les électrons traversent une barrière d'énergie grâce à l'effet tunnel quantique. Aujourd'hui, ce dispositif, la diode à effet tunnel résonant, devient le cœur d'une architecture de calcul inhabituelle.