Fractal

The fractal 1RB0LA_1RC---_0RD0RC_1LD0LA (bbch).

A fractal is a non-halting Turing machine that displays self-similarity at different scales.

Example

The fractal 1RB0LA_1RC---_0RD0RC_1LD0LA (bbch) is shown on the right, and portrays the most common type of fractal Turing machine. The fractal consists of two major parts: the left part consists of copies of the fractal at smaller scales, while the right part consists of an interrupted bouncer.

The idea for the following analysis is to notice that, if X denotes the top quarter of the image, the spacetime diagram for the fractal seems to consist of two copies of X, followed by another copy of X but modified such that the bouncers on the right are all increased in size by some constant. Hence we must consider not only X, but also variants of X corresponding to any starting bouncer size. In other words, the starting bouncer size must be an additional parameter to our recursion. There will also be fillers between the copies of X in order to move the head to desired positions.

With this idea, define a two-parameter family of macro steps R_{n, m} recursively as follows:

${\begin{aligned}\mathbf {R} _{0,m}&=\mathrm {A} 0\ \mathrm {B} 0\ \mathrm {C} 1^{m}\ \mathrm {C} 0,\\\mathbf {R} _{n+1,m}&=\mathbf {R} _{n,m}\ \mathrm {D} 0^{2^{n}+m+1}\ \mathrm {D} 1\ \mathrm {A} 1^{2^{n+1}-1}\ \mathbf {R} _{n,0}\ \mathrm {D} 1\ \mathbf {R} _{n,m+2^{n}}.\end{aligned}}$

We can verify by induction on n that

R_{n, m}: A (0^2n)<0(1m)(0^(2n+1-1)) → D (1^2n+1)(0^(2n+m))>.

The source of R_{n, 0} matches the starting configuration, and the length of R_{n, 0} is easily seen to grow without bound. It follows that the transcript of this Turing machine is the limit of R_{n, 0} as n approaches ∞.

Step counts

By taking lengths of the formulas in the equations for R_{n, m}, we find that the step counts a_n = |R_n| obey the recurrence

${\begin{aligned}a_{0,m}&=m+3\\a_{n+1,m}&=a_{n,m}+a_{n,0}+a_{n,m+2^{n}}+3\cdot 2^{n}+m+2.\end{aligned}}$

Using the ansatz $a_{n,m}=f_{n}m+g_{n}$, we find that the solution to the recurrence is

$a_{n,m}=(2^{n+1}-1)m+2\cdot 4^{n}+4\cdot 3^{n}-2\cdot 2^{n}-1$.

In particular,

$a_{n,0}=2\cdot 4^{n}+4\cdot 3^{n}-2\cdot 2^{n}-1.$