Speedup and Slowdown Phenomena in Turing Machines

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]
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.
Permanent Citation
"Speedup and Slowdown Phenomena in Turing Machines"
http://demonstrations.wolfram.com/SpeedupAndSlowdownPhenomenaInTuringMachines/
Wolfram Demonstrations Project
Published: November 8 2012