We present a variant with no control states of the Turing machine model of computation in which, at each computation step, the operation to be performed next is determined by the symbol currently scanned and by a bounded-length suffix of the sequence of the operations already executed on the tape. We show that our variant is Turing complete, i.e., it can simulate any (standard) Turing machine. (In fact, we shall provide a strong simulation which replicates the same tape configurations assumed by the simulated Turing machine, without using any additional tape symbol.) As a consequence, we argue that in order to perform general computation tasks, Turing machines do not need to memorize in their control states events arbitrarily far back in the past.
A variant of Turing machines with no control states and its connection to bounded temporal memory
CANTONE, Domenico;
2016-01-01
Abstract
We present a variant with no control states of the Turing machine model of computation in which, at each computation step, the operation to be performed next is determined by the symbol currently scanned and by a bounded-length suffix of the sequence of the operations already executed on the tape. We show that our variant is Turing complete, i.e., it can simulate any (standard) Turing machine. (In fact, we shall provide a strong simulation which replicates the same tape configurations assumed by the simulated Turing machine, without using any additional tape symbol.) As a consequence, we argue that in order to perform general computation tasks, Turing machines do not need to memorize in their control states events arbitrarily far back in the past.File | Dimensione | Formato | |
---|---|---|---|
A variant of Turing machines with no control states and its connection to bounded temporal memory..pdf
accesso aperto
Descrizione: Articolo principale
Tipologia:
Versione Editoriale (PDF)
Licenza:
Creative commons
Dimensione
505.38 kB
Formato
Adobe PDF
|
505.38 kB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.