Skip to main content
4 of 5
edited tags
David Roberts
  • 35.5k
  • 11
  • 124
  • 349

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