Fractal Dimension versus Time Complexity in Turing Machines

Requires a Wolfram Notebook System

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

Requires a Wolfram Notebook System

Edit on desktop, mobile and cloud with any Wolfram Language product.

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]

We considered TMs with two colors and three states that run on a one-sided tape where the red cell indicates the end of the tape. A computation halts on a particular input if the head "falls off" on the right-hand side. Each of the blocks in the diagram depicts a so-called space-time diagram: the top line is the original tape input and each line below shows the TM tape at the next step in the computation. There is a close connection between the limiting Hausdorff dimension of the space-time diagrams and the time complexity class to which the TM belongs.

[less]

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.



Feedback (field required)
Email (field required) Name
Occupation Organization
Note: Your message & contact information may be shared with the author of any specific Demonstration for which you give feedback.
Send