Wolfram Demonstrations Project

12,000+ Open Interactive Demonstrations
Powered by Notebook Technology »

Speedup and Slowdown Phenomena in Turing Machines

Initializing live version
Download to Desktop

Requires a Wolfram Notebook System

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

This Demonstration shows how on average using more states in a Turing machine (TM) leads to slower-running algorithms to compute the same function. Use the slider "function" to choose between the 21 functions that occur in the three explored Turing machine spaces with two symbols and two, three, and four states.

[more]

The diagrams show how much tape space and how much time the Turing machines used to compute each function with different states. The first column of diagrams with refers to how many tape cells were used by the TM. The second column displays how many computation steps were needed before the TMs finished their computation. For example, the plots the time usages for each Turing machine; the diagram plots the average time usage, and the diagram shows the harmonic average (as a measure of average information) computed in a unit of time. Function 8, for example, is the function that just deletes the first black input cell; you can see that there are Turing machines with three and four states that compute function 8 in exponential time.

On the left, a visual representation of the computed function is given. You should read it as a sequence of rows, where each row represents an output tape configuration. The top row is the output (as a tape configuration) of the TM when it started with just one black cell. The next row below it is the tape configuration that is output by the TM after feeding it two consecutive black cells etc. Our TMs compute with only black and white cells and do not use other colors. A red tape indicates that the TM did not halt on the corresponding input. You can choose the number of states to be 2, 3, or 4.

[less]

Contributed by: Joost Joosten, Fernando Soler-Toscano, Hector Zenil (November 2012)
Open content licensed under CC BY-NC-SA

Snapshots

Details

The Demonstration can be seen as a visual summary of a long-term project performed by the authors. Refer to [1] for more details of how the experiment was performed. To the authors' knowledge, the project is the first experimental approach to study the tradeoff between time complexity and Kolmogorov complexity.

We have looked at all 4,096 TMs with two states and two colors and collected all 74 different functions computed by them. Next, we looked at all the close to three million TMs with three states and two colors, again focusing on the different functions computed by them. For TMs with four states and two colors, we were forced to take a large sample. We then found these 21 functions computed in the three spaces.

To deal with the halting problem and other undecidable phenomena, we took a pragmatic approach using mathematical analysis to predict outcomes of TMs that run for an astronomically long time and cut off values when such analysis might not have yielded anything. We refer the reader to [2] for more details.

The top line in the Demonstration shows how many TMs compute the selected function. It also shows the different number of what we call algorithms. We say that two TMs that have the same time and space usages per input compute the same algorithm (this is a nonstandard notion of algorithm). For every function, we also show the number of different algorithms computing that function.

An overview of the most prominent findings is presented in a forthcoming book [3].

References

[1] 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. arxiv.org/abs/1102.5389.

[2] 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.

[3] H. Zenil, F. Soler-Toscano, and J. J. Joosten, The Micro-Cosmos of Small Turing Machines, SpringerBrief, Springer Verlag, forthcoming.

Embed Code

Take advantage of the Wolfram Notebook Emebedder for the recommended user experience.

Related Demonstrations More by Author
Browse all topics
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