Rule Primality, Minimal Generating Sets and Turing-Universality in the Causal Decomposition of Elementary Cellular Automata

New Turing-universality results in Elementary Cellular Automata in recent published paper: "Rule Primality, Minimal Generating Sets and Turing-Universality in the Causal Decomposition of Elementary Cellular Automata" by Jürgen Riedel and Hector Zenil

 

New paper discovers and proves 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. It is introduced a 4-colour Turing-universal cellular automaton that carries the Boolean composition of 2 and 3 ECA rules emulating ECA rule 110 under multi-scale coarse-graining. They 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. They 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.

Source: www.oldcitypublishing.com