15
$\begingroup$

Has the 3-tag system investigated by Emil Post $(0\to00, 1\to1101)$ been solved? Is there a decision algorithm to determine which starting strings terminate, which end up in a cycle, and which (if any) grow without bound?

Also, what cycle structures are there? Setting $a=$ '00' and $b=$ '1101', the only cycles I know of begin with $ab, b^2 a^2$, combinations of these, and $a^2 b^3 (a^3 b^3)^n$. Are there any more?

$\endgroup$
  • $\begingroup$ Worth noting: this is the 75th anniversary of the problem’s publication! Post mentioned its intractability on p 204 of his 1943 article. The bibliography to the Wikipedia article (en.wikipedia.org/wiki/Tag_System) has the citation to Post and quotes Minsky concurring in 1967. $\endgroup$ – Matt F. Dec 2 '18 at 9:37
6
+200
$\begingroup$

Here are the two irreducible repeating patterns that Liesbeth de Mol discovered, together with a third high-period irreducible repeating pattern discovered by Rich Schroeppel:

  • $b^3 a^5 b^5$ (period 40);
  • $a b^2 a b^3 a^3 b^3 a^2 b^2 a^4 b^2$ (period 66);
  • $a b^3 a b a b a^2 b^2 a b^9 a^2$ (period 282);

This was discovered by 2004, and as far as I know no other irreducible repeating patterns are known yet.

$\endgroup$
11
$\begingroup$

Q1: The status of Post's 3-tag system as of 2011 was reviewed by Liesbeth de Mol in On the complex behavior of simple tag systems. An experimental approach. "It is still not known whether this particular example has a decidable reachability problem." Citations to this work through 2017 indicate that the situation has not changed since 2011.

Q2: Concerning cycle structures, De Mol found additional cycles:

Let $a = 00$, $b = 1101$. Watanabe deduced wrongly that there are only four kinds of periodic words in Post’s tag system, i.e., $a^2b^3(a^3b^3)^n$ with period 6, $ba$ with period 2, $b^2a^2$ with period 4, or any concatenation of the last two. In some preliminary runs on Post’s tag system we found three other kinds of periodic words, a period 10, 40 and 66. The period 10 $(b^2a^3b^3a^2)$ is similar to the periodic words found by Watanabe, the period 40 and 66 are very different from these periodic words.

$\endgroup$
  • $\begingroup$ The period 10 word is a combination of $b^2 a^2 $ and $ab$, so it's not technically a new periodic word $\endgroup$ – Thomas Dec 3 '18 at 7:38
  • $\begingroup$ indeed, it's the period 40 and period 66 words which are different. $\endgroup$ – Carlo Beenakker Dec 3 '18 at 10:50

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.