Infinitely Growing Configurations in Emil Post’s Tag System Problem

Infinitely Growing Configurations in Emil Post’s
Tag System Problem

Nikita V. Kurilenko
Department of Mechanics and Mathematics
Moscow State University
Moscow, Russia
kurilenkonikita@gmail.com

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 20000 iterations of tag.

Keywords: tag systems; chaotic systems

Cite this publication as:
N. V. Kurilenko, “Infinitely Growing Configurations in Emil Post’s Tag System Problem,” Complex Systems, 31(3), 2022 pp. 279–286.
https://doi.org/10.25088/ComplexSystems.31.3.279