P-completeness of Cellular Automaton Rule 110

DOI10.1007/11786986_13MaRDI QIDQ3613755zbMATH OpenOpenAlexFDO

Authors Turlough Neary, Damien Woods

Publication date 12 March 2009

Published in Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/11786986_13

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Cellular automata (computational aspects) (68Q80)

Recommendations

• Universality in elementary cellular automata
• A concrete view of Rule 110 computation
• scientific article; zbMATH DE number 1241089
• The Complexity of Small Universal Turing Machines
• The complexity of small universal Turing machines: A survey

Cited in

(44)

• The complexity of small universal Turing machines: A survey
• On the computational complexity of finite cellular automata
• Parallel computation using active self-assembly
• A one-dimensional physically universal cellular automaton
• Freezing sandpiles and Boolean threshold networks: equivalence and complexity
• On the complexity of asynchronous freezing cellular automata
• The mirage of universality in cellular automata
• On fungal automata
• Emulating cellular automata in chemical reaction-diffusion networks
• On the complexity of two-dimensional signed majority cellular automata
• Tag systems and Collatz-like functions
• Wang's B machines are efficiently universal, as is Hasenjaeger's small universal electromechanical toy
• Unraveling simplicity in elementary cellular automata
• The Complexity of Small Universal Turing Machines: A Survey
• Computational equivalence and classical recursion theory
• Universal Sleptsov net
• Distributed multi-authority attribute-based encryption using cellular automata
• On the Computational Complexity of Spiking Neural P Systems
• scientific article; zbMATH DE number 4058875 (Why is no real title available?)
• scientific article; zbMATH DE number 1241089 (Why is no real title available?)
• Ulam's cellular automaton and Rule 150
• Chaos emerged on the `edge of chaos'
• Nontrivial turmites are Turing-universal
• Computational complexity of the stability problem for elementary cellular automata
• Average-Case Completeness in Tag Systems
• A concrete view of Rule 110 computation
• Parallel Computation Using Active Self-assembly
• Rule set design problems for oritatami systems
• Universality in elementary cellular automata
• Topological chaos of universal elementary cellular automata rule
• Bulking II: Classifications of cellular automata
• Freezing, bounded-change and convergent cellular automata
• Communication complexity meets cellular automata: necessary conditions for intrinsic universality
• Building squares with optimal state complexity in restricted active self-assembly
• Communication complexity and intrinsic universality in cellular automata
• Four states are enough!
• Abstract geometrical computation. IV: Small Turing universal signal machines
• A simple P-complete problem and its language-theoretic representations
• On the complex behavior of simple tag systems -- an experimental approach
• Unpredictability and entanglement in open quantum systems
• On principles of emergent organization
• Symbolic dynamics of cellular automata
• Agent motion planning as block asynchronous cellular automata: pushing, pulling, suplexing, and more
• Elementary cellular automaton Rule 110 explained as a block substitution system. Rule 110 as a block substitution system

This page was built for publication: P-completeness of Cellular Automaton Rule 110

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