We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
Infinitely Growing Configurations in Emil Post's Tag System Problem.
- Authors
Kurilenko, Nikita V.
- 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 284 initial configurations were checked. This paper presents a family of configurations of this type in the form of strings AnBCm that evolve to An+1BCm+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.
- Subjects
KOLMOGOROV complexity; FINITE, The
- Publication
Complex Systems, 2022, Vol 31, Issue 3, p279
- ISSN
0891-2513
- Publication type
Article
- DOI
10.25088/ComplexSystems.31.3.279