Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH scholarly article en Neary, Turlough http://www.dagstuhl.de/lipics License
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-49486
URL:

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

pdf-format:


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.

BibTeX - Entry

@InProceedings{neary:LIPIcs:2015:4948,
  author =	{Turlough Neary},
  title =	{{Undecidability in Binary Tag Systems and the Post Correspondence Problem for Five Pairs of Words}},
  booktitle =	{32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)},
  pages =	{649--661},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-78-1},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{30},
  editor =	{Ernst W. Mayr and Nicolas Ollinger},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2015/4948},
  URN =		{urn:nbn:de:0030-drops-49486},
  doi =		{http://dx.doi.org/10.4230/LIPIcs.STACS.2015.649},
  annote =	{Keywords: tag system, Post correspondence problem, undecidability}
}

Keywords: tag system, Post correspondence problem, undecidability
Seminar: 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)
Related Scholarly Article:
Issue date: 2015
Date of publication: 2015


DROPS-Home | Fulltext Search | Imprint Published by LZI