# 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