Small Semi-Thue System Universal with Respect to the Termination Problem

• Autorzy: Halava, V. , Matiyasevich, Y. , Niskanen, R.
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

semi-Thue system; termination problem; undecidability; universal semi-Thue system

• Czasopismo: Fundamenta Informaticae
• Rocznik: 2017
• Tom: Vol. 154, nr 1/4
• Strony: 177--184
• Opis fizyczny: Bibliogr. 11 poz.

Twórcy

autor

Halava, V.

• Department of Mathematics and Statistics, University of Turku, Finland,
• Department of Computer Science, University of Liverpool, UK

autor

Matiyasevich, Y.

• St. Petersburg Department of Steklov Institute of Mathematics of Russian Academy of Sciences (POMI RAN), St.Petersburg, Russia,

autor

Niskanen, R.

• Department of Computer Science, University of Liverpool, UK,

Bibliografia

• [1] Matiyasevich Y, Sénizergues G. Decision problems for semi-Thue systems with a few rules. In: 11th Annual IEEE Symposium on Logic in Computer Science (New Brunswick, NJ, 1996), pp. 523–531. IEEE Comput. Soc. Press, Los Alamitos, CA, 1996. doi:10.1109/LICS.1996.561469.
• [2] Matiyasevich Y, Sénizergues G. Decision problems for semi-Thue systems with a few rules. Theor. Comput. Sci., 2005;330(1):145–169. doi:10.1016/j.tcs.2004.09.016.
• [3] Матиясевич Ю.В, Простые примеры неразрешимых ассоциативных исчислений. Доклады АН СССР 1967;173:1264––1266. Translated as Yu. V. Matiyasevich. Simple examples of undecidable associative calculi. Soviet Mathematics. Doklady, volume 8, pages 555—557, 1967, MR 0216955, ZBl 0189.01102.
• [4]Цейтин Г.С. Ассоциативное исчисление с неразрешимой проблемой эквивалентности. Доклады АН СССР. 107:370–371.
• [5] Цейтин Г.С. Ассоциативное исчисление с неразрешимой проблемой эквивалентности. Тр.МИАН СССР, 1958;52:172–189. http://mi.mathnet.ru/tm1317. MR 99922, ZBl 0087.25303.
• [6] Scott D. A short recursively unsolvable problem. J. Symb. Logic, 1956;21:111–112.
• [7]Новиков П.С. Об алгоритмической неразрешимости проблемы тождества слов в теори групп. Тр.МИАН СССР, 1955. pp. 3–143. http://mi.mathnet.ru/eng/tm1180, MR 75197, ZBl an:0068.01301., 1955. pp. 3–143. http://mi.mathnet.ru/eng/tm1180, MR 75197, ZBl an:0068.01301.
• [8] Huet G, Lankford D. On the uniform halting problem for term rewriting systems. Rapport Laboria, 1978. URL http://www.ens-lyon.fr/LIP/REWRITING/TERMINATION/Huet_Lankford.pdf.
• [9] Rogozhin Y. Small Universal Turing Machines. Theor. Comput. Sci., 1996;168(2):215–240. doi:10.1016/S0304-3975(96)00077-1.
• [10] Sénizergues G. Some Undecidable Termination Problems for Semi-Thue Systems. Theor. Comput. Sci., 1995;142(2):257–276. doi:10.1016/0304-3975(94)00278-9.
• [11]Маканин Г.С. Проблема тождества в конечно определенных полугруппах. Доклады АН СССР, 1966;171:285–287. Translated in Soviet Math. Dokl. 7, (1966), 1478-1480.

Identyfikatory

DOI

10.3233/FI-2017-1559