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 n ∈ N de l’équation u = θ^{n}u, 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 n ∈ N, u = θ^{n}u 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 A^{†} et S^{†}, soient deux homomorphismes φ et ψ de A^{†} dans S^{†}, et soit le problème de la recherche de solutions non triviales x ∈ A^{†} pour l’équation de diagonalisation φx = ψx. Un résultat de Post (^{6}) 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 (^{1}), que ce cas peut se ramener au Tag-problem de Post (^{5}) lui-même récursivement insoluble d’après un résultat de Minsky (^{3}). Schützenberger a conjecturé que l’équation φx = ψx reste encore récursivement insoluble quand à la fois φ et ψ sont deux monomorphismes.

b. Isomorphismes de codes. — Au lieu de φx = ψx, il revient au même de considérer l’équation w = θw, où θ = ψφ^{−1} (ce qui est une notation abrégée pour dire que θ est une bijection de φA^{†} dans ψA^{†} définie par θw = ψx pour w = φx). Par facilité de langage, on appellera ^{≪} isomorphismes de codes ^{≫} les applications telles que θ. Ce terme rappelle que θ(w_{1}w_{2}) = θw_{1} θw_{2}; et aussi que, A = { a_{i} }_{i∈I} désignant l’alphabet (les générateurs) de A^{†}, { φa_{i} }_{i∈I} et { ψa_{i} }_{i∈I} sont appelés des^{≪} codes^{≫} sur S^{†}, car, pour y quelconque de S^{†}, il existe au plus un ensemble d’indices { i_{1}, i_{2}, …, i_{p} } tels que y = φa_{i_{1}} φa_{i_{2}} … φa_{i_{p}}, 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.

— e_{A} et e_{S} désignant les éléments neutres respectivement de A^{†} et de S^{†}, il va de soi implicitement pour tout θ que l’on a e_{S} = θe_{S}, avec φe_{A} = ψe_{A} = e_{S} (d’où, d’ailleurs, une solution triviale pour w = θw et pour w = θ^{n}w, avec n ∈ N). Ceci étant, chaque isomorphisme de codes particulier pourra être défini par la donnée d’un ensemble de relations du type { m_{i,φ} → m_{i,ψ} }_{i∈I}, à condition que { m_{i,φ} }_{i∈I} et { m_{i,ψ} }_{i∈I} soient des ^{≪} codes ^{≫} et que la correspondance soit bijective. En effet, A^{†} est implicitement défini par I, S^{†} l’est par les symboles utilisés pour noter les m_{i,φ} et m_{i,ψ}; et l’on peut interpréter les relations comme des correspondances { φa_{i} → ψa_{i} }_{i∈I}.

d. Vérification qu’un ensemble de mots donnés est un code. — Plus loin, on invoquera souvent la propriété suivante : Si C et K_{d} désignent respectivement un code et un préfix-code droit sur S^{†}, et si α est un symbole (générateur de S^{†}) ne figurant pas dans C ni dans K_{d}, alors, l’ensemble C ∪ αK_{d} est un code. De même, en remplaçant K_{d} par un préfix-code gauche K_{g}, l’ensemble C ∪ K_{g}α est un code. Rappelons que tout préfix-code droit K_{d} est par définition (^{4}) tel que, si m_{i}, m_{j} ∈ K_{d} et si, avec y ∈ S^{†}, on a m_{i} = m_{j}y, alors, y = e_{S} (tandis que pour les préfix-codes gauches, c’est m_{i} = ym_{j} qui impose y = e_{S}).

e. Épimorphismes de codes. — On parlera d’ ^{≪} épimorphisme de codes ^{≫} τ dans le cas de relations { m_{i,φ} → m_{i,ψ} }_{i∈I}, où { m_{i,φ} }_{i∈I} est bien un code C_{φ}, mais où { m_{i,ψ} }_{i∈I} est astreint seulement à ne pas contenir d’autres mots que ceux d’un code C_{ψ}.

2. Machines de Turing réversibles. — Soit une machine de Turing MT dont { ε_{p} }_{p∈P} et { σ_{q} }_{q∈Q} sont les ensembles d’états et de symboles, et { δ_{r} }_{r∈R} les déplacements de ruban, qui peuvent être ±1 ou 0. On peut définir MT par un ensemble de quintuples

χ_{MT} = { ε_{p_{1}(i)}; σ_{q_{1}(i)}; ε_{p_{2}(i)}; σ_{q_{2}(i)}; δ_{r(i)}}_{i∈I},

où les indices p_{1}, p_{2}, q_{1}, q_{2}, r sont fonctions de l’indice i. A chacun de ces quintuples, décidons d’associer un^{≪} quintuple image inverse^{≫} (ε_{p_{2}(i)}^{∗}; σ_{q_{2}(i)}; ε_{p_{1}(i)}^{∗}; σ_{q_{1}(i)}; −δ_{r(i)}). 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 ε_{p}^{∗} seront dits images des ε_{p}. La substitution d’un ε_{p}^{∗} à un ε_{p} dans une configuration instantanée U_{k} sera dite passage à U_{k} à sa configuration image U_{k}^{∗}. Les suites de configurations de MT^{∗} sont images de celles de MT, mais MT^{∗} les parcourt dans l’ordre inverse. Considérons maintenant la machine R (MT), dont l’ensemble de quintuples est

χ_{R (MT)} = χ_{MT} ∪ χ_{MT}^{∗} ∪ { (ε_{p}; σ_{q})_{stop}; ε_{p}^{∗}; σ_{q}; 0},

où (ε_{p}; σ_{q})_{stop} désigne tout couple pour lequel MT stoppe. Si l’on fait partir MT et R (MT) d’une même configuration instantanée U_{0}, 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.

3. 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 (ε_{g}, σ_{h}, ε_{j}, σ_{k}, 1), on associe trois relations, à savoir ici : { α_{g}σ_{h} → σ_{k}α_{j}; ω_{g}σ_{h} → σ_{k}α_{j}; σ_{h}β_{g} → σ_{k}α_{j} }. Aux (ε_{g}, σ_{h}, ε_{j}, σ_{k}, 0), on associe : { α_{g}σ_{h} → ω_{j}σ_{k}; ω_{g}σ_{h} → ω_{j}σ_{k}; σ_{h}β_{g} → ω_{j}σ_{k} }. Aux (ε_{g}, σ_{h}, ε_{j}, σ_{k}, −1), on associe { α_{g}σ_{h} → β_{j}σ_{k}; ω_{g}σ_{h} → β_{j}σ_{k}; σ_{h}β_{g} → β_{j}σ_{k} }. Enfin, à tout symbole σ_{q} de MT, on associe σ_{q} → σ_{q}. 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 τ_{max} celui-ci, τ_{max} 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 u_{i}, u_{i+1} on ait u_{i+1} = τ_{max}u_{i}. 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 ε_{p} de la machine, et de façon à indiquer, non seulement la position π_{1} du prochain symbole à lire, mais encore celle π_{2} du symbole précédemment écrit (acev convention particulière pour la configuration initiale). Un α_{p} signifie que π_{1} est le premier symbole à sa droite, π_{2} le premier à sa gauche. Un β_{p}, l’inverse. Un ω_{p} signifie que π_{1} et π_{2}, confondus, sont tous deux le premier symbole à droite de ce ω_{p}. On a bien alors u_{i+1} = τ_{max}u_{i}. Si certains états ε_{p} ne peuvent apparaître que sous deux seulement, ou une seule, des formes α_{p}, ω_{p}, β_{p}, et soit τ_{min} obtenu en retranchant de τ_{max} toutes les relations contenant des formes qui n’apparaissent jamais, alors, τ_{min} est encore tel que u_{i+1} = τ_{min}u_{i}. Si τ_{min} est un isomorphisme de codes, MT est réversible.

4. Simulation de MT quelconque sur MT′ réversible. Application aux isomorphismes de codes. — a. Propriété. — On peut simuler une machine de Turing MT quelconque (de configurations v_{i}) sur une machine de Turing réversible MT_{ρ} (de configurations u_{i,j}) de façon que : 1^{0} quand MT passe de v_{i} à v_{i+1}, MT_{ρ} passe de u_{i,0} à u_{i+1,0} par l’intermédiaire d’un nombre fini de configurations u_{i,1}; u_{i,2}; …; 2^{0} on passe d’un v_{i} au suivant par un épimorphisme de codes τ, d’un u_{i,j} au suivant par un isomorphisme de codes θ; 3^{0} si les configurations initiales sont v_{0} pour MT et u_{0,0} pour MT_{ρ}, avec u_{0,0} = λv_{0}μν, alors pour tout i, on a u_{i,0} = λv_{i}μw_{i}ν, où w_{i} est un mot, et où λ, μ, ν sont trois symboles qui n’apparaissent ni dans v_{i} ni dans w_{i}, si bien que u_{i,0} connu donne v_{i} et w_{i}; 4^{0} il y a des symboles r_{k} dont chacun représente une relation de τ autre que d’identité; un symbole blanc b; et pour tout i on a w_{i} = b^{2}r_{k_{1}}r_{k_{2}} … r_{k_{i}}b, où r_{k_{p}} est la relation intervenue dans v_{p} = τv_{p−1}. Ainsi, w_{i} représente l’histoire du calcul de MT jusqu’au temps i; 5^{0} MT_{ρ} stoppe sur les u_{i,0} correspondant à des stop de MT, et eux seulement; 6^{0} la machine R (MT_{ρ}), couplage de MT_{ρ} avec son image inverse, partie de u_{0 0} = λv_{0}μν passe par la configuration image λv_{0}^{∗}μν si et seulement si MT, partie de v_{0}, stoppe; 7^{0} il existe pour R (MT_{ρ}) certaines configurations instantanées u_{st} telles que, partant de λv_{0}μν, R (MT_{ρ}) ne peut atteindre ces configurations autrement qu’en passant par λv_{0}^{∗}μν (c’est-à-dire si MT, partie de v_{0}, stoppe). On peut ainsi faire en sorte que le retour de R (MT_{ρ}) à λv_{0}μν (ou bien, le passage par des u_{st} 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 { I_{k,τ} }_{k∈K_{τ}} à l’ensemble des relations { I_{j,θ} }_{j∈J_{θ}} définissant θ et MT_{ρ}. Limitonsnous à donner le principe de cette construction, en montrant comment simuler une instruction I_{k_{i},τ} de la forme α_{p}σ_{q} → σ_{f}α_{g}. A celle-ci, on associera : une instruction α_{p}σ_{q} → σ_{f,g,α} ε_{α,α,p,q,f,g,σ}, où le symbole σ_{fgα} marque la place où l’on doit modifier v_{i}, et la nature de la modification; des instructions permettant de conduire le contrôle à gauche de ν par un état ε_{ααpqfgν}; une instruction bε_{ααpqfgν} → ε_{s}r_{k_{i}}, où r_{k_{i}} représente I_{k_{i},τ}, complètant w_{i}; des instructions de service déplaçant ν et, éventuellement aussi λ, μ et w_{i} tout entier, pour rétablir les blancs nécessaires dans u_{i,0} puis reportant le contrôle en σ_{f,g,α} avec un état ε_{σ}; une instruction σ_{f,g,α} ε_{σ} → σ_{f}α_{g} qui complète v_{i} dans u_{i,0}.

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 w = θ^{n}w, où θ est un isomorphisme de codes, avec n ∈ N est récursivement insoluble en n pour w, θ donnés quelconques. L’equation w_{1} = θ^{n}w_{2}, avec w_{1} ≠ w_{2}, est aussi récursivement insoluble en n.

(^{∗}) Séance du 21 octobre 1963.

(^{1}) N. Chomsky et M. P. Schützenberger, Computer Programming and Formal Systems, Hirschberg et Braffort, North-Holland Publ. Co., Amsterdam, 1963, p. 118–161.

(^{2}) H. Wang, Mathematische Annalen, 152, 1963, p. 65–74.

(^{3}) M. Minsky, Annals of Math., 74-3, 1961.

(^{4}) M. P. Schützenberger, I. R. E. Trans. Inf. Theory, IT-2, 1956, p. 47-60.

(^{5}) E. Post, Amer. J. Math., 65, 1943, p. 196–215.

(^{6}) E. Post, Bull. Amer. Math. Soc., 52, 1946, p. 264–268.

(Euratom, 51, rue Belliard, Bruxelles.)