Document Open Access Logo

Undecidability in Binary Tag Systems and the Post Correspondence Problem for Five Pairs of Words

Author Turlough Neary

PDF
Thumbnail PDF

File

LIPIcs.STACS.2015.649.pdf
  • Filesize: 0.6 MB
  • 13 pages

Document Identifiers

Author Details

Turlough Neary

Cite AsGet BibTex

Turlough Neary. Undecidability in Binary Tag Systems and the Post Correspondence Problem for Five Pairs of Words. In 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 30, pp. 649-661, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
https://doi.org/10.4230/LIPIcs.STACS.2015.649

Abstract

Since Cocke and Minsky proved 2-tag systems universal, they have been extensively used to prove the universality of numerous computational models. Unfortunately, all known algorithms give universal 2-tag systems that have a large number of symbols. In this work, tag systems with only 2 symbols (the minimum possible) are proved universal via an intricate construction showing that they simulate cyclic tag systems. We immediately find applications of our result. We reduce the halting problem for binary tag systems to the Post correspondence problem for 5 pairs of words. This improves on 7 pairs, the previous bound for undecidability in this problem. Following our result, only the cases for 3 and 4 pairs of words remains open, as the problem is known to be decidable for 2 pairs. In a further application, we apply the reductions of Vesa Halava and others to show that the matrix mortality problem is undecidable for sets with six 3 x 3 matrices and for sets with two 18 x 18 matrices. The previous bounds for the undecidability in this problem was seven 3 x 3 matrices and two 21 x 21 matrices.
Keywords
  • tag system
  • Post correspondence problem
  • undecidability

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Vincent D. Blondel and John N. Tsitsiklis. When is a pair of matrices mortal? Information Processing Letters, 63(5):283-286, 1997. Google Scholar
  2. Vincent D. Blondel and John N. Tsitsiklis. A survey of computational complexity results in systems and control. Automatica, 36(9):1249-1274, 2000. Google Scholar
  3. Julien Cassaigne and Juhani Karhumäki. Examples of undecidable problems for 2-generator matrix semigroup. TCS, 204(1-2):29-34, 1998. Google Scholar
  4. Volker Claus. Some remarks on PCP(k) and related problems. Bull. EATCS, 12:54-61, 1980. Google Scholar
  5. John Cocke and Marvin Minsky. Universality of tag systems with P = 2. Journal of the ACM, 11(1):15-20, 1964. Google Scholar
  6. Matthew Cook. Universality in elementary cellular automata. Complex Systems, 15(1):1-40, 2004. Google Scholar
  7. Andrzej Ehrenfeucht, Juhani Karhumäki, and Grzegorz Rozenberg. The (generalized) Post correspondence problem with lists consisting of two words is decidable. TCS, 21(2):119-144, 1982. Google Scholar
  8. Vesa Halava and Tero Harju. Mortality in matrix semigroups. American Mathematical Monthly, 108(7):649-653, 2001. Google Scholar
  9. Vesa Halava, Tero Harju, and Mika Hirvensalo. Undecidability bounds for integer matrices using Claus instances. IJFCS, 18(5):931-948, 2007. Google Scholar
  10. Tero Harju and Maurice Margenstern. Splicing systems for universal Turing machines. In DNA 10, volume 3384 of LNCS, pages 149-158. Springer, 2005. Google Scholar
  11. Kristian Lindgren and Mats G. Nordahl. Universal computation in simple one-dimensional cellular automata. Complex Systems, 4(3):299-318, 1990. Google Scholar
  12. Yuri Matiyasevich and Géraud Sénizergues. Decision problems for semi-Thue systems with a few rules. TCS, 330(1):145-169. (An earlier version appeared in "11th Annual IEEE Symposium on Logic in Computer Science, LICS 1996".), 2005. Google Scholar
  13. Marvin Minsky. Recursive unsolvability of Post’s problem of "tag" and other topics in theory of Turing machines. Annals of Mathematics, 74(3):437-455, 1961. Google Scholar
  14. Marvin Minsky. Size and structure of universal Turing machines using tag systems. In Recursive Function Theory: Proceedings, Symposium in Pure Mathematics, volume 5, pages 229-238, Provelence, 1962. AMS. Google Scholar
  15. Turlough Neary and Damien Woods. P-completeness of cellular automaton Rule 110. In ICALP 2006, Part I, volume 4051 of LNCS, pages 132-143. Springer, 2006. Google Scholar
  16. Michael S. Paterson. Unsolvability in 3× 3 matrices. Studies in Applied Mathematics, 49(1):105-107, 1970. Google Scholar
  17. Emil L. Post. Formal reductions of the general combinatorial decision problem. American Journal of Mathematics, 65(2):197-215, 1943. Google Scholar
  18. Emil L. Post. A variant of a recursively unsolvable problem. Bulletin of The American Mathematical Society, 52:264-268, 1946. Google Scholar
  19. Raphael M. Robinson. Undecidability and nonperiodicity for tilings of the plane. Inventiones Mathematicae, 12(3):177-209, 1971. Google Scholar
  20. Yurii Rogozhin. Small universal Turing machines. TCS, 168(2):215-240, 1996. Google Scholar
  21. Paul Rothemund. A DNA and restriction enzyme implementation of Turing machines. In DNA Based Computers, volume 27 of DIMACS, pages 75-119. AMS, 1996. Google Scholar
  22. Hao Wang. Tag systems and lag systems. Mathematical Annals, 152:65-74, 1963. Google Scholar
  23. Damien Woods and Turlough Neary. On the time complexity of 2-tag systems and small universal Turing machines. In 47^th Annual IEEE Symposium on Foundations of Computer Science, pages 439-448, 2006. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact