You are using a browser not supported by the Wolfram Cloud
Supported browsers include recent versions of Chrome, Edge, Firefox and Safari.
I understand and wish to continue anyway »
WOLFRAM NOTEBOOK
Fractal Dimension versus Time Complexity in Turing Machines
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.