Pre-Publicación 2009-04
Anahi Gajardo:
The complexity of a particular shift associated to a Turing machine
Abstract:
A sub shift is associated to each Turing machine, and its properties are studied. The sub shift consists in the set of sequences of symbols that the machine reads, together with the states it takes during each evolution, considering every initial configuration. We focus on machines whose associated sub shift is recognized by a deterministic pushdown automaton in real-time. It is proved that all of these machines have restrictions on their movements. Moreover, these machines are characterized as machines that cannot make zig-zag movements of arbitrary length. We also prove that synchronicity is related to restrictions on the machine movements.
