Is Post's tag system solved?
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.
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.