Skip to main content
3 of 5
fix confusing markup
Emil Jeřábek
  • 47.2k
  • 4
  • 147
  • 209

Is Post's tag system solved?

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?

Thomas
  • 2.8k
  • 16
  • 29