Zigzags in Turing Machines

DOI10.1007/978-3-642-13182-0_11zbMATH Open1285.68046arXiv1003.0588OpenAlexW3123161773MaRDI QIDQ3569735FDOQ3569735

Authors: Anahí Gajardo, Pierre Guillon 

Publication date: 22 June 2010

Published in: Computer Science – Theory and Applications (Search for Journal in Brave)

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

Full work available at URL: https://arxiv.org/abs/1003.0588

Recommendations

• Automates et codes zigzag
• scientific article; zbMATH DE number 4083572
• Involutory Turing machines
• Turing machines as clocks, rulers and randomizers
• scientific article; zbMATH DE number 3924875
• scientific article; zbMATH DE number 7589250
• Turing machines and bimachines
• scientific article; zbMATH DE number 1161355

zbMATH Keywords

discrete dynamical systemsformal languagesTuring machinessubshifts

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Symbolic dynamics (37B10)

Cited In (8)

• The Group of Reversible Turing Machines
• The Transitivity Problem of Turing Machines
• Realtime subshifts
• A small minimal aperiodic reversible Turing machine
• Topological mixing notions on Turing machine dynamical systems
• One head machines from a symbolic approach
• Undecidability of the Surjectivity of the Subshift Associated to a Turing Machine
• On relations between properties in transitive Turing machines

This page was built for publication: Zigzags in Turing Machines

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3569735)