Rule primality, minimal generating sets and Turing-universality in the causal decomposition of elementary cellular automata

MaRDI QIDQ5010160zbMATH OpenFDO

Authors Jürgen Riedel, Hector Zenil

Publication date 24 August 2021

Full work available at URL https://arxiv.org/abs/1802.08769, http://www.oldcitypublishing.com/journals/jca-home/jca-issue-contents/jca-volume-13-number-5-6-2018/jca-13-5-6-p-479-497/

zbMATH Keywords

Boolean compositioncausal compositionECA algebraic and group-theoretic propertieselementary cellular automatamulti-scale coarse-grainingrenormalizationTuring universality

Mathematics Subject Classification ID

Dynamical aspects of cellular automata (37B15) Cellular automata (computational aspects) (68Q80)

Abstract: We introduce several concepts such as prime and composite rule, tools and methods for causal composition and decomposition. We discover and prove new universality results in ECA, namely, that the Boolean composition of ECA rules 51 and 118, and 170, 15 and 118 can emulate ECA rule 110 and are thus Turing-universal coupled systems. We construct the 4-colour Turing-universal cellular automaton that carries the Boolean composition of the 2 and 3 ECA rules emulating ECA rule 110 under multi-scale coarse-graining. We find that rules generating the ECA rulespace by Boolean composition are of low complexity and comprise prime rules implementing basic operations that when composed enable complex behaviour. We also found a candidate minimal set with only 38 ECA prime rules---and several other small sets---capable of generating all other (non-trivially symmetric) 88 ECA rules under Boolean composition.

Recommendations

• Universality in elementary cellular automata
• The complexity of small universal Turing machines: A survey
• The Complexity of Small Universal Turing Machines
• scientific article; zbMATH DE number 4195207
• The Complexity of Small Universal Turing Machines: A Survey

Cites work

• Asymptotic behavior and ratios of complexity in cellular automata
• Automorphisms of transition graphs for linear cellular automata
• Compression-based investigation of the dynamical properties of cellular automata and other systems
• scientific article; zbMATH DE number 1818513 (Why is no real title available?)
• Is there a sharp phase transition for deterministic cellular automata?
• Statistical mechanics of cellular automata
• Universality in elementary cellular automata

Cited in

(1)

• Model discovery and discrete inverse problems with cellular automata and Boolean networks

This page was built for publication: Rule primality, minimal generating sets and Turing-universality in the causal decomposition of elementary cellular automata

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