On the simplest and smallest universal Turing machine
Why research on the universality of the Wolfram 2,3 Turing machine (http://www.wolframscience.com/prizes/tm23/) and the small universal Turing machine is relevant for modern computer science:
* New techniques for proving universality are being developed (Alex Smith’s novel approach for unbounded computations from arbitrary lengths and non-periodic initial configurations).
* Completely new universal systems have been discovered (cyclic tag- systems, bi-tag systems).
* Such research provides a better understanding of universality, its limits, its underlying principles and its necessary and sufficient conditions.
* It is a base for actually building universal devices when only a few elements can be used, e.g. in nanotechnology or molecular computation.
* Simple/small machines may be more easily/effectively embedded in other systems.
* The old discovery/invention duality question comes to the fore: It sheds light on how simple universality is, how frequently it occurs, whether it is engineered or not, whether one builds universal computation or finds it in the universe.
* It could shed light on the relative feasibility of universal Turing machines based on different tape configurations (e.g. blank characters, repetitive words, non-repetitive with computationally simple backgrounds) as actual physical systems. At present it is not at all clear why one ought to favor blank characters over other possible real-world backgrounds, such as “noise.”
* Questions of size and complexity arise: It would be interesting, for instance, to find out whether there is a polynomial (or exponential) trade-off between program size and and the concept of simulating a process.
* Some questions on algorithmic complexity arise: Will the encoding always be more complex if the machine is simpler? All theorems in algorithmic information theory depend on additive constants, which depend on the sizes of typical universal Turing machines. What is the impact of different generalizations of universality on algorithmic complexity and what is the role of encoding in such a measure?
* Some questions arise on the relation between several variants of universality definitions: Is there an effective and efficient encoding for each non-periodic encoding preserving universality? If so, how does this impact their complexity? Is there a non-periodic encoding with blank characters for each periodic blank word encoding, and what would the impact of such an encoding be on the size/complexity of the Turing machine in question?
The field is active and still an important area of research. Several computer science conferences include talks on small computational systems. For instance, Computability in Europe (CiE) and Machines, Computations and Universality (MCU) included such talks this year, focusing in particular on reversible cellular automata and universal Turing machines.
Here are some references from the small Turing machine community, some of them very recent:
[1] Manfred Kudlek. Small deterministic Turing machines. Theoretical Computer Science, 168(2):241-255, November 1996.
[2] Manfred Kudlek and Yurii Rogozhin. A universal Turing machine with 3 states and 9 symbols. In Werner Kuich, Grzegorz Rozenberg, and Arto Salomaa, editors, Developments in Language Theory (DLT) 2001, vol. 2295 of LNCS, pp. 311-318, Vienna, May 2002. Springer.
[3] Maurice Margenstern and Liudmila Pavlotskaya. On the optimal number of instructions for universality of Turing machines connected with a finite automaton. International Journal of Algebra and Computation, 13(2):133-202, April 2003.
[4] Claudio Baiocchi. Three small universal Turing machines. In Maurice Margenstern and Yurii Rogozhin, editors, Machines, Computations, and Universality (MCU), volume 2055 of LNCS, pp. 1-10, Chisinau Moldavia, May 2001. Springer.
[5] Turlough Neary and Damien Woods. Four small universal Turing machines. Machines, Computations, and Universality (MCU), volume 4664 of LNCS, pp. 242-254, Orleans, France, September 2007. Springer.
[6] Yurii Rogozhin. Small universal Turing machines. Theoretical Computer Science, 168(2):215-240, November 1996.
[7] Shigeru Watanabe. 5-symbol 8-state and 5-symbol 6-state universal Turing machines. Journal of the ACM, 8(4):476-483, October 1961.
[8] Shigeru Watanabe. 4-symbol 5-state universal Turing machines. Journal of Information Processing Society of Japan, 13(9):588-592, 1972.
[9] Stephen Wolfram. A New Kind of Science. Wolfram Media, 2002.
I will post more later on Alex Smith’s contribution after the proof he provided to prove the universality of Wolfram’s 2,3 Turing machine.
Comments (2 comments)
[...] Some of the researchers in the video talk about how nature produce its own nanomachines, such as the flagella that let spermatozoa to swim. Imagine how many structures can be found by exploring the universe of possible simple nanostructures. We also know that starting from some few elements computing devices could be capable of universal computation (see previous previous post on the smallest universal Turing machine) so they could provide the nanomachine with coded instructions for the automatic performance of any task–of course with the constraints of its mechanical capabilities. [...]
Anima ex Machina » Blog Archive » HD Nanotechnology video from KQED / November 8th, 2007, 2:00 pm
[...] Some of the researchers in the video talk about how nature produce its own nanomachines, such as the flagella that let spermatozoa to swim. Imagine how many structures can be found by exploring the universe of possible simple nanostructures. We also know that starting from some few elements computing devices could be capable of universal computation (see my previous post on the smallest universal Turing machine) so they could provide the nanomachine with coded instructions for the automatic performance of any task–of course with the constraints of its mechanical capabilities. [...]
Anima ex Machina » Blog Archive » HD Nanotechnology video from KQED / November 8th, 2007, 2:27 pm
What do you think?
You must be logged in to post a comment.