License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2015.649
URN: urn:nbn:de:0030-drops-49486
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/4948/
Go to the corresponding LIPIcs Volume Portal

Neary, Turlough

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

pdf-format:
48.pdf (0.6 MB)

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 =		{10.4230/LIPIcs.STACS.2015.649},
  annote =	{Keywords: tag system, Post correspondence problem, undecidability}
}

Keywords: tag system, Post correspondence problem, undecidability
Collection: 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)
Issue Date: 2015
Date of publication: 26.02.2015

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI