Infinitely growing configurations in Emil Post's tag system problem

Abstract

Emil Post's tag system problem posed the question of whether or not a tag system $\{N=3,P(0)=00,P(1)=1101\}$ has a configuration, simulation of which will never halt or end up in a loop. Over the subsequent decades, there were several attempts to find an answer to this question, including a recent study, during which the first $2^{84}$ initial configurations were checked. This paper presents a family of configurations of this type in the form of strings $A^{n}B{C}^m$ that evolve to $A^{n+1}B{C}^{m+1}$ after a finite number of steps. The proof of this behavior for all non-negative $n$ and $m$ is described later in this paper as a finite verification procedure, which is computationally bounded by 20 000 iterations of tag.

8 pages, 0 figures

References in corpus (1)

• After 100 Years, Can We Finally Crack Post's Problem of Tag? A Story of Computational Irreducibility, and More