Undecidability in binary tag systems and the post correspondence problem for five pairs of words
- Conference Paper
Rights / licenseCreative Commons Attribution 3.0 Unported
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. Show more
Mayr, Ernst W.
Book titleProceedings of the 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)
Journal / seriesLeibniz International Proceedings in Informatics
Pages / Article No.
PublisherSchloss Dagstuhl - Leibniz-Zentrum fur Informatik
SubjectTag system; Post correspondence problem; Undecidability
MoreShow all metadata