Zigzags in Turing Machines

DOI10.1007/978-3-642-13182-0_11MaRDI QIDQ3569735zbMATHOpenAlexFDO

Authors Anahí Gajardo, Pierre Guillon

Publication date 22 June 2010

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

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

zbMATH Keywords

discrete dynamical systemsformal languagesTuring machinessubshifts

Mathematics Subject Classification ID

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

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.

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

Cited in

(9)

• Undecidability of the Surjectivity of the Subshift Associated to a Turing Machine
• One head machines from a symbolic approach
• On relations between properties in transitive Turing machines
• Realtime subshifts
• Topological mixing notions on Turing machine dynamical systems
• A small minimal aperiodic reversible Turing machine
• The transitivity problem of Turing machines
• Distortion in one-head machines and cellular automata
• The group of reversible 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)