Papers

Let $G$ be a group and let $A$ be a set with at least two elements. A lazy cellular automaton over $A^G$ acts as the identity except at the cells where a fixed pattern occurs, where it replaces the central symbol by a fixed different symbol. Let $M(G;A)$ be the submonoid of $\mathrm{CA}(G;A)$ generated by the lazy and the invertible cellular automata. We study when $M(G;A) = \mathrm{CA}(G;A)$. Since no lazy cellular automaton is surjective, every surjective element of $M(G;A)$ is invertible; hence $M(G;A) \neq \mathrm{CA}(G;A)$ whenever $A$ is infinite or $G$ has an element of infinite order. Moreover, if $|A| = 2$ and $G$ has a quotient isomorphic to the Klein four-group $C_2 \times C_2$, then $M(G;A) \neq \mathrm{CA}(G;A)$. For locally finite $G$, and in particular for finite $G$, these are the only obstructions: we prove that $M(G;A) = \mathrm{CA}(G;A)$ if and only if $3 \leq |A| < \infty$, or $|A| = 2$ and $G$ has no quotient isomorphic to $C_2 \times C_2$.

We study geometry-controlled, initial-density-dependent stationary states in exclusion processes with branching-merging structures. We consider two boundary geometries for connecting the parallel branches to the reservoirs: the \(1\)-\(n\)-\(1\) model, in which a single lane branches into \(n\) parallel lanes and then merges back into a single lane, and the \(0\)-\(n\)-\(0\) model, in which particles directly enter and leave the \(n\) parallel lanes. For both models, we derive critical initial densities separating the low-density, shock-wave, and high-density regimes, and show that the theoretical predictions reproduce the phase diagrams and branch-averaged densities observed in simulations. In the \(1\)-\(n\)-\(1\) geometry, the critical initial densities depend on both the number of branches and the lengths of the upstream and downstream single-lane segments, whereas in the \(0\)-\(n\)-\(0\) geometry the corresponding estimates depend only on the number of branches. These results show that initial-condition dependence can arise from the global geometry of a branching-merging exclusion process, even without an explicit friction rule at the merging point.

We find a robust scenario for the emergence of the Golden Ratio (GR) dynamical universality class, characterized by the dynamical exponent $z \equiv \varphi=\frac{1}{2}(1+\sqrt{5})$. Previously, its emergence required fine-tuning of system parameters. Here, the GR universality class appears generically in a wide class of Markov processes as a consequence of a global, circulant symmetry of the flux Jacobian. This symmetry leads to GR universality in systems where the total number of conservation laws is odd and larger than three. We introduce a multilane exclusion process with Bernoulli stationary measure as a minimal, parameter-free model, which features GR universality for all conserved modes, most of which are doubly degenerate. Our predictions, based on mode-coupling theory generalized to treat degenerate conserved modes, are corroborated by large-scale Monte Carlo simulations.

A lazy cellular automaton $\tau:A^G\to A^G$ is determined by a finite neighborhood $S\subseteq G$ containing the group identity $e$, a pattern $p\in A^S$, and a writing symbol $a\in A\setminus\{p(e)\}$: its local rule is equal to the projection to $e$ except when it reads the pattern $p$, in which case it writes $a$. For a nonempty subset $T$ of the fiber $S_a:= p^{-1}(a)$, we introduce compatibility conditions on $p$ along the right translates $St$, $t\in T$. We show that, over every group, the existence of a compatible set is necessary for $\tau$ to be non-idempotent, and that it is also sufficient whenever $st = ts$ for all $t \in S_a$, $s \in S_{p(e)}$. In particular, compatibility characterizes non-idempotence over abelian groups, which reduces deciding idempotence to a search over subsets of $S_a$. Finally, for every dihedral group $D_n$ with $n\geq 4$, we construct an idempotent lazy cellular automaton that admits a compatible set, showing that the commutation hypothesis cannot simply be dropped.

Complex Network (CN) classification requires high-level structural characterizations that are both scale-invariant and computationally efficient. Methods based on Life-Like Network Automata (LLNA) offer an interesting way to extract network descriptors by leveraging emergent temporal patterns without requiring provided features, but their efficacy is bottlenecked by a high-cost combinatorial optimization problem: the selection of the automaton transition rule. While current literature relies on exhaustive searches that are unfeasible for large-scale applications, this work reveals that the rule space is fundamentally structured by a property we term “jaggedness”, that quantifies the resemblance of a LLNA transition function with a sawtooth shape. We demonstrate that this metric acts as a theoretical proxy for chaoticity and sensitivity – properties essential for generating discriminative dynamic behaviors among network categories. Moreover, we introduce a heuristic search strategy that uses jaggedness to guide the rule selection. Experimental results show that our approach achieves classification accuracies within 5% of the global optimum while reducing computational overhead by 90% compared to exhaustive approach. Our findings provide a novel, efficient, framework for optimizing automata-based methods for pattern recognition.

We show that the Turing complete rule 110 in elementary cellular automata can be emulated by alternating three simple symmetric rules in space. As the constituent rules themselves are trivial, this shows that diversity alone can generate emergent phenomena. The rules cannot distinguish left from right, and the chirality of rule 110 is created by their arrangement. Random initial conditions lock on to rule 110 over 90% of the time, explained through the motion of domain walls between desynchronized regions. Adding random noise creates errors that seed domain walls, whose fraction scales with the square root of noise strength, explained through a simple rate equation. This points to a route to complexity through repeated, perturbed units, common in biology, and shows that in cellular automaton models of quantum field theory, broken symmetries such as parity need not be present in the local rules.

We study a real-valued max-plus particle system on a finite periodic lattice. Its three-dimensional fundamental diagram relates the mean flow to two densities: the conserved particle density and a second density defined by a local state function. We prove that the deviation from the diagram tends to zero for arbitrary initial data with all state values in [0,1]. The proof uses two nonnegative local quantities and their evolution relations. For rational initial data with all state values in $[0,1]$, the orbit is eventually periodic, and the fundamental-diagram relation holds exactly on the periodic orbit.

The parity problem in 1D Cellular Automata is a classifier based on a local rule. If the number of ones in a ring of binary cells is odd then the automaton shall converge to all-one (11...11) else to all-zero (00...00). The objective is to find rules that are related to Fatès's Balanced Rule F but use less active neighborhoods (actions). The method is to analyze the effect of each actions and to find a functioning subset of the 12 actions used in rule F. New rules called HA, HB, HC, HF are defined with 10, 6, 4, 8 actions. Rule HC and HF need only three inputs whereas all others need four. The classification time of the rules was determined by averaging over many simulation runs with random initial configurations. It is almost the same for the rules HA and F, and is longer for the rules HB, HC, HF. In addition, the rule HD is defined, which updates three cells in parallel and works faster. In future work, the functioning and performance of the proposed rules should be treated in a more formal way, and related rules (also with different update schemes) could be considered.

Modern AI architectures used to solve visual reasoning tasks typically rely heavily on global connectivity and synchronization. As biological systems demonstrate, though, sophisticated computation can be performed in a more decentralized fashion. In this work, we test the reasoning capabilities of Neural Cellular Automata (NCAs), networks of recurrent cells that use strictly local connectivity and asynchronous updates. NCAs have been extensively studied in artificial life experiments, but it is unclear whether they can perform complex multi-step reasoning. We show that NCAs produce spatio-temporal dynamics capable of solving challenging visual reasoning tasks, including large mazes, Sudoku, and ARC-AGI-1. Furthermore, we provide evidence that NCAs generalize out-of-distribution when running with larger grids, longer rollouts, or parallel trials; and that the latter can be made more efficient via pruning of redundant trajectories. We find that these generalization capabilities depend on training with sample replay and stochastic perturbations, and that stochasticity remains beneficial at test time. Finally, we show that NCAs are robust reasoners capable of dynamically modulating compute to recover efficiently from damage, and that they can scale to solve reasoning in raw pixel space.

We study one-dimensional binary cellular automata with a five-slot radius-two local rule of exact algebraic-normal-form degree two, acting on periodic rings of length n. We prove that every such rule is non-injective whenever 4 | n and n >= 8. The proof begins with the four-cell collapse, where the two extreme formal slots coincide. A structural classification of the resulting four-variable maps separates the 65,472 exactly quadratic rules into 63,456 rules with an immediate ring-four collision and 2,016 exceptional lifts. The latter split into layers of sizes 480 and 1,536. Their remaining finite obligations are represented by 136 parameter-region constructions and 768 per-lift records, respectively. Each certificate supplies differentiating closed walks of lengths 8 and 12 with a common pair-graph base vertex. Concatenation then gives lengths 8a + 12b, which are exactly the multiples of four from eight onward. The load-bearing finite certificate core therefore contains 904 = 136 + 768 independently replayable objects checked by standalone, non-searching programs. The complete checker CLIs additionally reconstruct expected populations and execute coverage, complement, and regression/guard checks; 904 is not a count of total checker operations. Periodic extension also yields full-shift non-injectivity; that consequence is used here only as a corollary.

We introduce causal graph rewriting, a model of computation in which local rules are applied on directed acyclic graphs in an asynchronous manner. The non-determinism arising from asynchrony is disciplined by the oriented edges, which must be understood as both computational dependencies and locality constraints—and are themselves subject to the rewriting. We illustrate the model through two examples: a particle system, and a time-dilation example—reminiscent of general relativity. We study the well-definedness and properties of induced subgraphs and graph composition, which isolate and recombine the region affected by a rewrite. We then study locality with respect to these constructions, showing how a local rewrite preserves positions, borders, and context. Our main result concerns sequential composition: locality extends from single rule applications to arbitrary valid sequences, as any local rule is automatically $*$-local and $*$-extensive. We also formalise and prove the simulation of any one-dimensional cellular automaton.

Which cellular-automaton diagonal families form bases in every finite window? For canonical polynomial lifts of elementary rules, two truth-table bits determine triangularity, and units on the matrix diagonal determine invertibility. Exactly 24 rules give universal binary bases; all remain universal over every modulus. Among triangular binary coordinate maps, the Pascal transform is uniquely characterized by converting OR convolution into pointwise multiplication, while increment becomes strict prefix summation. Explicit inverses and coordinate comparisons distinguish sparsity from evaluation cost. A Rule 30 polynomial construction gives Fibonacci bounds on interpolation order and prime-modulus periods. Exact additive periods anchor a finite census modulo two and three. These results separate all-window basis classification from optimization of a representation and from period patterns observed in finite windows.

The single-seed Rule 30 cone has unbounded least diagonal periods in both directions. On the finite-support side, first contact fixes the least Newton index and an integer polynomial lift gives a Fibonacci ceiling. For reflected Rule 86, a backward map on periodic tail profiles retains the zero boundary and bounds periods independently of transients. At depth $m$, the Rule 30 period is at least $\lfloor m/2\rfloor+1$; for natural Rule 86 cuts through depth $m$, the largest period is at least $\tfrac12\log_2(m+2)$. This proves infinitely many reset/integration period doublings. The physical Rule 135 orbit is a translated complement of Rule 30 after its first step, yielding finite or cofinite supports. A separately initialized auxiliary recurrence has exact index-by-index stabilization. Residue tables and block formulas describe the remaining structure and permit evaluation from supplied representations. Construction and minimization remain separate costs.

The hat and spectre monotiles, discovered in 2023, tile the plane only aperiodically; no cellular automaton dynamics on these tilings has previously been reported. Cellular automata are studied here on patches generated by finite-state transducers, so that every experiment regenerates deterministically from a small record. Within edge-adjacency semi-totalistic rules, exhaustive and evolutionary searches find only mortal travelers: gliders are absent. Guided by a reproduction of the known Penrose-tiling glider, the rule space is extended to vertex neighborhoods and to priority-table rules whose non-quiescent states are visible to neighbors. Evolutionary search then discovers gliders on both monotilings; tracked by a sliding window that regenerates the patch along the flight, they travel one million rings at constant speed and heading. All headings are quantized, to millidegrees, onto a six-spoke compass - the fast axes of the tiling's graph metric. An ablation shows both rule-space extensions are individually necessary. All results replay exactly in an accompanying interactive essay.

We construct the first fully spatially local fault-tolerant quantum computer based on topological codes in fewer than four spatial dimensions. Our construction is a two-dimensional architecture that uses only geometrically local quantum and classical operations, bounded-speed classical communication and computation, and a constant density of quantum and classical resources. The core component is a new time-translation-invariant cellular-automaton decoder for the surface code. This decoder preserves logical information for a time stretched-exponential in the code distance and operates continuously during state injection, stabilizer-state preparation, lattice surgery, and transversal readout. We also prove that every translation-invariant topological Pauli stabilizer code is locally decodable under phenomenological noise.

For every right half we determine the unique left half whose Rule 30 central trace is constant: an alternating tail selected by the leading one of the right half when the initial center is 0, and a single universal checkerboard when it is 1. Every nonzero member of either fiber carries infinitely many ones, so the zero row is the only finite configuration with a constant trace. For support radius w the sharp maximum constant-prefix length is 2*ceil(w/2)+1 when the initial center is 0 and 2*floor(w/2)+2 when it is 1, so the maximum over both is w+2, attained by exactly 2^w configurations for even w and 2^w - 1 for odd w. Hence no column of a nonzero finite Rule 30 orbit is eventually constant.

Multiscale simulation requires coupling physics models that operate at different characteristic length and time scales, because no single method spans the range needed for most problems of interest. Moving to a coarser-grained representation unlocks longer length and time scales, but it discards the microscopic interactions that build morphology. A fine-grained model can be initialized from an arbitrary packing and left to self-assemble into a physically meaningful structure; a lower-resolution model cannot, and must inherit its starting configuration from a higher-fidelity simulation. The length scales accessible to the coarse-grained model are therefore set not by the coarse-grained method itself, but by the largest fine-grained configuration that can be affordably equilibrated. A representative example is the scale-up from particle-based molecular dynamics (MD) to a lattice-based representation such as kinetic Monte Carlo (kMC). In this work, we present a cellular automata (CA) approach for generating arbitrarily large lattice starting configurations. CA is a natural fit for this task: short-ranged local rules drive the evolution of a lattice, and their repeated application gives rise to emergent long-range order, thematically mirroring how short-ranged interactions in MD produce self-assembled morphology. We use a configuration from a higher-fidelity simulation as a training set and learn the CA rules from it via logistic regression. As a proof of principle, we develop these rules for a hydrated anion exchange membrane (AEM), generate new starting configurations, and benchmark their performance in mesoscale kMC simulations against an MD-derived "ground truth." We then demonstrate the ability to generate substantially larger lattices and show that their behavior in kMC is consistent with that of the smaller CA benchmark configurations.

The way numbers are represented strongly influences which arithmetic structures are easy to see. The prime clockwork is a recursively growing discrete dynamical system: a list of autonomous two-hand clocks driven by one common $+1$ signal. No primes or primality labels are supplied. Starting empty, the process appends a clock of period $n$ whenever none already present rings; the primes are generated internally as its growth times. For each installed prime $p$, the seconds reading $R_p$ advances through $0,\ldots,p-1$, and each return to zero increments the minutes reading $M_p$, which counts completed $p$-cycles. The hands use only increment, comparison, reset, and carry, without explicit mod or div operations. At time $n$, $n=pM_p(n)+R_p(n)$. The valuation readout $V_p(n)=\nu_p(n)$ is generated locally: it is zero when the seconds counter is non-zero (silent state) and otherwise (when the p-clock rings) one plus the earlier valuation addressed by the current minutes reading. The valuation vector gives the integer in unique prime-factorized form. Its coordinates add and subtract under multiplication and division, representing every positive rational uniquely; divisibility becomes weak componentwise order, and unique factorization is natural in this representation. Finite seconds arrays form Cartesian-product state spaces whose common orbit visits every joint state once before repeating; this grand cycle is the order-sensitive dynamical counterpart of the Chinese remainder theorem. The same coordinates expose gcd, lcm, perfect powers, Bézout's identity, and Euler's totient. Rational valuation levels reach certain positive algebraic irrationalities, but not algebraic numbers in general.

Continuous cellular automata such as Lenia spontaneously produce lifelike, self-propelling patterns, including the Orbium glider, which travels in a straight line while pulsing through a fixed breathing cycle. Collision-based logic, where moving patterns compute by colliding, is established in discrete cellular automata and continuous physical media. Within continuous cellular automata, computation has so far been trained into the rule rather than emerging from collisions, and whether a fixed-rule automaton like Lenia can support general collision-based computation remains open. This paper constructs an INHIBIT gate from collisions of the Orbium glider. Of the patterns searched across four continuous-CA rule types, the Orbium glider is the only one shown to survive a collision with both copies intact. A control glider deflects a signal glider off its output line, so the output carries a signal only when no control is present. The gate blocks across all twenty-four phases of the breathing cycle and nine integer offsets of the control. Two such gates in series, with one signal line and two controls, compose into an AND-NOT chain, correct on all eight input combinations. By contrast, routing a signal beyond that single chain is undemonstrated. A deflected signal is not restored to a fixed landing position, and no reusable absorber for the surviving gliders was found. The immediate open question for collision-based computation in Lenia therefore narrows from whether a gate exists to whether a deflected signal can be delivered to a downstream gate, the next requirement for composing the gate beyond a single straight chain.

Cellular automata conform a set of computational models which evolve with a reduced set of simple rules, yet still are able to show extremely complex emergent phenomena such as fractals and universal computation. Despite their apparent simplicity, they have shown great potential in simulating natural systems and solving challenging computational tasks such as classification and image generation. Instead of implementing cellular automata purely at the software level, it is desirable to design novel analog computing platforms that physically evolve following the automata's underlying rules, thereby reducing power requirements and latency. Here, we introduce an optical extreme learning machine for the simulation of a wide range of cellular automata. Our system operates in free space, and uses a spatial light modulator to encode the evolution rules of the system, while coherent wave propagation performs the corresponding computations. Our results demonstrate a simple, fully-programmable, cost and power efficient, and easy to build and align platform for the implementation of a wide range of complex computational systems such as elementary cellular automata, Conway's Game of Life, and two-dimensional Turing machines.

Any type of attractor basin (classic-graph) created in DDLab can now be visualised, manipulated, and deconstructed as a drag/drop “interactive state transition graph” (istr-graph). The new istr-graph applies to subtrees, single basins, the basin of attraction field, compression, and all other classic-graph parameters. This is an important update on the pre-existing “interactive basin of attraction field graph” (ibaf-graph) specific to just the complete uncompressed field, but the ibaf-graph is nevertheless retained for some of its unique attributes. These issues are discussed with a focus on the scope and implementation of the new istr-graph.

I explore Conway's Game of Life (GoL) on six composite Archimedean lattices. On the Kagome lattice, on which small gliders and puffers appear particularly frequently across inputs, I use the output of a symmetry-constrained evolutionary search algorithm to construct a novel glider gun. The glider gun comprises four interacting bouncers and stably emits a small glider every 276th generation. Serving as an extension of classical GoL, I also propose cells with a phase degree of freedom and an associated local phase rule, which on the Kagome lattice is demonstrated to host phase-periodic gliders. This enables the possibility of phase-sensitive and interference-based computations.

Using patch-matrix-product methods, we study two reversible three-state interaction-round-a-face cellular automata introduced by Klobas and Prosen [J. Phys. A 55, 094003 (2022)] - the species-preserving and species-flipping rules - and a coherent quantum deformation interpolating between them. Within an explicit translationally invariant ansatz, the two classical rules share a one-parameter family of quasi-local conservation laws with an auxiliary-dimension-three realization. Every regular member is also the first centered logarithmic derivative of an analytic auxiliary-dimension-two family passing through the identity observable. On the closed span of this family and the three elementary local charges, the only nonzero Euler velocities are $\pm\sqrt{3/23}$. Consequently, $\sqrt{3/23}$ is a rigorous lower bound on the maximal Euler speed in any larger conserved sector. For the species-flipping rule, this value agrees with the reported extrapolated value $0.361$ of Klobas and Prosen, strongly supporting completeness of the known sound-active charges. The species-preserving rule admits, in addition, a staggered generating family whose logarithmic derivatives form an infinite tower of strictly local charges. In the quantum deformation, the same algebraic structures yield exact low-bond-dimension invariant states (scar candidates), exponentially long-lived quasi-local quasimodes, and diagonal quasi-local charges that produce a nonzero Mazur bound after projection away from the three elementary local charges.

We introduce Semantic Lenia, an artificial life framework that transforms Large Language Model (LLM) inference from a static optimization problem into a continuous, closed-loop dynamical system. By establishing a non-linear homeostatic feedback loop to dynamically balance semantic attraction and syntactic repulsion, we demonstrate the emergence of “Homeostatic Solitons”-metastable semantic structures that actively resist repetitive crystallization. Our exhaustive parameter sweeps map a critical “Habitable Ridge” where applied steering forces balance the model's intrinsic syntactic inertia. This approach successfully maintains generative trajectories in a numerically sensitive critical regime, triggering profound abductive leaps without structural collapse, and reveals a capacity-dependent scaling trend in the syntactic inertia across different model sizes.

We propose an improved mean-field analysis of cellular automata models of single-lane vehicular traffic. By combining aspects of the Car-Oriented-Mean-Field (COMF) theory and the 2-site cluster method, which have been previously successfully applied to similar models, we aim to capture both short- and long-range correlations more accurately. In contrast to classical mean-field theories, the improved method is well suited for models with inhomogeneous stationary states and able to capture the essential properties of phase separation, e.g. in models with slow-to-start rules. The improved accuracy and new physical insights are illustrated through an application to the VDR model with $v_{\text{max}}=1$.