Gheorghe ŞTEFAN
A Universal Turing Machine with Zero Internal States

Abstract.
Can we define the simplest Universal Turing Machine (UTM) as a structure containing only uniform circuits? Is there possible a 0-state machine containing only structures having constant sized simple definitions. In a 0-state UTM all random structures are missing, and the resulting system exhibits only uniform circuits. Removing the finite automaton (FA) from the definition of UTM is the main structural effect of our approach. The state of the computational process is stored only on the “tape”, in contrast with the current versions of UTM in which the state of the computational process is given by both, the state of FA and the content of the “tape”. In the current UTMs, FA interprets the description of a certain Turing Machine (TM) stored on the “tape”. In the proposed, 0-state UTM, the description of a certain TM, stored on the same “tape”, is executed only by uniform simple circuits.