A concrete view of Rule 110 computation

MaRDI QIDQ5145148zbMATH OpenFDO

Authors Matthew Cook

Publication date 20 January 2021

Full work available at URL https://arxiv.org/abs/0906.3248, http://eptcs.web.cse.unsw.edu.au/paper.cgi?CSP08.4

Mathematics Subject Classification ID

Thue and Post systems, etc. (03D03) Classical models of computation (Turing machines, etc.) (68Q04) Cellular automata (computational aspects) (68Q80)

Recommendations

• P-completeness of Cellular Automaton Rule 110
• The complexity of small universal Turing machines: A survey
• The Complexity of Small Universal Turing Machines: A Survey
• The Complexity of Small Universal Turing Machines
• Universality in elementary cellular automata

Cited in

(9)

• An automaton group with undecidable order and Engel problems
• Universality in infinite Petri nets
• Reproducing the cyclic tag system developed by Matthew Cook with Rule 110 using the phases \(f_{i_-}1\)
• scientific article; zbMATH DE number 3848616 (Why is no real title available?)
• Determining a regular language by glider-based structures calles phases f_i\_1 in Rule 110
• P-completeness of Cellular Automaton Rule 110
• Impartial games emulating one-dimensional cellular automata and undecidability
• scientific article; zbMATH DE number 5244527 (Why is no real title available?)
• Elementary cellular automaton Rule 110 explained as a block substitution system. Rule 110 as a block substitution system

This page was built for publication: A concrete view of Rule 110 computation

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