Histoire et cultureOutil · Glossaire
machine de Post
La machine de Post est un modèle abstrait de calcul composé d’un ruban divisé en cases marquées ou non, d’une tête qui lit, écrit et se déplace, et d’un programme fini de règles. Un calcul consiste à répéter ces actions locales depuis une configuration initiale ; ce modèle a la même puissance de calcul qu’une machine de Turing.
Sommaire
Ce que vous allez apprendre
- Reconnaître le ruban, la tête et le programme fini de règles.
- Suivre une exécution simple de la configuration initiale à l’arrêt.
- Distinguer la machine de Post du problème de correspondance de Post.
- Interpréter correctement l’équivalence avec la machine de Turing et l’indécidabilité.
En clair
Imaginez une longue bande de cases, dont chacune est soit vide, soit marquée. Une tête se place sur une case, regarde son état, peut le modifier, puis se déplace selon une consigne. La consigne suivante dépend de ce qui vient d’être lu.
La machine de Post réduit ainsi un calcul à une suite de gestes élémentaires. Le ruban conserve l’information, la tête agit localement et un nombre fini de règles organise l’ensemble.
Définition
Une machine de Post est un modèle abstrait de calcul. Son support est un ruban partagé en cases, chacune portant l’un de deux états : marquée ou non marquée. Une tête de lecture et d’écriture désigne une seule case à la fois. Elle en lit l’état, peut le changer et se déplace sur le ruban conformément au programme.
Le programme contient un nombre fini de règles. À chaque étape, la règle en cours et l’état observé déterminent l’action suivante. La configuration de la machine réunit donc le marquage du ruban, la position de la tête et la règle active. Le ruban porte les données et les résultats, tandis que les règles décrivent le calcul.
Ce modèle publié par Emil Leon Post en 1936 sous le titre « Formulation I » possède la même puissance de calcul que la machine de Turing. Cette équivalence concerne ce que les deux modèles peuvent calculer, et non l’identité de leur présentation ni de leurs gestes élémentaires.
Où on le rencontre
On rencontre la machine de Post dans une représentation de calcul sur ruban. Quatre marqueurs permettent de la reconnaître : une suite de cases, deux états possibles par case, une tête placée sur une case et un programme fini de règles. Des flèches peuvent aussi signaler les déplacements successifs de la tête.
Le dessin ne représente pas un appareil matériel. Il encode une configuration : les marques constituent la mémoire visible, la position de la tête indique où aura lieu la prochaine lecture, et la règle active précise l’action à exécuter.
Le mode d'emploi
La grandeur à suivre n’est pas une mesure physique, mais l’évolution de la configuration complète de la machine.
1. Repérez la case sous la tête et notez si elle est marquée.
2. Lisez la règle active, puis choisissez la branche correspondant à cet état.
3. Appliquez exactement l’écriture ou le déplacement annoncé.
4. Passez à la règle indiquée et recommencez, sauf si le programme s’arrête.
2. Lisez la règle active, puis choisissez la branche correspondant à cet état.
3. Appliquez exactement l’écriture ou le déplacement annoncé.
4. Passez à la règle indiquée et recommencez, sauf si le programme s’arrête.
La convention essentielle est l’origine choisie pour numéroter les cases et le sens positif du ruban. L’œil peut suivre seulement la tête et oublier qu’une ancienne marque reste en mémoire. Le bon réflexe consiste à recopier après chaque étape le ruban, la position de la tête et la règle active.
Un exemple, pas à pas
Considérons un programme illustratif et un ruban numéroté vers la droite. Au départ, les cases −1 et 2 sont marquées, la tête est sur la case 0 et la règle 1 est active. La figure reprend les données de chaque configuration.
1. La règle 1 marque la case 0, déplace la tête d’une case vers la droite, puis active la règle 2. La tête arrive donc sur la case 1.
2. La règle 2 teste la case 1. Comme elle n’est pas marquée, elle déplace la tête d’une case vers la droite et active la règle 3.
3. La règle 3 teste la case 2. Cette case est marquée : le programme s’arrête sans la modifier.
À l’arrêt, les cases −1, 0 et 2 sont marquées, et la tête se trouve sur la case 2. Le contrôle consiste à comparer les deux configurations : seule la case 0 a changé, tandis que deux déplacements vers la droite ont conduit la tête de 0 à 2.
En pratique
Pour étudier un calcul, on écrit une configuration initiale puis on déroule les règles une par une. Cette trace convient lorsque l’on veut vérifier localement chaque lecture, écriture et déplacement.
Pour comparer des modèles théoriques, on cherche à traduire les calculs de l’un dans l’autre. La machine de Turing constitue l’alternative naturelle lorsque sa présentation facilite davantage le raisonnement ; leur puissance de calcul est équivalente.
Pour réfléchir aux limites des algorithmes, on sépare la simulation d’un programme particulier de l’existence d’une procédure générale. Le problème de correspondance de Post montre précisément que certains problèmes de décision n’admettent pas un tel algorithme universel.
À ne pas confondre
Machine de Post et machine de Turing. Elles ont la même puissance de calcul, mais leur présentation n’est pas identique. Si l’énoncé parle précisément du ruban à cases marquées ou non et du modèle de Post, le nom « machine de Post » reste pertinent.
Machine de Post et problème de correspondance de Post. La première est un modèle de calcul sur ruban. Le second est un problème de décision sur la concaténation de mots. Un exercice qui demande d’associer des suites de mots relève du problème de correspondance, pas du fonctionnement du ruban.
Limites et pièges
Une exécution réussie ne prouve pas qu’une méthode générale existe. Le symptôme est un raisonnement fondé sur quelques exemples terminés. Il faut distinguer le déroulement de ces cas particuliers de la preuve qu’un algorithme répond dans tous les cas.
Équivalence ne signifie pas identité. Deux modèles peuvent calculer les mêmes choses sans employer la même description. Il faut comparer leur puissance de calcul séparément de leur ruban, de leurs symboles ou de leurs règles élémentaires.
L’indécidabilité ne signifie pas que chaque cas est insoluble. Pour le problème de correspondance de Post, l’absence porte sur un algorithme général capable de répondre correctement à toutes les instances. Il faut donc annoncer la portée universelle du résultat, sans conclure que nul cas particulier ne peut être tranché.
Pour aller plus loin
La machine de Turing offre un autre modèle de calcul théorique de même puissance et permet de comparer les conventions de représentation.
La fiche décidabilité et indécidabilité précise ce que signifie l’absence d’un algorithme général pour un problème de décision.
La notion d’algorithme aide à relier un programme fini de règles à une procédure exécutable étape par étape.
Explorez les mathématiques autrement
Retrouvez nos magazines, podcasts et jeux pour explorer les mathématiques autrement.
Découvrir les offres