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

\begin{document}
\begin{flushright}
{\parindent 0pt
\textit{Comptes Rendus Hebdomadaires des S\'eances de L'acad\'emie des
Sciences},
\mbox{257:2597--2600}, S\'eance du 28 Octobre 1963.}
\end{flushright}
\vskip 0.75in
\begin{list}{}{\setlength{\leftmargin}{0.75in}
	       \setlength{\rightmargin}{0.5in}
	       \setlength{\itemindent}{-0.25in}}
\item \textsc{Logique Math\'ematique.} --- \textit{Machines de Turing
r\'eversibles.\\ R\'ecursive insolubilit\'e en $n\in{\bf N}$ de
l'\'equation $u=\theta^n u$, o\`u $\theta$ est un {\flqq} isomorphisme de
codes {\frqq}.} Note ($^*$) de M. \textbf{Yves Lecerf}, pr\'esent\'ee par
M. 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 On d\'efinit des {\flqq} machines de Turing r\'eversibles {\frqq} et
des {\flqq} isomorphismes de codes $\theta$ {\frqq}.  Leurs propri\'et\'es
permettent de prouver que l'equation en $n\in{\bf N}$, $u=\theta^n u$ est
r\'ecursivement insoluble.  Une second Note appliquera ceci \`a la
d\'emonstration d'une conjecture de Sch\"utzenberger rattachant le
probl\`eme des correspondances de Post \`a des probl\`emes de
diagonalisation d'homomorphismes de mono\"ides libres.}
\end{list}

1. \textsc{Isomorphismes de codes, \'epimorphismes de codes.} ---
\textit{a. Une conjecture de Sch\"utzenberger.} --- Soient deux mono\"ides
libres non triviaux ${\rm A}^\dag$ et ${\rm S}^\dag$, soient deux
homomorphismes $\varphi$ et $\psi$ de ${\rm A}^\dag$ dans ${\rm S}^\dag$, et
soit le probl\`eme de la recherche de solutions non triviales $x\in{\rm
A}^\dag$ pour l'\'equation de diagonalisation $\varphi x=\psi x$.  Un
r\'esultat de Post ($^6$) est que cette \'equation est r\'ecursivement
insoluble dans le cas de $\varphi$ et $\psi$ homomorphismes quelconques.  Elle
l'est \'egalement lorsqu'on astreint $\varphi$ \`a \^etre un monomorphisme;
Chomsky et Sch\"utzenberger ont fait observer, en effet ($^1$), que ce cas
peut se ramener au Tag-problem de Post ($^5$) lui-m\^eme r\'ecursivement
insoluble d'apr\`es un r\'esultat de Minsky ($^3$).  Sch\"utzenberger a
conjectur\'e que l'\'equation $\varphi x=\psi x$ reste encore r\'ecursivement
insoluble quand \`a la fois $\varphi$ et $\psi$ sont deux monomorphismes.

b. \textit{Isomorphismes de codes.} --- Au lieu de $\varphi x=\psi x$, il
revient au m\^eme de consid\'erer l'\'equation $w=\theta w$, o\`u
$\theta=\psi\varphi^{-1}$ (ce qui est une notation abr\'eg\'ee pour dire
que $\theta$ est une bijection de $\varphi{\rm A}^\dag$ dans $\psi{\rm
A}^\dag$ d\'efinie par $\theta w=\psi x$ pour $w=\varphi x$).  Par
facilit\'e de langage, on appellera {\flqq} isomorphismes de codes {\frqq}
les applications telles que $\theta$.  Ce terme rappelle que
$\theta(w_1w_2)=\theta w_1\,\theta w_2$; et aussi que, ${\rm
A}=\{\,a_i\,\}_{i\in{\rm I}}$ d\'esignant l'alphabet (les g\'en\'erateurs)
de ${\rm A}^\dag$, $\{\,\varphi a_i\,\}_{i\in{\rm I}}$ et $\{\,\psi
a_i\,\}_{i\in{\rm I}}$ sont appel\'es des {\flqq} codes {\frqq} sur ${\rm
S}^\dag$, car, pour $y$ quelconque de ${\rm S}^\dag$, il existe au plus un
ensemble d'indices $\{\,i_1,i_2,\ldots,i_p\,\}$ tels que $y=\varphi
a_{i_1}\,\varphi a_{i_2}\,\ldots\varphi a_{i_p}$, et de m\^eme pour $\psi$.
En fait, c'est surtout \`a l'\'etude des isomorphismes de code que seront
consacr\'ees la pr\'esente Note et la suivante.

c. \textit{D\'efinitions d' {\flqq} isomorphismes de codes {\frqq}
particuliers par donn\'ee de relations.} --- $e_{\rm A}$ et $e_{\rm S}$
d\'esignant les \'el\'ements neutres respectivement de ${\rm A}^\dag$ et de
${\rm S}^\dag$, il va de soi implicitement pour tout $\theta$ que l'on a
$e_{\rm S}=\theta e_{\rm S}$, avec $\varphi e_{\rm A}=\psi e_{\rm A}=e_{\rm
S}$ (d'o\`u, d'ailleurs, une solution triviale pour $w=\theta w$ et pour
$w=\theta^nw$, avec $n\in{\bf N}$).  Ceci \'etant, chaque isomorphisme de
codes particulier pourra \^etre d\'efini par la donn\'ee d'un ensemble de
relations du type $\{\,m_{i,\varphi}\,\rightarrow\,m_{i,\psi}\,\}_{i\in{\bf
I}}$, \`a condition que $\{\,m_{i,\varphi}\,\}_{i\in{\rm I}}$ et
$\{\,m_{i,\psi}\,\}_{i\in{\rm I}}$ soient des \mbox{{\flqq} codes {\frqq}}
et que la correspondance soit bijective.  En effet, ${\rm A}^\dag$ est
implicitement d\'efini par ${\rm I}$, ${\rm S}^\dag$ l'est par les symboles
utilis\'es pour noter les $m_{i,\varphi}$ et $m_{i,\psi}$; et l'on peut
interpr\'eter les relations comme des correspondances $\{\,\varphi
a_i\rightarrow\psi a_i\,\}_{i\in{\rm I}}$.

d. \textit{V\'erification qu'un ensemble de mots donn\'es est un code.} ---
Plus loin, on invoquera souvent la propri\'et\'e suivante : Si ${\rm C}$ et
${\rm K}_d$ d\'esignent respectivement un code et un pr\'efix-code droit
sur ${\rm S}^\dag$, et si $\alpha$ est un symbole (g\'en\'erateur de $\rm
S^\dag$) ne figurant pas dans ${\rm C}$ ni dans ${\rm K}_d$, alors,
l'ensemble ${\rm C}\cup\alpha{\rm K}_d$ est un code.  De m\^eme, en
rempla\c cant ${\rm K}_d$ par un pr\'efix-code gauche ${\rm K}_g$,
l'ensemble ${\rm C}\cup{\rm K}_g\alpha$ est un code.  Rappelons que tout
pr\'efix-code droit ${\rm K}_d$ est par d\'efinition ($^4$) tel que, si
$m_i$, $m_j\in{\rm K}_d$ et si, avec $y\in{\rm S}^\dag$, on a $m_i=m_jy$,
alors, $y=e_{\rm S}$ (tandis que pour les pr\'efix-codes gauches, c'est
$m_i=ym_j$ qui impose $y=e_{\rm S}$).

e. \textit{\'Epimorphismes de codes.} --- On parlera d' {\flqq}
\'epimorphisme de codes {\frqq} $\tau$ dans le cas de relations
$\{\,m_{i,\varphi}\rightarrow m_{i,\psi}\,\}_{i\in{\rm I}}$, o\`u
$\{\,m_{i,\varphi}\,\}_{i\in{\rm I}}$ est bien un code ${\rm C}_\varphi$, mais
o\`u $\{\,m_{i,\psi}\,\}_{i\in{\rm I}}$ est astreint seulement \`a ne pas
contenir d'autres mots que ceux d'un code ${\rm C}_\psi$.
\vskip 5pt

2. \textsc{Machines de Turing r\'eversibles.} --- Soit une machine de
Turing MT dont $\{\,\varepsilon_p\,\}_{p\in{\rm P}}$ et
$\{\,\sigma_q\,\}_{q\in Q}$ sont les ensembles d'\'etats et de symboles, et
$\{\,\delta_r\,\}_{r\in R}$ les d\'eplacements de ruban, qui peuvent \^etre
$\pm1$ ou {0}.  On peut d\'efinir MT par un
ensemble de 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}},
\]
o\`u les indices $p_1, p_2, q_1, q_2, r$ sont fonctions de l'indice $i$.  A
chacun de ces quintuples, d\'ecidons d'associer un {\flqq} quintuple image
inverse {\frqq} ($\varepsilon^*_{p_2(i)}$; $\sigma_{q_2(i)}$;
$\varepsilon^*_{p_1(i)}$; $\sigma_{q_1(i)}$; $-\delta_{r(i)}$).  L'ensemble
de ceux-ci ne constituera g\'en\'eralement pas une machine de Turing; mais
lorsqu'il en sera ainsi, on dira que MT est {\flqq} r\'eversible {\frqq},
et l'on donnera \`a la nouvelle machine le nom d'image inverse MT$^*$ de
MT.  Les $\varepsilon^*_p$ seront dits images des $\varepsilon_p$.  La
substitution d'un $\varepsilon^*_p$ \`a un $\varepsilon_p$ dans une
configuration instantan\'ee ${\rm U}_k$ sera dite passage \`a ${\rm U}_k$
\`a sa configuration image ${\rm U}^*_k$.  Les suites de configurations de
${\rm MT}^*$ sont images de celles de MT, mais ${\rm MT}^*$ les parcourt
dans l'ordre inverse.  Consid\'erons maintenant la machine R (MT), dont
l'ensemble de quintuples est
\[
\chi_{\rm R\,(MT)}=\chi_{\rm MT}\cup\chi^*_{\rm
MT}\cup\{\,(\varepsilon_p;\sigma_q)_{\rm stop}; \varepsilon^*_p; \sigma_q; 0\},
\]
o\`u $(\varepsilon_p; \sigma_q)_{\rm stop}$ d\'esigne tout couple pour
lequel MT stoppe.  Si l'on fait partir MT et R\,(MT) d'une m\^eme
configuration instantan\'ee ${\rm U}_0$, elles passent par les m\^emes
configurations tant que MT ne stoppe pas (donc \'eventuellement
ind\'efiniment).  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.
\vskip 5pt

3. \textsc{Repr\'esentation de machines de Turing par des \'epimorphismes
(ou des isomorphismes) de codes.} --- Revenons au cas o\`u MT est
quelconque.  A chacun de ses quintuples comportant le mouvement $+1$, soit
par exemple $(\varepsilon_g,\sigma_h,\varepsilon_j,\sigma_k,{1})$, on
associe trois relations, \`a savoir ici :
$\{\,\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\,\}$.
Aux $(\varepsilon_g,\sigma_h,\varepsilon_j,\sigma_k,{0})$, on associe :
$\{\,\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\,\}$.
Aux $(\varepsilon_g,\sigma_h,\varepsilon_j,\sigma_k,-{1})$, on associe
$\{\,\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\,\}$.
Enfin, \`a tout symbole $\sigma_q$ de MT, on associe
$\sigma_q\rightarrow\sigma_q$.  On peut v\'erifier, par le proc\'ed\'e
donn\'e au paragraphe 1, $d$, que l'ensemble de toutes ces relations
d\'efinit un \'epimorphisme de codes.  Soit $\tau_{\rm max}$ celui-ci,
$\tau_{\rm max}$ est une repr\'esentation de MT, car il en d\'efinit
l'alphabet et les quintuples.  On peut, d'autre part, trouver pour les
configurations instantan\'ees de MT des notations telles que pour tout
couple de configurations successives $u_i,u_{i+1}$ on ait
$u_{i+1}=\tau_{\rm max}u_i$.  Pour cela, une configuration se composera
d'une suite de symboles $\sigma$ (le mot du ruban) dans laquelle on
intercalera une des lettres $\alpha, \omega$ ou $\beta$, avec un indice $p$
\'egal \`a celui de l'\'etat $\varepsilon_p$ de la machine, et de fa\c con
\`a indiquer, non seulement la position $\pi_1$ du prochain symbole \`a
lire, mais encore celle $\pi_2$ du symbole pr\'ec\'edemment \'ecrit (acev
convention particuli\`ere pour la configuration initiale).  Un $\alpha_p$
signifie que $\pi_1$ est le premier symbole \`a sa droite, $\pi_2$ le
premier \`a sa gauche.  Un $\beta_p$, l'inverse.  Un $\omega_p$ signifie
que $\pi_1$ et $\pi_2$, confondus, sont tous deux le premier symbole \`a
droite de ce $\omega_p$.  On a bien alors $u_{i+1}=\tau_{max}u_i$.  Si
certains \'etats $\varepsilon_p$ ne peuvent appara\^itre que sous deux
seulement, ou une seule, des formes $\alpha_p,\omega_p,\beta_p$, et soit
$\tau_{\rm min}$ obtenu en retranchant de $\tau_{\rm max}$ toutes les
relations contenant des formes qui n'apparaissent jamais, alors, $\tau_{\rm
min}$ est encore tel que $u_{i+1}=\tau_{\rm min}u_i$.  Si $\tau_{\rm min}$
est un isomorphisme de codes, MT est r\'eversible.
\vskip 5pt

4. \textsc{Simulation de MT quelconque sur ${\rm MT}'$ r\'eversible.
Application aux isomorphismes de codes.} --- \textit{a. Propri\'et\'e.} ---
On peut simuler une machine de Turing MT quelconque (de configurations
$v_i$) sur une machine de Turing r\'eversible ${\rm MT}_\rho$ (de
configurations $u_{i,j}$) de fa\c con que : ${ 1^0}$ quand MT passe de $v_i$
\`a $v_{i+1}$, ${\rm MT}_\rho$ passe de $u_{i,0}$ \`a $u_{i+1,0}$ par
l'interm\'ediaire d'un nombre fini de configurations $u_{i,1}; u_{i,2};
\ldots$; ${2^0}$ on passe d'un $v_i$ au suivant par un \'epimorphisme de 
codes $\tau$, d'un $u_{i,j}$ au suivant par un isomorphisme de codes
$\theta$; ${3^0}$ si les configurations initiales sont $v_0$ pour MT et
$u_{0,0}$ pour ${\rm MT}_\rho$, avec $u_{0,0}=\lambda v_0\mu\nu$, alors
pour tout $i$, on a $u_{i,0} = \lambda v_i\mu w_i\nu$, o\`u $w_i$ est un
mot, et o\`u $\lambda,\mu,\nu$ 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\'esente une relation de
$\tau$ autre que d'identit\'e; un symbole blanc $b$; et pour tout $i$ on a
$w_i=b^2r_{k_1}r_{k_2}\ldots r_{k_i}b$, o\`u $r_{k_p}$ est la relation
intervenue dans $v_p=\tau v_{p-1}$.  Ainsi, $w_i$ repr\'esente l'histoire
du calcul de MT jusqu'au temps $i$; ${5^0}$ ${\rm MT}_\rho$ stoppe sur les
$u_{i,0}$ correspondant \`a des stop de MT, et eux seulement; ${6^0}$ la
machine ${\rm R}\,({\rm MT}_\rho)$, couplage de ${\rm MT}_\rho$ avec son
image inverse, partie de $u_{0\,0}=\lambda v_0\mu\nu$ passe par la
configuration image $\lambda v^*_0\mu\nu$ si et seulement si MT, partie de
$v_0$, stoppe; ${7^0}$ il existe pour ${\rm R}\,({\rm MT}_\rho)$ certaines
configurations instantan\'ees $u_{st}$ telles que, partant de $\lambda
v_0\mu\nu$, ${\rm R}\,({\rm MT}_\rho)$ ne peut atteindre ces configurations
autrement qu'en passant par $\lambda v^*_0\mu\nu$ (c'est-\`a-dire si MT,
partie de $v_0$, stoppe).  On peut ainsi faire en sorte que le retour de
${\rm R}\,({\rm MT}_\rho)$ \`a $\lambda v_0\mu\nu$ (ou bien, le passage par des
$u_{st}$ encadr\'es par $\lambda'\nu'$ au lieu de $\lambda\nu$) soit
conditionn\'e par un stop de MT.

\textit{Preuve.} --- On montre comment passer de $\tau$, suppos\'e donn\'e
par un ensemble de relations $\{\,{\rm I}_{k,\tau}\,\}_{k\in{\rm K}_\tau}$
\`a l'ensemble des relations $\{\,{\rm I}_{j,\theta}\,\}_{j\in{\rm
J}_\theta}$ d\'efinissant $\theta$ et ${\rm MT}_\rho$.  Limitons-nous \`a
donner le principe de cette construction, en montrant comment simuler une
instruction ${\rm I}_{k_i,\tau}$ de la forme
$\alpha_p\sigma_q\rightarrow\sigma_f\alpha_g$.  A celle-ci, on associera :
une instruction
$\alpha_p\sigma_q\rightarrow\sigma_{f,g,\alpha}\,\varepsilon_{\alpha,\alpha,p,q,f,g,\sigma}$,
o\`u le symbole $\sigma_{fg\alpha}$ marque la place o\`u l'on doit modifier
$v_i$, et la nature de la modification; des instructions permettant de
conduire le contr\^ole \`a gauche de $\nu$ par un \'etat
$\varepsilon_{\alpha\alpha pqfg\nu}$; une instruction
$b\varepsilon_{\alpha\alpha pqfg\nu}\rightarrow\varepsilon_sr_{k_i}$, o\`u
$r_{k_i}$ repr\'esente $I_{k_i,\tau}$, compl\`etant $w_i$; des instructions
de service d\'epla\c cant $\nu$ et, \'eventuellement aussi $\lambda$, $\mu$
et $w_i$ tout entier, pour r\'etablir les blancs n\'ecessaires dans
$u_{i,0}$ puis reportant le contr\^ole en $\sigma_{f,g,\alpha}$ avec un
\'etat $\varepsilon_\sigma$; une instruction
$\sigma_{f,g,\alpha}\,\varepsilon_\sigma\rightarrow\sigma_f\alpha_g$ qui
compl\`ete $v_i$ dans $u_{i,0}$.

\textit{b.} \textsc{Th\'eor\`eme 1.} --- \textit{Le probl\`eme du stop pour
une machine de Turing r\'eversible g\'en\'erale est ind\'ecidable.  Il en
est de m\^eme du probl\`eme du retour \`a la configuration initiale, et de
celui du passage par une configuration d\'etermin\'ee autre que la
configuration initiale.}

\textit{c.} \textsc{Th\'eor\`eme 2.} --- \textit{L'\'equation $w=\theta^n
w$, o\`u $\theta$ est un isomorphisme de codes, avec $n\in{\bf N}$ est
r\'ecursivement insoluble en $n$ pour $w$, $\theta$ donn\'es quelconques.
L'equation $w_1 = \theta^nw_2$, avec $w_1\neq w_2$, est aussi
r\'ecursivement insoluble en $n$.}
\vskip 0.25in

{\small
($^*$) S\'eance du {21} octobre {1963}.

($^1$) \textsc{N. Chomsky} et \textsc{M. P. Sch\"utzenberger},
\textit{Computer Programming and Formal Systems}, Hirschberg et 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}
