arxiv: 2604.14966 · v1 · submitted 2026-04-16 · 🌊 nlin.CG · cs.FL

Recognition: unknown

Measuring the Computational Power of Finite Patches of Cellular Automata

Attila Egri-Nagy, Chrystopher L. Nehaniv

Pith reviewed 2026-05-10 08:45 UTC · model grok-4.3

classification 🌊 nlin.CG cs.FL

keywords cellular automatatransformation semigroupsConway's Game of Lifecomputational powerhierarchical decompositionmacro-micro statesdiscrete dynamical systemsmorphic images

0 comments

The pith

Finite patches of Conway's Game of Life convert into transformation semigroups that capture both evolution and interactive operations.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes a method for assigning an algebraic structure to a finite patch of a cellular automaton by mapping it to a transformation semigroup. This structure encodes the time evolution rule together with all possible external inputs, turning the patch into a programmable device whose elements can be composed. Hierarchical decompositions are then applied to the semigroup using macro-micro state partitions and morphic image approximations to handle the large global state space without full enumeration. A sympathetic reader would care because the approach gives a concrete, algebraically tractable measure of what computations any given finite region can actually perform. The same construction works for any discrete dynamical system, not only cellular automata.

Core claim

We convert a small patch of Conway's Game of Life into a transformation semigroup. The conversion captures not only time evolution but also interactive operations. In this way, the cellular automaton becomes directly programmable. Once this measurement is made, we apply hierarchical decompositions to the resulting algebraic object as a way of understanding it. These decompositions are based on a macro/micro-state division inspired by statistical mechanics. However, cellular automata have a large number of global states. Therefore, we focus on partitioning the state space and creating morphic images approximations that can serve as macro-level descriptions. The methods developed here are not

What carries the argument

The transformation semigroup obtained by treating every possible input sequence as a transformation on the set of patch configurations, thereby encoding both the deterministic update rule and all interactive operations as semigroup elements.

If this is right

Any finite patch of a cellular automaton acquires an explicit algebraic measure of its computational capacity that includes user interactions.
Macro-level descriptions become obtainable through state-space partitions and morphic images without enumerating the full exponential number of global configurations.
The cellular automaton patch can be treated as a programmable object by composing semigroup elements that correspond to chosen input sequences.
The same algebraic measurement and decomposition technique extends directly to arbitrary discrete dynamical systems.
Hierarchical decompositions reveal layered structure in the computational behavior that would otherwise remain hidden in the raw transition table.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Patches whose derived semigroups contain particular algebraic features such as regular elements or certain subsemigroups could be systematically selected for embedding logic gates or memory.
The macro-micro decomposition might be iterated to produce multi-scale approximations whose accuracy can be quantified by the size of the kernel of the morphic image map.
Comparing the semigroups of patches with different boundary conditions could quantify how much external interaction is required to achieve a given computational task.
The method supplies a route to classify the computational complexity of local regions in cellular automata by the algebraic invariants of their transformation semigroups.

Load-bearing premise

That representing the cellular automaton patch as a transformation semigroup accurately measures its computational power and that the macro-micro hierarchical decompositions yield valid approximations despite the large global state space.

What would settle it

A concrete counter-example in which a computation that is possible by direct simulation on the cellular automaton patch cannot be realized as any composition of transformations in the derived semigroup.

Figures

Figures reproduced from arXiv: 2604.14966 by Attila Egri-Nagy, Chrystopher L. Nehaniv.

**Figure 2.** Figure 2: Wide glider on a 4 × 4 toroidal patch. Time proceeds from left to right. This configuration yields a 4-cycle in the state space, a copy of Z4. The glider would continue on longer stripes of 4 cells [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗

**Figure 3.** Figure 3: A cycle of length 8 on the toroidal 4 × 4 patch. The configurations are symmetric. Spatial boundaries In theory, we can consider cellular automata virtually infinite. In contrast, when working with small patches the boundaries and how we deal with them make decisive differences. We consider finite boundaries, denoted by □, and toroidal boundaries, denoted by ⟳. One has to be careful with the toroidal for… view at source ↗

**Figure 4.** Figure 4: The state congruence class of the 4 stages of the wide glider (98 configurations). In other words, these configurations [PITH_FULL_IMAGE:figures/full_fig_p006_4.png] view at source ↗

read the original abstract

Computational power can be measured by assigning an algebraic structure to a computational device. Here, we convert a small patch of Conway's Game of Life into a transformation semigroup. The conversion captures not only time evolution but also interactive operations. In this way, the cellular automaton becomes directly programmable. Once this measurement is made, we apply hierarchical decompositions to the resulting algebraic object as a way of understanding it. These decompositions are based on a macro/micro-state division inspired by statistical mechanics. However, cellular automata have a large number of global states. Therefore, we focus on partitioning the state space and creating morphic images approximations that can serve as macro-level descriptions. The methods developed here are not limited to cellular automata; they apply more generally to discrete dynamical systems.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

They convert finite CA patches to transformation semigroups with interactive ops and hierarchical decompositions, but the morphic approximations risk losing distinctions in the transformations.

read the letter

The main takeaway is that this work turns small patches of Conway's Game of Life into transformation semigroups whose generators cover both the global evolution and added interactive operations, then decomposes the result using macro/micro partitions and morphic images. The claim is that this setup measures computational power and makes the automaton programmable in an algebraic sense. The approach extends standard transformation semigroup techniques to cellular automata in a direct way, and the statistical-mechanics-inspired decomposition is a coherent way to handle the large state space without just brute-forcing everything. That part is worth noting as a concrete bridge between algebraic automata theory and discrete dynamical systems. The methods are also framed as applying more broadly, which keeps the scope reasonable. The central soft spot is exactly the one the stress test flags. Morphic images and state partitions can identify distinct transformations that differ on the original states, which would shrink the effective semigroup and change the reported decomposition length or power measure. The abstract flags the need for approximations due to exponential state growth but gives no explicit criterion or check that the quotients preserve the distinguishing action of the generators. Without that, the numerical or structural results on computational power rest on an unverified assumption. No circularity shows up, and the construction does not appear to invent new entities or hide free parameters. The paper is aimed at people already comfortable with semigroup decompositions who work on formal measures of computation in automata or nonlinear systems. A reader who knows the Krohn-Rhodes theorem and related tools would see the most value and could judge whether the approximations hold up in the full constructions. It deserves peer review because the idea is grounded in existing theory and the gaps are fixable with more detail on the examples and preservation properties rather than fatal to the whole approach.

Referee Report

2 major / 2 minor

Summary. The manuscript proposes measuring the computational power of finite patches of cellular automata (e.g., Conway's Game of Life) by converting them into transformation semigroups whose generators encode both the global evolution map and additional interactive operations, thereby rendering the CA 'directly programmable.' Hierarchical decompositions based on macro/micro-state partitions (inspired by statistical mechanics) are then applied, with morphic-image approximations used to handle the exponential global state space; the methods are asserted to generalize to other discrete dynamical systems.

Significance. If the semigroup conversion faithfully captures interactive dynamics and the morphic approximations preserve the distinguishing actions of the generators, the framework would supply a novel algebraic metric for computational capability in CA patches, potentially enabling systematic decomposition and comparison across dynamical systems. The absence of free parameters and the grounding in standard transformation-semigroup theory are strengths, but the approach requires concrete verification to realize this potential.

major comments (2)

[Abstract and morphic-image construction] Abstract (paragraph on morphic images): the central claim that morphic-image approximations yield valid macro-level descriptions of computational power rests on the unproven assumption that the chosen partitions preserve the semigroup action on states. Homomorphic images can identify distinct transformations that differ on the original state space; without a preservation criterion or explicit check that the macro generators retain the same distinguishing power as the micro-level object, the reported decomposition length and power measure may be systematically underestimated.
[Hierarchical decompositions] Section on hierarchical decompositions: no concrete example is supplied showing the full pipeline (patch to semigroup generators to macro/micro decomposition) for even a 2x2 or 3x3 Life patch, nor is there an error analysis or comparison against the exact (unapproximated) semigroup. This gap is load-bearing because the abstract acknowledges the exponential state-space barrier yet provides no verification that the approximations do not collapse the very computational distinctions the method aims to measure.

minor comments (2)

[Semigroup conversion] Notation for the transformation semigroup and its generators is introduced without an explicit small example or diagram; adding one would clarify how interactive operations are encoded as additional generators beyond the global map.
[Results] The manuscript would benefit from a short table comparing the decomposition length or generator count for the approximated versus (where feasible) exact semigroup on a toy patch.

Circularity Check

0 steps flagged

No significant circularity in the algebraic construction

full rationale

The paper converts a finite CA patch into a transformation semigroup whose generators encode the global evolution map together with interactive operations, then applies hierarchical macro/micro decompositions and morphic-image approximations to manage state-space size. This chain relies on standard transformation-semigroup constructions and the Krohn-Rhodes-style decomposition framework applied externally to the CA; no equation or definition is shown to be equivalent to its own input by construction, no fitted parameter is relabeled as a prediction, and no load-bearing premise collapses to a self-citation whose validity is internal to the present work. The approximations are explicitly acknowledged as lossy and are not used to redefine the original semigroup or the claimed measure of computational power.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests primarily on the domain assumption that the transformation semigroup faithfully captures computational power via time evolution and interactions, with no free parameters or invented entities explicitly introduced in the abstract.

axioms (2)

domain assumption The transformation semigroup representation accurately measures the computational power of the CA patch by capturing time evolution and interactive operations.
This is the core premise stated in the abstract for why the conversion makes the CA directly programmable.
domain assumption Hierarchical decompositions based on macro/micro-state division provide meaningful approximations for understanding the system despite large state spaces.
Invoked to justify focusing on partitioning the state space and creating morphic images.

pith-pipeline@v0.9.0 · 5425 in / 1344 out tokens · 40453 ms · 2026-05-10T08:45:57.146801+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

12 extracted references

[1]

D., and P ´eresse, Y

East, J., Egri-Nagy, A., Mitchell, J. D., and P ´eresse, Y . (2019). Computing finite semigroups.Journal of Symbolic Computa- tion, 92:110–155

2019
[2]

Egri-Nagy, A. (2017). Finite computational structures and imple- mentations: Semigroups and morphic relations.International Journal of Networking and Computing, 7(2):318–335

2017
[3]

and Nehaniv, C

Egri-Nagy, A. and Nehaniv, C. L. (2024). From relation to emula- tion and interpretation: Computer algebra implementation of the covering lemma for finite transformation semigroups. In

2024
[4]

and Nehaniv, C

Egri-Nagy, A. and Nehaniv, C. L. (2025). The attractor-cycle nota- tion for finite transformations. In Kilgour, D. M., Kunze, H., Figure 4: The state congruence class of the 4 stages of the wide glider (98 configurations). In other words, these configurations form the smallest macro state that contains left-to-right glider. An open question is why precise...

2025
[5]

and Wegner, P

Goldin, D. and Wegner, P. (2008). The interactive nature of com- puting: Refuting the strong Church–Turing thesis.Minds and Machines, 18(1):17–38

2008
[6]

Q., Smolka, S

Goldin, D. Q., Smolka, S. A., Attie, P. C., and Sonderegger, E. L. (2004). Turing machines, transition systems, and interaction. Information and Computation, 194(2):101–128

2004
[7]

M., Conway, J

Izhikevich, E. M., Conway, J. H., and Seth, A. (2015). Game of life.Scholarpedia, 10(6):1816

2015
[8]

and Greene, D

Johnston, N. and Greene, D. (2022).Conway’s Game of Life: Mathematics and Construction.conwaylife.com

2022
[9]

(2013).Introduction to Theory of Computation 3rd Edi- tion

Sipser, M. (2013).Introduction to Theory of Computation 3rd Edi- tion. Cengage Learning

2013
[10]

(2025).Forty-Four Esolangs: The Art of Esoteric Code

Temkin, D. (2025).Forty-Four Esolangs: The Art of Esoteric Code. Hardcopy. MIT Press

2025
[11]

Wainwright, R. T. (1974). Life is universal! InProceedings of the 7th Conference on Winter Simulation - Volume 2, WSC ’74, page 449–459. Winter Simulation Conference

1974
[12]

Wegner, P. (1997). Why interaction is more powerful than algo- rithms.Communications of the ACM, 40(5):80–91

1997