\input zb-basic
\input zb-ioport
\iteman{io-port 01738661}
\itemau{Caucal, Didier}
\itemti{On the transition graphs of Turing machines.}
\itemso{Margenstern, Maurice (ed.) et al., Machines, computations, and universality. 3rd international conference, MCU 2001, Chi\c{s}in\v{a}u, Moldova, May 23-27, 2001. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 2055, 177-189 (2001).}
\itemab
Summary: As for pushdown automata, we consider labelled Turing machines with $\epsilon$-rules. With any Turing machine $M$ and with a rational set $C$ of configurations, we associate the restriction to $C$ of the $\varepsilon$-closure of the transition set of $M$. We get the same family of graphs by using the labelled word rewriting systems. We show that this family is the set of graphs obtained from the binary tree by applying an inverse mapping into $f$ followed by a rational restriction, where $f$ is any family of recursively enumerable languages containing the rational closure of all linear languages. We show also that this family is obtained from the rational graphs by inverse rational mappings.
\itemrv{~}
\itemcc{}
\itemut{}
\itemli{http://link.springer.de/link/service/series/0558/bibs/2055/20550177}
\end