0-State Universal Turing Machine
The following sentences are equivalent (see [Stefan '99]):
In 1956 Claude Shanonn published a paper proving a 2-state UTM is possible (C. E. Shannon: ``A Universal Turing Machine with
Two Internal States", in Annals of Mathematics Studies, No. 34:
Automata Studies, Princeton Univ. Press, pp 157-165, 1956.).
- 0-state Universal Turing Machine (UTM) is possible
- the UTM is simple
- there is a UTM without the finite automaton
- the complexity of computation can be ostracized in programs
- the simple hardware can be completely segregated by the complex software
The research related to 0-State UTM is the result of the struggle to emphasize meaningful differences between size and
complexity in computation (see also Loops & Complexity ).
[Stefan '97] Gh. Stefan: Circuit Complexity, Recursion, Grammars and Information.
Multiple Morphisms, Ed. Transilvania University of Brasov, 1997.
[Stefan '99] Gh. Stefan: "No State Universal Turing Machine", in Fundamentals of Computation Theory, Iasi '99, 1999.
[Stefan '06] Gh. Stefan: "A Universal Turing Machine with Zero Internal States", in
Romanian Journal of Information Science and Technology, Vol. 9, no. 3, 2006, p. 227-243
[Stefan work in endless progress] Gh. Stefan:
Loops & Complexity in Digital Systems. Lecture Notes on Digital Design in the Giga-Gate/Chip Era