Weekly Proceedings of the Academy of Science, 257:2597–2600, Meeting of October 28, 1963.

Translated from French by Michael P. Frank, January 14, 1998.

                           http://www.ai.mit.edu/~mpf/rc/Lecerf/lecerf.html

Mathematical Logic. — Reversible Turing machines. Recursive insolubility in n ∈ N of the equation u = θ^{n}u, where θ is an “isomorphism of codes.” Note (^{∗}) by Mr. Yves Lecerf, presented by Mr. André Lichnerowicz.

We define “reversible Turing machines” and “isomorphisms of codes θ.” Their properties make it possible to prove that the equation in n ∈ N, u = θ^{n}u is recursively unsolvable. A second note will apply this to the demonstration of a conjecture of Schützenberger relating the Post correspondence problem to the problem of diagonalization of homomorphisms of free monoids.

1. Isomorphisms of codes, epimorphisms of codes. — a. A conjecture of Schützenberger. — Given two nontrivial free monoids A^{†} and S^{†}, and given two homomorphisms φ and ψ of A^{†} into S^{†}, consider the problem of the search for nontrivial solutions x ∈ A^{†} for the equation of diagonalization φx = ψx. A result of Post (^{6}) is that this equation is recursively unsolvable in the case of φ and ψ being arbitrary homomorphisms. It is also so when one restricts φ to be a monomorphism; indeed, Chomsky and Schützenberger remarked (^{1}) that this case can be reduced to Post’s Tag-problem (^{5}), itself recursively unsolvable according to a result of Minsky (^{3}). Schützenberger conjectured that the equation φx = ψx remains recursively unsolvable when φ and ψ are both monomorphisms.

b. Isomorphisms of codes. — Instead of φx = ψx, it is equivalent to consider the equation w = θw, where θ = ψφ^{−1} (this is shorthand notation for saying that θ is a bijection of φA^{†} into ψA^{†} defined by θw = ψx for w = φx). For convenience, we will call the applications such as θ “isomorphisms of codes.” The term recalls that θ(w_{1}w_{2}) = θw_{1} θw_{2}; and also that, A = { a_{i} }_{i∈I} designating the alphabet (generators) of A^{†}, { φa_{i} }_{i∈I} and { ψa_{i} }_{i∈I} are called “codes” on S^{†}, because, for an arbitrary y in S^{†}, there exists a set of indices { i_{1}, i_{2}, …, i_{p} } such that y = φa_{i_{1}} φa_{i_{2}} … φa_{i_{p}}, and the same for ψ. In fact, it is especially the study of isomorphisms of codes to which will be devoted the present Note and the following one.

c. Definitions of particular “isomorphisms of codes” using relation elements. — With e_{A} and e_{S} designating the identity elements respectively of A^{†} and S^{†}, it goes without saying implicitly for every θ that one has e_{S} = θe_{S}, with φe_{A} = ψe_{A} = e_{S} (whenceforth a trivial solution for w = θw and for w = θ^{n}w, with n ∈ N). This being the case, each particular isomorphism of codes could be defined by a set of relation elements of the type { m_{i,φ} → m_{i,ψ} }_{i∈I}, provided that { m_{i,φ} }_{i∈I} and { m_{i,ψ} }_{i∈I} are “codes” and that the correspondence is bijective. Indeed, A^{†} is implicitly defined by I, and S^{†} by the symbols used to note the m_{i,φ} and m_{i,ψ}; and one can interpret the relations as correspondences { φa_{i} → ψa_{i} }_{i∈I}.

d. Checking whether a given set of words is a code. — Further, the following property will be often called upon: If C and K_{r} designate respectively a code and a right prefix-code on S^{†}, and if α is a symbol (generator of S^{†}) not appearing in C nor in K_{r}, then, the set C ∪ αK_{r} is a code. In the same way, replacing K_{r} by a left prefix-code K_{ℓ}, the set C ∪ K_{ℓ}α is a code. Let us recall that any right prefix-code K_{r} is by definition (^{4}) such that, if m_{i}, m_{j} ∈ K_{r} and if, with y ∈ S^{†}, one has m_{i} = m_{j}y, then y = e_{S} (while for the left prefix-codes, it is m_{i} = ym_{j} which imposes y = e_{S}).

e. Epimorphisms of codes. — One speaks about “epimorphisms of codes” τ in the case of relations { m_{i,φ} → m_{i,ψ} }_{i∈I}, where { m_{i,φ} }_{i∈I} is a complete code C_{φ}, but where { m_{i,ψ} }_{i∈I} is only constrained not to contain words other than those of a code C_{ψ}.

2. Reversible Turing machines. — Let MT be a Turing machine of which { ε_{p} }_{p∈P} and { σ_{q} }_{q∈Q} are the sets of states and symbols, and { δ_{r} }_{r∈R} are tape displacements, which can be ±1 or 0. One can define MT by a set of quintuples

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

where the indices p_{1}, p_{2}, q_{1}, q_{2}, r are functions of index i. With each of the quintuples, let us decide to associate an “inverse image quintuple” (ε_{p_{2}(i)}^{∗}; σ_{q_{2}(i)}; ε_{p_{1}(i)}^{∗}; σ_{q_{1}(i)}; −δ_{r(i)}). The set of those will generally not constitute a Turing machine; but when it does, we will say that MT is “reversible,” and call the new machine the inverse image MT^{∗} of MT. The ε_{p}^{∗} will be known as the images of ε_{p}. The substituion of ε_{p}^{∗} for ε_{p} in an instantaneous configuration U_{k} will be known as transformation of U_{k} to its image configuration U_{k}^{∗}. The continuations of configurations of MT^{∗} are images of those of MT, but MT^{∗} traverses them in the opposite order. Now let us consider the machine R (MT), whose set of quintuples is

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

where (ε_{p}; σ_{q})_{halt} designates any state-symbol pair for which MT halts. If one starts MT and R (MT) from the same instantaneous configuration U_{0}, they pass through the same configurations as long as MT does not halt (thus possibly indefinitely). When MT halts, R (MT) continues, traversing in the opposite order the image configurations of the traversed configurations, and passes by the image of the initial configuration. R (MT) will be known as the coupling of MT with its reverse image.

3. Representation of Turing machines by epimorphisms (or isomorphismes) of codes. — Let us be given an arbitrary MT. With each quintuple having movement +1, that is to say for example (ε_{g}, σ_{h}, ε_{j}, σ_{k}, 1), we associate three relation elements, namely: { α_{g}σ_{h} → σ_{k}α_{j}; ω_{g}σ_{h} → σ_{k}α_{j}; σ_{h}β_{g} → σ_{k}α_{j} }. With (ε_{g}, σ_{h}, ε_{j}, σ_{k}, 0), we associate: { α_{g}σ_{h} → ω_{j}σ_{k}; ω_{g}σ_{h} → ω_{j}σ_{k}; σ_{h}β_{g} → ω_{j}σ_{k} }. With (ε_{g}, σ_{h}, ε_{j}, σ_{k}, −1), we associate { α_{g}σ_{h} → β_{j}σ_{k}; ω_{g}σ_{h} → β_{j}σ_{k}; σ_{h}β_{g} → β_{j}σ_{k} }. Finally, with any symbol σ_{q} of MT, we associate σ_{q} → σ_{q}. One can check, by the process given in paragraph 1d, that the set of these relations defines an epimorphism of codes. With τ_{max} being this set, τ_{max} is a representation of MT, because it defines its alphabet and quintuples. We can, in addition, find, for the instantaneous configurations of MT, notations such that for any pair of successive configurations u_{i}, u_{i+1} we have u_{i+1} = τ_{max}u_{i}. For that, a configuration will be composed of a succession of symbols σ (the string on the tape) into which one will intercalate one of the letters α, ω or β, with an index p equal to that of the state ε_{p} of the machine, and indicating, not only the position π_{1} of the next symbol to read, but also the position π_{2} of the symbol previously written (with a particular convention for the initial configuration). An α_{p} signifies that π_{1} is the first symbol to its right, π_{2} the first on its left. A β_{p}, vice-versa. An ω_{p} means that π_{1} and π_{2} are both the first symbol to the right of the ω_{p}. We have then achieved that u_{i+1} = τ_{max}u_{i}. So certain states ε_{p} can appear under only two or one of the forms α_{p}, ω_{p}, β_{p}, and τ_{min} is obtained by removing from τ_{max} all the relation elements containing the forms which never appear, so τ_{min} is still such that u_{i+1} = τ_{min}u_{i}. If τ_{min} is an isomorphism of codes, MT is reversible.

4. Simulation of arbitrary MT on reversible MT′. Application to isomorphisms of codes. — a. Properties. — One can simulate an arbitrary Turing machine MT (with configurations v_{i}) on a reversible Turing machine MT_{ρ} (with configurations u_{i,j}) so that: (1) when MT passes from v_{i} to v_{i+1}, MT_{ρ} passes from u_{i,0} to u_{i+1,0} via the intermediary of a finite number of configurations u_{i,1}; u_{i,2}; …;

(2) we pass from one v_{i} to the next via an epimorphism of codes τ, and from one u_{i,j} to the next via an isomorphism of codes θ; (3) if the initial configurations are v_{0} for MT and u_{0,0} for MT_{ρ}, with u_{0,0} = λv_{0}μν, then for any i, one has u_{i,0} = λv_{i}μw_{i}ν, where w_{i} is a string, and where λ, μ, ν are three symbols which appear neither in v_{i} nor in w_{i}, so that knowing u_{i,0} gives v_{i} and w_{i}; (4) there are symbols r_{k} of which each one represents a relation element of τ other than that of identity; a blank symbol b; and for any i we have w_{i} = b^{2}r_{k_{1}}r_{k_{2}} … r_{k_{i}}b, where r_{k_{p}} is the relation invoked by v_{p} = τv_{p−1}. Thus, w_{i} represents the history of the computation of MT until time i;

(5) MT_{ρ} halts on the u_{i,0} corresponding to the halting of MT, and them only; (6) the machine R (MT_{ρ}), coupling MT_{ρ} with its reverse image, starting from u_{0,0} = λv_{0}μν passes through the image configuration λv_{0}^{∗}μν if and only if MT, starting from v_{0}, halts; (7) there exists for R (MT_{ρ}) certain instantaneous configurations u_{s,t} such that, when started at λv_{0}μν, R (MT_{ρ}) cannot reach those configurations other than by passing through λv_{0}^{∗}μν (i.e., if MT, starting from v_{0}, halts). One can thus arrange that the return of of R (MT_{ρ}) to λv_{0}μν (or the passage through u_{st} framed by λ′ν′ instead of λν) is conditional on the halting of MT.

Proof. — It is shown how to proceed from τ, presumed to be given by a set of relation elements { I_{k,τ} }_{k∈K_{τ}} to the set of relation elements { I_{j,θ} }_{j∈J_{θ}} defining θ and MT_{ρ}. We delimit the principles of this construction, by showing how to simulate an I_{k_{i},τ} of the form α_{p}σ_{q} → σ_{f}α_{g}. With this, we associate: an instruction α_{p}σ_{q} → σ_{f,g,α} ε_{α,α,p,q,f,g,σ}, where the symbol σ_{fgα} marks the place where one must modify v_{i}, and the nature of the modification; instructions allowing control to be lead to the left from ν through a state ε_{ααpqfgν}; an instruction bε_{ααpqfgν} → ε_{s}r_{k_{i}}, where r_{k_{i}} represents I_{k_{i},τ}, supplementing w_{i}; working instructions moving ν and possibly also λ, μ and the entire w_{i}, to restore the necessary blanks in u_{i,0} and then defer control in σ_{f,g,α} with a state ε_{σ}; an instruction σ_{f,g,α} ε_{σ} → σ_{f}α_{g} which supplements v_{i} in u_{i,0}.

b. Theorem 1. — The halting problem for a general reversible Turing machine is undecidable. Similarly for the problem of returning to the initial configuration, and that of the passage through a given configuration other than the initial configuration.

c. Theorem 2. — The equation w = θ^{n}w, where θ is an isomorphism of codes, with n ∈ N is recursively unsolvable in n given arbitrary w, θ. The equation w_{1} = θ^{n}w_{2}, with w_{1} ≠ w_{2}, is also recursively unsolvable in n.

(^{∗}) Meeting of October 21, 1963. (^{1}) N. Chomsky et M. P. Schützenberger, Computer Programming and Formal

Systems, Hirschberg and 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.)