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\ge 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\ge 1$ such that for all sufficiently large $N$, the $N$-th transition is identical to the $N+px$-th transition.

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}$.