Portal de Periódicos da CAPES

Zigzags in Turing Machines

2010; Springer Science+Business Media; Linguagem: Inglês

10.1007/978-3-642-13182-0_11

1611-3349

Anahí Gajardo, P. Guillon,

Computability, Logic, AI Algorithms

We study one-head machines through symbolic and topological dynamics. In particular, a subshift is associated to the subshift, and we are interested in its complexity in terms of realtime recognition. We emphasize the class of one-head machines whose subshift can be recognized by a deterministic pushdown automaton. We prove that this class corresponds to particular restrictions on the head movement, and to equicontinuity in associated dynamical systems.