Simulation of Turing machines by a regular rewrite rule. (English) Zbl 0753.68052

Summary: We prove that for any Turing machine, there exists a regular (i.e. left- linear and nonoverlapping, also called orthogonal) and variable- preserving rule that simulates its behaviour. The main corollary is the undecidability of termination for such a rule.


68Q42 Grammars and rewriting systems
68Q05 Models of computation (Turing machines, etc.) (MSC2010)
03D03 Thue and Post systems, etc.
03D35 Undecidability and degrees of sets of sentences
Full Text: DOI


[1] Book, R.V., Thue systems as rewriting systems, J. symbolic comput., 3, 39-68, (1987) · Zbl 0638.68091
[2] Dauchet, M., Termination of rewriting is undecidable in the one-rule case, (), 262-268, Lecture Notes in Computer Science
[3] Dauchet, M., Simulation of Turing machines by a regular rewrite rule, (), 109-120, Lecture Notes in Computer Science
[4] Dershowitz, N., Termination, J. symbolic comput., 3, 69-116, (1987) · Zbl 0637.68035
[5] Dershowitz, N.; Jouannaud, J.P., Rewrite systems, (), 243-320 · Zbl 0900.68283
[6] Devienne, Ph., Weighted graphs: a tool for studying the halting problem and term complexity in term rewriting systems and logic programming, Theoret. comput. sci., 75, 157-215, (1990) · Zbl 0702.68036
[7] Jouannaud, J.P., J. symbolic comput., 3, 2-3, (1987), Editorial of
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.