## 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