Unraveling simplicity in elementary cellular automata

DOI10.1016/J.TCS.2016.01.004MaRDI QIDQ2628772zbMATH OpenOpenAlexFDO

Authors Pierre Meunier

Publication date 15 July 2016

Published in Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

communication complexityelementary cellular automataintrinsic universality

Mathematics Subject Classification ID

Communication complexity, information complexity (68Q11) Analysis of algorithms and problem complexity (68Q25) Cellular automata (computational aspects) (68Q80)

Abstract: We show that a large number of elementary cellular automata are computationally simple. This work is the first systematic classification of elementary cellular automata based on a formal notion of computational complexity. Thanks to the generality of communication complexity, the perspectives of our method include its application to other natural systems such as neural networks and gene regulatory networks.

Recommendations

• Cellular automata and communication complexity
• A full computation-relevant topological dynamics classification of elementary cellular automata
• Evolution complexity of the elementary cellular automaton rule 18
• scientific article; zbMATH DE number 17562
• Universality in elementary cellular automata

Cites work

• A full computation-relevant topological dynamics classification of elementary cellular automata
• Cellular automata and communication complexity
• Communication Complexity
• Communication complexity and intrinsic universality in cellular automata
• Computational mechanics of cellular automata: an example
• Endomorphisms and automorphisms of the shift dynamical system
• scientific article; zbMATH DE number 4195207 (Why is no real title available?)
• scientific article; zbMATH DE number 3896307 (Why is no real title available?)
• scientific article; zbMATH DE number 3268145 (Why is no real title available?)
• Intrinsic universality in self-assembly
• Intrinsic universality in tile self-assembly requires cooperation
• On factor universality in symbolic spaces
• On local symmetries and universality in cellular automata
• P-completeness of Cellular Automaton Rule 110
• Predicting nonlinear cellular automata quickly by decomposing them into linear ones
• Quantum information theory
• STACS 2005
• The Nilpotency Problem of One-Dimensional Cellular Automata
• The program-size complexity of self-assembled squares (extended abstract)
• The Two-Handed Tile Assembly Model Is Not Intrinsically Universal
• Understanding a Non-trivial Cellular Automaton by Finding Its Simplest Underlying Communication Protocol
• Universality in elementary cellular automata

Cited in

(4)

• The parts and the whole: inquiring how the interaction of simple subsystems generates complexity
• Understanding a Non-trivial Cellular Automaton by Finding Its Simplest Underlying Communication Protocol
• Simplicity via Complexity: Sandboxes, Reading Novalis
• THE CURL OF ELEMENTARY CELLULAR AUTOMATA

This page was built for publication: Unraveling simplicity in elementary cellular automata

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