85 citations · 742 across the 80 of their papers we have counts for
5 papers · 1 filter
Rule Primality, Minimal Generating Sets, Turing-Universality and Causal Decomposition in Elementary Cellular Automata
Jürgen Riedel, Hector Zenil
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, n…
Algorithmic Information Dynamics of Persistent Patterns and Colliding Particles in the Game of Life
Hector Zenil, Narsis A. Kiani, Jesper Tegnér
Without loss of generalisation to other systems, including possibly non-deterministic ones, we demonstrate the application of methods drawn from algorithmic information dynamics to…
Computation and Universality: Class IV versus Class III Cellular Automata
Genaro J. Martinez, Juan C. Seck-Tuoh-Mora, Hector Zenil
This paper examines the claim that cellular automata (CA) belonging to Class III (in Wolfram's classification) are capable of (Turing universal) computation. We explore some chaoti…
Asymptotic Behaviour and Ratios of Complexity in Cellular Automata
Hector Zenil
We study the asymptotic behaviour of symbolic computing systems, notably one-dimensional cellular automata (CA), in order to ascertain whether and at what rate the number of comple…
Wolfram's Classification and Computation in Cellular Automata Classes III and IV
Genaro J. Martinez, J. C. Seck-Tuoh-Mora, Hector Zenil
We conduct a brief survey on Wolfram's classification, in particular related to the computing capabilities of Cellular Automata (CA) in Wolfram's classes III and IV. We formulate a…