Skip to main content
1 of 5
Thomas
  • 2.8k
  • 16
  • 29

Is Post's tag system solved?

Has the 3-tag system investigated by Emil Post $(0->00, 1->1101)$ 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