9867

Fractal Dimension versus Time Complexity in Turing Machines

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

SNAPSHOTS

  • [Snapshot]
  • [Snapshot]
  • [Snapshot]

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.
    • Share:

Embed Interactive Demonstration New!

Just copy and paste this snippet of JavaScript code into your website or blog to put the live Demonstration on your site. More details »

Files require Wolfram CDF Player or Mathematica.









 
RELATED RESOURCES
Mathematica »
The #1 tool for creating Demonstrations
and anything technical.
Wolfram|Alpha »
Explore anything with the first
computational knowledge engine.
MathWorld »
The web's most extensive
mathematics resource.
Course Assistant Apps »
An app for every course—
right in the palm of your hand.
Wolfram Blog »
Read our views on math,
science, and technology.
Computable Document Format »
The format that makes Demonstrations
(and any information) easy to share and
interact with.
STEM Initiative »
Programs & resources for
educators, schools & students.
Computerbasedmath.org »
Join the initiative for modernizing
math education.
Step-by-step Solutions »
Walk through homework problems one step at a time, with hints to help along the way.
Wolfram Problem Generator »
Unlimited random practice problems and answers with built-in Step-by-step solutions. Practice online or make a printable study sheet.
Wolfram Language »
Knowledge-based programming for everyone.
Powered by Wolfram Mathematica © 2014 Wolfram Demonstrations Project & Contributors  |  Terms of Use  |  Privacy Policy  |  RSS Give us your feedback
Note: To run this Demonstration you need Mathematica 7+ or the free Mathematica Player 7EX
Download or upgrade to Mathematica Player 7EX
I already have Mathematica Player or Mathematica 7+