Affiliations: [a] Department of Mathematics and Statistics, University of Turku, Finland, and Department of Computer Science, University of Liverpool, UK. [email protected] | [b] St. Petersburg Department of Steklov Institute of Mathematics of Russian Academy of Sciences (POMI RAN), St.Petersburg, Russia. [email protected] | [c] Department of Computer Science, University of Liverpool, UK. [email protected]
Correspondence:
[*]
Address for correspondence: Department of Mathematics and Statistics, University of Turku, Finland
Abstract: The termination problem for semi-Thue systems asks whether all derivations for a given word in a given semi-Thue system are finite, i.e., all derivations terminate after finite number of steps. This problem is known to be undecidable, there is a standard reduction of the halting problem of the Turing machines into termination problem; moreover, one can fix a semi-Thue system and still have the undecidability. In 1996 Sénizergues and the second author gave a construction for a 3-rule semi-Thue system with undecidable termination problem. However, in their construction the words of one of the rules are very long. Using some ideas of Tseijtin we give a construction for a semi-Thue system with low number of short rules having undecidable termination problem. Namely, we construct a semi-Thue system with 24 rules over 8 letter alphabet with rule words of length at most 5, and the termination problem for this semi-Thue system is undecidable. Moreover, this system is universal, that is, it can simulate any semi-Thue system.
Keywords: semi-Thue system, termination problem, undecidability, universal semi-Thue system
