Comptes Rendus Hebdomadaires des Séances de L'académie des Sciences, 257:2597--2600, Séance du 28 Octobre 1963. 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  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.)