Infinitely Growing Configurations in Emil Post’s Tag System Problem
Nikita V. Kurilenko · Complex Systems · 2022
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 20000 iterations of tag.