Small Semi-Thue System Universal with Respect to the Termination Problem
Vesa Halava, Yuri Matiyasevich, Reino Niskanen · Fundamenta Informaticae · 2017
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 Turi ng 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.