0-State Universal Turing Machine

The following sentences are equivalent (see [Stefan '99]):

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

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

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

References

[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