Tag systems and the complexity of simple programs

DOI10.1007/978-3-662-47221-7_2MaRDI QIDQ5500609zbMATH OpenOpenAlexFDO

Authors Turlough Neary, Damien Woods

Publication date 7 August 2015

Published in Cellular Automata and Discrete Complex Systems (Search for Journal in Brave)

Full work available at URL https://hal.inria.fr/hal-01442479/file/338243_1_En_2_Chapter.pdf

Mathematics Subject Classification ID

Classical models of computation (Turing machines, etc.) (68Q04) Analysis of algorithms and problem complexity (68Q25) Grammars and rewriting systems (68Q42) Cellular automata (computational aspects) (68Q80)

Recommendations

• The complexity of small universal Turing machines: A survey
• The Complexity of Small Universal Turing Machines: A Survey
• Undecidability in binary tag systems and the Post correspondence problem for five pairs of words
• The Complexity of Small Universal Turing Machines
• On the boundaries of solvability and unsolvability in tag systems. Theoretical and experimental results

Cited in

(6)

• Generalized tag systems
• Undecidability in binary tag systems and the Post correspondence problem for five pairs of words
• Study of Limits of Solvability in Tag Systems
• Average-Case Completeness in Tag Systems
• On the boundaries of solvability and unsolvability in tag systems. Theoretical and experimental results
• On the complex behavior of simple tag systems -- an experimental approach

This page was built for publication: Tag systems and the complexity of simple programs

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