Speedup and Slowdown Phenomena in Turing Machines

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


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


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

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+