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