Comptes Rendus Hebdomadaires des Séances de L'académie des Sciences, 257:2597--2600, Séance du 28 Octobre 1963.

• LOGIQUE MATHéMATIQUE. --- Machines de Turing réversibles.
  Récursive insolubilité en de l'équation , où est un isomorphisme de codes . Note () de M. Yves Lecerf, présentée par M. André Lichnerowicz.

• On définit des machines de Turing réversibles et des isomorphismes de codes . Leurs propriétés permettent de prouver que l'equation en , est récursivement insoluble. Une second Note appliquera ceci à la démonstration d'une conjecture de Schützenberger rattachant le problème des correspondances de Post à des problèmes de diagonalisation d'homomorphismes de monoïdes libres.

1. ISOMORPHISMES DE CODES, éPIMORPHISMES DE CODES. --- a. Une conjecture de Schützenberger. --- Soient deux monoïdes libres non triviaux et , soient deux homomorphismes et de dans , et soit le problème de la recherche de solutions non triviales pour l'équation de diagonalisation . Un résultat de Post () est que cette équation est récursivement insoluble dans le cas de et homomorphismes quelconques. Elle l'est également lorsqu'on astreint à être un monomorphisme; Chomsky et Schützenberger ont fait observer, en effet (), que ce cas peut se ramener au Tag-problem de Post () lui-même récursivement insoluble d'après un résultat de Minsky (). Schützenberger a conjecturé que l'équation reste encore récursivement insoluble quand à la fois et sont deux monomorphismes.

b. Isomorphismes de codes. --- Au lieu de , il revient au même de considérer l'équation , où (ce qui est une notation abrégée pour dire que est une bijection de dans définie par pour ). Par facilité de langage, on appellera isomorphismes de codes les applications telles que . Ce terme rappelle que ; et aussi que, désignant l'alphabet (les générateurs) de , et sont appelés des codes sur , car, pour y quelconque de , il existe au plus un ensemble d'indices tels que , et de même pour . En fait, c'est surtout à l'étude des isomorphismes de code que seront consacrées la présente Note et la suivante.

c. Définitions d' isomorphismes de codes particuliers par donnée de relations. --- et désignant les éléments neutres respectivement de et de , il va de soi implicitement pour tout que l'on a , avec (d'où, d'ailleurs, une solution triviale pour et pour , avec ). Ceci étant, chaque isomorphisme de codes particulier pourra être défini par la donnée d'un ensemble de relations du type , à condition que et soient des codes et que la correspondance soit bijective. En effet, est implicitement défini par , l'est par les symboles utilisés pour noter les et ; et l'on peut interpréter les relations comme des correspondances .

d. Vérification qu'un ensemble de mots donnés est un code. --- Plus loin, on invoquera souvent la propriété suivante : Si et désignent respectivement un code et un préfix-code droit sur , et si est un symbole (générateur de ) ne figurant pas dans ni dans , alors, l'ensemble est un code. De même, en remplaçant par un préfix-code gauche , l'ensemble est un code. Rappelons que tout préfix-code droit est par définition () tel que, si , et si, avec , on a , alors, (tandis que pour les préfix-codes gauches, c'est qui impose ).

e. Épimorphismes de codes. --- On parlera d' épimorphisme de codes dans le cas de relations , où est bien un code , mais où est astreint seulement à ne pas contenir d'autres mots que ceux d'un code . MACHINES DE TURING RéVERSIBLES. --- Soit une machine de Turing MT dont et sont les ensembles d'états et de symboles, et les déplacements de ruban, qui peuvent être ou 0. On peut définir MT par un ensemble de quintuples

où les indices sont fonctions de l'indice i. A chacun de ces quintuples, décidons d'associer un quintuple image inverse (; ; ; ; ). L'ensemble de ceux-ci ne constituera généralement pas une machine de Turing; mais lorsqu'il en sera ainsi, on dira que MT est réversible , et l'on donnera à la nouvelle machine le nom d'image inverse MT de MT. Les seront dits images des . La substitution d'un à un dans une configuration instantanée sera dite passage à à sa configuration image . Les suites de configurations de sont images de celles de MT, mais les parcourt dans l'ordre inverse. Considérons maintenant la machine R (MT), dont l'ensemble de quintuples est

où désigne tout couple pour lequel MT stoppe. Si l'on fait partir MT et R(MT) d'une même configuration instantanée , elles passent par les mêmes configurations tant que MT ne stoppe pas (donc éventuellement indéfiniment). Lorsque MT stoppe, R(MT) continue, parcourt en ordre inverse les configurations images des configurations parcourues, et passe par l'image de la configuration initiale. R(MT) sera dite couplage de MT avec son image inverse. REPRéSENTATION DE MACHINES DE TURING PAR DES éPIMORPHISMES (OU DES ISOMORPHISMES) DE CODES. --- Revenons au cas où MT est quelconque. A chacun de ses quintuples comportant le mouvement +1, soit par exemple , on associe trois relations, à savoir ici : . Aux , on associe : . Aux , on associe . Enfin, à tout symbole de MT, on associe . On peut vérifier, par le procédé donné au paragraphe 1, d, que l'ensemble de toutes ces relations définit un épimorphisme de codes. Soit celui-ci, est une représentation de MT, car il en définit l'alphabet et les quintuples. On peut, d'autre part, trouver pour les configurations instantanées de MT des notations telles que pour tout couple de configurations successives on ait . Pour cela, une configuration se composera d'une suite de symboles (le mot du ruban) dans laquelle on intercalera une des lettres ou , avec un indice p égal à celui de l'état de la machine, et de façon à indiquer, non seulement la position du prochain symbole à lire, mais encore celle du symbole précédemment écrit (acev convention particulière pour la configuration initiale). Un signifie que est le premier symbole à sa droite, le premier à sa gauche. Un , l'inverse. Un signifie que et , confondus, sont tous deux le premier symbole à droite de ce . On a bien alors . Si certains états ne peuvent apparaître que sous deux seulement, ou une seule, des formes , et soit obtenu en retranchant de toutes les relations contenant des formes qui n'apparaissent jamais, alors, est encore tel que . Si est un isomorphisme de codes, MT est réversible. SIMULATION DE MT QUELCONQUE SUR #TEX2HTML_WRAP_INLINE601# RéVERSIBLE. APPLICATION AUX ISOMORPHISMES DE CODES. --- a. Propriété. --- On peut simuler une machine de Turing MT quelconque (de configurations ) sur une machine de Turing réversible (de configurations ) de façon que : quand MT passe de à , passe de à par l'intermédiaire d'un nombre fini de configurations ; on passe d'un au suivant par un épimorphisme de codes , d'un au suivant par un isomorphisme de codes ; si les configurations initiales sont pour MT et pour , avec , alors pour tout i, on a , où est un mot, et où sont trois symboles qui n'apparaissent ni dans ni dans , si bien que connu donne et ; il y a des symboles dont chacun représente une relation de autre que d'identité; un symbole blanc b; et pour tout i on a , où est la relation intervenue dans . Ainsi, représente l'histoire du calcul de MT jusqu'au temps i; stoppe sur les correspondant à des stop de MT, et eux seulement; la machine , couplage de avec son image inverse, partie de passe par la configuration image si et seulement si MT, partie de , stoppe; il existe pour certaines configurations instantanées telles que, partant de , ne peut atteindre ces configurations autrement qu'en passant par (c'est-à-dire si MT, partie de , stoppe). On peut ainsi faire en sorte que le retour de à (ou bien, le passage par des encadrés par au lieu de ) soit conditionné par un stop de MT.

Preuve. --- On montre comment passer de , supposé donné par un ensemble de relations à l'ensemble des relations définissant et . Limitons-nous à donner le principe de cette construction, en montrant comment simuler une instruction de la forme . A celle-ci, on associera : une instruction , où le symbole marque la place où l'on doit modifier , et la nature de la modification; des instructions permettant de conduire le contrôle à gauche de par un état ; une instruction , où représente , complètant ; des instructions de service déplaçant et, éventuellement aussi , et tout entier, pour rétablir les blancs nécessaires dans puis reportant le contrôle en avec un état ; une instruction qui complète dans .

b. THéORèME 1. --- Le problème du stop pour une machine de Turing réversible générale est indécidable. Il en est de même du problème du retour à la configuration initiale, et de celui du passage par une configuration déterminée autre que la configuration initiale.

c. THéORèME 2. --- L'équation , où est un isomorphisme de codes, avec est récursivement insoluble en n pour w, donnés quelconques. L'equation , avec , est aussi récursivement insoluble en n. () Séance du 21 octobre 1963.

() N. CHOMSKY et M. P. SCHüTZENBERGER, Computer Programming and Formal Systems, Hirschberg et Braffort, North-Holland Publ. Co., Amsterdam, 1963, p. 118--161.

() H. WANG, Mathematische Annalen, 152, 1963, p. 65--74.

() M. MINSKY, Annals of Math., 74-3, 1961.

() M. P. SCHüTZENBERGER, I. R. E. Trans. Inf. Theory, IT-2, 1956, p. 47-60.

() E. POST, Amer. J. Math., 65, 1943, p. 196--215.

() E. POST, Bull. Amer. Math. Soc., 52, 1946, p. 264--268. (Euratom, 51, rue Belliard, Bruxelles.)

• About this document ...