18
$\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?

Improve this question
$\endgroup$
1
  • $\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$
    – user44143
    Commented Dec 2, 2018 at 9:37

2 Answers 2

Reset to default
7
+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.

Improve this answer
$\endgroup$
12
$\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.

Improve this answer
$\endgroup$
2
  • $\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
    Commented Dec 3, 2018 at 7:38
  • $\begingroup$ indeed, it's the period 40 and period 66 words which are different. $\endgroup$
    – Carlo Beenakker
    Commented Dec 3, 2018 at 10:50

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .