\documentclass[12pt]{article}
\usepackage{urls}
\oddsidemargin 0.25in
\evensidemargin 0.25in
\topmargin -0.5in
\textheight 9in
\textwidth 6in

\begin{document}
\begin{flushright}
{\parindent 0pt
\textit{Weekly Proceedings of the Academy of Science},
\mbox{257:2597--2600}, Meeting of October~28, 1963.}\\[0.2in]
\fbox{\parbox{4.25in}{\raggedleft{\small Translated from French by Michael P. Frank, January~14, 1998.
{\url http://www.ai.mit.edu/~mpf/rc/Lecerf/lecerf.html}}}}
\end{flushright}
\vskip 0.2in
\begin{list}{}{\setlength{\leftmargin}{0.75in}
	       \setlength{\rightmargin}{0.5in}
	       \setlength{\itemindent}{-0.25in}}
\item \textsc{Mathematical Logic.} --- \textit{Reversible Turing
machines.  Recursive insolubility in $n\in{\bf N}$ of the equation
$u=\theta^n u$, where $\theta$ is an ``isomorphism of codes.''} Note ($^*$)
by Mr. \textbf{Yves Lecerf}, presented by Mr. Andr\'e Lichnerowicz.
\end{list}
\vskip .20in
\begin{list}{}{\setlength{\leftmargin}{0.25in}
	       \setlength{\rightmargin}{0.25in}
	       \setlength{\itemindent}{0.25in}
	       \setlength{\baselineskip}{11pt}}
\item
{\small We define ``reversible Turing machines'' and ``isomorphisms of
codes $\theta$.''  Their properties make it possible to prove that the
equation in $n\in{\bf N}$, $u=\theta^n u$ is recursively unsolvable.  A
second note will apply this to the demonstration of a conjecture of
Sch\"utzenberger relating the Post correspondence problem to the problem of
diagonalization of homomorphisms of free monoids.}
\end{list}

1. \textsc{Isomorphisms of codes, epimorphisms of codes.} ---
\textit{a. A conjecture of Sch\"utzenberger.} --- Given two
nontrivial free monoids ${\rm A}^\dag$ and ${\rm S}^\dag$, and given two
homomorphisms $\varphi$ and $\psi$ of ${\rm A}^\dag$ into ${\rm S}^\dag$,
consider the problem of the search for nontrivial solutions $x\in{\rm
A}^\dag$ for the equation of diagonalization $\varphi x=\psi x$.  A result
of Post ($^6$) is that this equation is recursively unsolvable in the case
of $\varphi$ and $\psi$ being arbitrary homomorphisms.  It is also so when
one restricts $\varphi$ to be a monomorphism; indeed, Chomsky and
Sch\"utzenberger 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\"utzenberger conjectured that the equation $\varphi
x=\psi x$ remains recursively unsolvable when $\varphi$ and $\psi$ are both
monomorphisms.

b. \textit{Isomorphisms of codes.} --- Instead of $\varphi x=\psi x$, it is
equivalent to consider the equation $w=\theta w$, where
$\theta=\psi\varphi^{-1}$ (this is shorthand notation for saying that
$\theta$ is a bijection of $\varphi{\rm A}^\dag$ into $\psi{\rm A}^\dag$
defined by $\theta w=\psi x$ for $w=\varphi x$).  For convenience, we will
call the applications such as $\theta$ ``isomorphisms of codes.''  The term
recalls that $\theta(w_1w_2)=\theta w_1\,\theta w_2$; and also that, ${\rm
A}=\{\,a_i\,\}_{i\in{\rm I}}$ designating the alphabet (generators) of
${\rm A}^\dag$, $\{\,\varphi a_i\,\}_{i\in{\rm I}}$ and $\{\,\psi
a_i\,\}_{i\in{\rm I}}$ are called ``codes'' on ${\rm S}^\dag$, because, for
an arbitrary $y$ in ${\rm S}^\dag$, there exists a set of indices
$\{\,i_1,i_2,\ldots,i_p\,\}$ such that $y=\varphi a_{i_1}\,\varphi
a_{i_2}\,\ldots\varphi a_{i_p}$, and the same for $\psi$.  In fact, it is
especially the study of isomorphisms of codes to which will be devoted the
present Note and the following one.

c. \textit{Definitions of particular ``isomorphisms of codes'' using
relation elements.} --- With $e_{\rm A}$ and $e_{\rm S}$ designating the
identity elements respectively of ${\rm A}^\dag$ and ${\rm S}^\dag$, it
goes without saying implicitly for every $\theta$ that one has $e_{\rm
S}=\theta e_{\rm S}$, with $\varphi e_{\rm A}=\psi e_{\rm A}=e_{\rm S}$
(whenceforth a trivial solution for $w=\theta w$ and for $w=\theta^nw$,
with $n\in{\bf N}$).  This being the case, each particular isomorphism of
codes could be defined by a set of relation elements of the type
$\{\,m_{i,\varphi}\,\rightarrow\,m_{i,\psi}\,\}_{i\in{\bf I}}$, provided
that $\{\,m_{i,\varphi}\,\}_{i\in{\rm I}}$ and
$\{\,m_{i,\psi}\,\}_{i\in{\rm I}}$ are ``codes'' and that the
correspondence is bijective.  Indeed, ${\rm A}^\dag$ is implicitly defined
by ${\rm I}$, and ${\rm S}^\dag$ by the symbols used to note the
$m_{i,\varphi}$ and $m_{i,\psi}$; and one can interpret the relations as
correspondences $\{\,\varphi a_i\rightarrow\psi a_i\,\}_{i\in{\rm I}}$.

d. \textit{Checking whether a given set of words is a code.} --- Further,
the following property will be often called upon: If C and ${\rm K}_r$
designate respectively a code and a right prefix-code on ${\rm S}^\dag$,
and if $\alpha$ is a symbol (generator of $\rm S^\dag$) not appearing in C
nor in ${\rm K}_r$, then, the set ${\rm C}\cup\alpha{\rm K}_r$ is a code.
In the same way, replacing ${\rm K}_r$ by a left prefix-code ${\rm
K}_\ell$, the set ${\rm C}\cup{\rm K}_\ell\alpha$ is a code.  Let us recall
that any right prefix-code ${\rm K}_r$ is by definition ($^4$) such that,
if $m_i$, $m_j\in{\rm K}_r$ and if, with $y\in{\rm S}^\dag$, one has
$m_i=m_jy$, then $y=e_{\rm S}$ (while for the left prefix-codes, it is
$m_i=ym_j$ which imposes $y=e_{\rm S}$).

e. \textit{Epimorphisms of codes.} --- One speaks about ``epimorphisms of
codes'' $\tau$ in the case of relations $\{\,m_{i,\varphi}\rightarrow
m_{i,\psi}\,\}_{i\in{\rm I}}$, where $\{\,m_{i,\varphi}\,\}_{i\in{\rm I}}$
is a complete code ${\rm C}_\varphi$, but where
$\{\,m_{i,\psi}\,\}_{i\in{\rm I}}$ is only constrained not to contain words
other than those of a code ${\rm C}_\psi$.
\vskip 5pt

2. \textsc{Reversible Turing machines.} --- Let MT be a Turing machine of
which $\{\,\varepsilon_p\,\}_{p\in{\rm P}}$ and $\{\,\sigma_q\,\}_{q\in Q}$
are the sets of states and symbols, and $\{\,\delta_r\,\}_{r\in R}$ are
tape displacements, which can be $\pm1$ or 0.  One can define MT by a set
of quintuples
\[
\chi_{\rm MT}=\{\,\varepsilon_{p_1(i)}; \sigma_{q_1(i)};
\varepsilon_{p_2(i)}; \sigma_{q_2(i)}; \delta_{r(i)}\}_{i\in{\rm 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'' ($\varepsilon^*_{p_2(i)}$; $\sigma_{q_2(i)}$;
$\varepsilon^*_{p_1(i)}$; $\sigma_{q_1(i)}$; $-\delta_{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 ${\rm MT}^*$ of MT.  The $\varepsilon^*_p$ will be known as the
images of $\varepsilon_p$.  The substituion of $\varepsilon^*_p$ for
$\varepsilon_p$ in an instantaneous configuration ${\rm U}_k$ will be known
as transformation of ${\rm U}_k$ to its image configuration ${\rm U}^*_k$.
The continuations of configurations of ${\rm MT}^*$ are images of those of
MT, but ${\rm MT}^*$ traverses them in the opposite order.  Now let us
consider the machine R\,(MT), whose set of quintuples is
\[
\chi_{\rm R\,(MT)}=\chi_{\rm MT}\cup\chi^*_{\rm
MT}\cup\{\,(\varepsilon_p;\sigma_q)_{\rm halt}; \varepsilon^*_p; \sigma_q; 0\},
\]
where $(\varepsilon_p; \sigma_q)_{\rm halt}$ designates any state-symbol
pair for which MT halts.  If one starts MT and R\,(MT) from the same
instantaneous configuration ${\rm 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.
\vskip 5pt

3. \textsc{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
$(\varepsilon_g,\sigma_h,\varepsilon_j,\sigma_k,{1})$, we associate three
relation elements, namely:
$\{\,\alpha_g\sigma_h\rightarrow\sigma_k\alpha_j;\,\omega_g\sigma_h\rightarrow\sigma_k\alpha_j;\,\sigma_h\beta_g\rightarrow\sigma_k\alpha_j\,\}$.
With $(\varepsilon_g,\sigma_h,\varepsilon_j,\sigma_k,0)$, we associate:
$\{\,\alpha_g\sigma_h\rightarrow\omega_j\sigma_k;\,\omega_g\sigma_h\rightarrow\omega_j\sigma_k;\,\sigma_h\beta_g\rightarrow\omega_j\sigma_k\,\}$.
With $(\varepsilon_g,\sigma_h,\varepsilon_j,\sigma_k,-{1})$, we associate
$\{\,\alpha_g\sigma_h\rightarrow\beta_j\sigma_k;\,\omega_g\sigma_h\rightarrow\beta_j\sigma_k;\,\sigma_h\beta_g\rightarrow\beta_j\sigma_k\,\}$.
Finally, with any symbol $\sigma_q$ of MT, we associate
$\sigma_q\rightarrow\sigma_q$.  One can check, by the process given in
paragraph 1\textit{d}, that the set of these relations defines an
epimorphism of codes.  With $\tau_{\rm max}$ being this set, $\tau_{\rm
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}=\tau_{\rm max}u_i$.  For
that, a configuration will be composed of a succession of symbols $\sigma$
(the string on the tape) into which one will intercalate one of the letters
$\alpha$, $\omega$ or $\beta$, with an index $p$ equal to that of the state
$\varepsilon_p$ of the machine, and indicating, not only the position
$\pi_1$ of the next symbol to read, but also the position $\pi_2$ of the
symbol previously written (with a particular convention for the initial
configuration).  An $\alpha_p$ signifies that $\pi_1$ is the first symbol
to its right, $\pi_2$ the first on its left.  A $\beta_p$, vice-versa.  An
$\omega_p$ means that $\pi_1$ and $\pi_2$ are both the first symbol to the
right of the $\omega_p$.  We have then achieved that
$u_{i+1}=\tau_{max}u_i$.  So certain states $\varepsilon_p$ can appear
under only two or one of the forms $\alpha_p$, $\omega_p$, $\beta_p$, and
$\tau_{\rm min}$ is obtained by removing from $\tau_{\rm max}$ all the
relation elements containing the forms which never appear, so $\tau_{\rm
min}$ is still such that $u_{i+1}=\tau_{\rm min}u_i$.  If $\tau_{\rm min}$
is an isomorphism of codes, MT is reversible.
\vskip 5pt

4. \textsc{Simulation of arbitrary MT on reversible ${\rm MT}'$.
Application to isomorphisms of codes.} --- \textit{a. Properties.} ---
One can simulate an arbitrary Turing machine MT (with configurations $v_i$)
on a reversible Turing machine ${\rm MT}_\rho$ (with configurations
$u_{i,j}$) so that: (1) when MT passes from $v_i$ to $v_{i+1}$, ${\rm
MT}_\rho$ 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}; \ldots$; (2) we pass
from one $v_i$ to the next via an epimorphism of codes $\tau$, and from one
$u_{i,j}$ to the next via an isomorphism of codes $\theta$; (3) if the
initial configurations are $v_0$ for MT and $u_{0,0}$ for ${\rm MT}_\rho$,
with $u_{0,0}=\lambda v_0\mu\nu$, then for any $i$, one has $u_{i,0} =
\lambda v_i\mu w_i\nu$, where $w_i$ is a string, and where $\lambda$, $\mu$,
$\nu$ 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 $\tau$ other than that of
identity; a blank symbol $b$; and for any $i$ we have
$w_i=b^2r_{k_1}r_{k_2}\ldots r_{k_i}b$, where $r_{k_p}$ is the relation
invoked by $v_p=\tau v_{p-1}$.  Thus, $w_i$ represents the history of the
computation of MT until time $i$; (5) ${\rm MT}_\rho$ halts on the
$u_{i,0}$ corresponding to the halting of MT, and them only; (6) the
machine ${\rm R}\,({\rm MT}_\rho)$, coupling ${\rm MT}_\rho$ with its
reverse image, starting from $u_{0,0}=\lambda v_0\mu\nu$ passes through the
image configuration $\lambda v^*_0\mu\nu$ if and only if MT, starting from
$v_0$, halts; (7) there exists for R\,(${\rm MT}_\rho$) certain
instantaneous configurations $u_{s,t}$ such that, when started at $\lambda
v_0\mu\nu$, R\,(${\rm MT}_\rho$) cannot reach those configurations other
than by passing through $\lambda v^*_0\mu\nu$ (\textit{i.e.}, if MT,
starting from $v_0$, halts).  One can thus arrange that the return of of
R\,(${\rm MT}_\rho$) to $\lambda v_0\mu\nu$ (or the passage through
$u_{st}$ framed by $\lambda'\nu'$ instead of $\lambda\nu$) is conditional
on the halting of MT.

\textit{Proof.} --- It is shown how to proceed from $\tau$, presumed to be
given by a set of relation elements $\{\,{\rm I}_{k,\tau}\,\}_{k\in{\rm
K}_\tau}$ to the set of relation elements $\{\,{\rm
I}_{j,\theta}\,\}_{j\in{\rm J}_\theta}$ defining $\theta$ and ${\rm
MT}_\rho$.  We delimit the principles of this construction, by showing how
to simulate an ${\rm I}_{k_i,\tau}$ of the form
$\alpha_p\sigma_q\rightarrow\sigma_f\alpha_g$.  With this, we associate: an
instruction
$\alpha_p\sigma_q\rightarrow\sigma_{f,g,\alpha}\,\varepsilon_{\alpha,\alpha,p,q,f,g,\sigma}$,
where the symbol $\sigma_{fg\alpha}$ 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 $\nu$ through a state $\varepsilon_{\alpha\alpha
pqfg\nu}$; an instruction $b\varepsilon_{\alpha\alpha
pqfg\nu}\rightarrow\varepsilon_sr_{k_i}$, where $r_{k_i}$ represents
$I_{k_i,\tau}$, supplementing $w_i$; working instructions moving $\nu$ and
possibly also $\lambda$, $\mu$ and the entire $w_i$, to restore the
necessary blanks in $u_{i,0}$ and then defer control in
$\sigma_{f,g,\alpha}$ with a state $\varepsilon_\sigma$; an instruction
$\sigma_{f,g,\alpha}\,\varepsilon_\sigma\rightarrow\sigma_f\alpha_g$ which
supplements $v_i$ in $u_{i,0}$.

\textit{b.} \textsc{Theorem 1.} --- \textit{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.}

\textit{c.} \textsc{Theorem 2.} --- \textit{The equation $w=\theta^n
w$, where $\theta$ is an isomorphism of codes, with $n\in{\bf N}$ is
recursively unsolvable in $n$ given arbitrary $w$, $\theta$.  The equation
$w_1 = \theta^nw_2$, with $w_1\neq w_2$, is also recursively unsolvable in
$n$.}
\vskip 0.25in

{\small
($^*$) Meeting of October 21, 1963.

($^1$) \textsc{N. Chomsky} et \textsc{M. P. Sch\"utzenberger},
\textit{Computer Programming and Formal Systems}, Hirschberg and Braffort,
North-Holland Publ.\ Co., Amsterdam, {1963}, \mbox{p.~118--161}.

($^2$) \textsc{H. Wang}, \textit{Mathematische Annalen}, \textbf{152},
{1963}, p.~{65--74}.

($^3$) \textsc{M. Minsky}, \textit{Annals of Math.}, \textbf{74-3}, {1961}.

($^4$) \textsc{M. P. Sch\"utzenberger},
\textit{I. R. E. Trans.\ Inf.\ Theory}, IT-2, {1956, p.~47-60}.

($^5$) \textsc{E. Post}, \textit{Amer.\ J. Math.}, \textbf{65}, {1943},
p.~{196--215}.

($^6$) \textsc{E. Post}, \textit{Bull.\ Amer. Math. Soc.}, \textbf{52}, {
1946, p.~264--268}.
\vskip 5pt
\begin{flushright}
(\textit{Euratom, 51, rue Belliard, Bruxelles.})
\end{flushright}
}

\end{document}
