User:ISquillante

Isis Squillante

Discord: @isisoftheeast

E-Mail: isissquillante@gmail.com

Drafts below.

Quasicycler

A quasicycler is a Turing machine which is neither a cycler nor a translated cycler but cycles through states periodically.

Formal definition

A quasicycler or quasicyclic Turing machine $\tau$ is a Turing machine which has the following two properties:

1. There exists some natural number $p\geq 1$ such that for all sufficiently large $N$, the current state of $\tau$ after $N$ transitions is identical to the current state of $\tau$ after $N+p$ transitions. $p$ is called the period length of $\tau$.
2. There is no natural number $x\geq 1$ such that for all sufficiently large $N$, the $N$-th transition is identical to the $N+px$-th transition.

This second property is what distinguishes quasicyclers from translated cyclers; translated cyclers are defined by the negation of the second property of quasicyclers.

Properties

For any quasicyclic Turing machine with preperiod of length $r$ and period of length $p$, its rate of strict tape growth $\gamma (x)$ is bounded above by ${\frac {p}{2}}{\sqrt {x}}+{\frac {r}{3}}$.