# Fractal Dimension versus Time Complexity in Turing Machines

Requires a Wolfram Notebook System

Interact on desktop, mobile and cloud with the free Wolfram Player or other Wolfram Language products.

This Demonstration illustrates some of the main results of a research project in which the authors investigated the behavior of small Turing machines (TMs). Among the surprising findings (see also [2, 3, 5]) was an effect that is shown in this Demonstration: the fractal dimension of the memory configurations of a TM throughout time (the space-time diagrams shown) is an indication of its runtime complexity class.

[more]
Contributed by: Joost J. Joosten, Fernando Soler-Toscano, and Hector Zenil (February 2014)

Open content licensed under CC BY-NC-SA

## Snapshots

## Details

The TMs are fed with a series of inputs where the input consists of consecutive black cells on an otherwise white tape. By convention, the TM computation starts with its head in the rightmost cell in state 1. The TMs are numbered using Wolfram's enumeration scheme [1]. Small and big notation indicates the asymptotic behavior of space or time usage. For example, denotes linear limit behavior and denotes super-polynomial limit behavior (in the limit, growing faster than any polynomial).

The Busy Beaver is the TM in this space of three states and two colors that has the largest computation time at each input. It can be seen as TM number 599603, which lives in -space and -time. Since the runtimes grow so astronomically fast, only the computations corresponding to the first five inputs are shown.

The fractal dimension is computed by using an approximation of the box-counting dimension. Since the convergence rates of these approximations are in general very slow, the sequences are analyzed and small values are extrapolated to the larger setting [4].

References

[1] J. J. Joosten. "Turing Machine Enumeration: NKS versus Lexicographical" from the Wolfram Demonstrations Project—A Wolfram Web Resource. demonstrations.wolfram.com/TuringMachineEnumerationNKSVersusLexicographical.

[2] J. J. Joosten, F. Soler-Toscano, and H. Zenil, "Program-size versus Time Complexity Slowdown and Speed-up Phenomena in the Micro-cosmos of Small Turing Machines," *International Journal of Unconventional Computing*, 7(5), 2011 pp. 353-387.

[3] J. J. Joosten, F. Soler-Toscano, and H. Zenil. "Speedup and Slowdown Phenomena in Turing Machines" from the Wolfram Demonstrations Project—A Wolfram Web Resource. demonstrations.wolfram.com/SpeedupAndSlowdownPhenomenaInTuringMachines.

[4] J. J. Joosten, F. Soler-Toscano, and H. Zenil. "Fractal Dimension versus Computational Complexity." arxiv.org/abs/1309.1779.

[5] H. Zenil, F. Soler-Toscano, and J. J. Joosten. "Empirical Encounters with Computational Irreducibility and Unpredictability," *Minds and Machines*, 22(3), 2012 pp. 149-165. doi:dx.doi.org/10.1007/s11023-011-9262-y.

## Permanent Citation