Pith. sign in

REVIEW 4 major objections 5 minor 25 references

Frequency-Histogram Coarse Graining in Elementary Cellular Automata and 2D CA

T0 review · 4 major / 5 minor · reviewed 2026-08-15 · deepseek-v4-flash

Pith's one-line read Frequency-histogram coarse graining compresses cellular automata space-time diagrams and highlights rare, computation-like structures across all 88 elementary rules and Game of Life.

desk verdict The core claim of a systematic FHCG atlas of all 88 ECA rules is not supported by the appendix, which repeats Rule 50 and Rule 126 for most tables, leaving only a few plausible examples and an unvalidated method. read the letter →

arxiv 2507.18674 v1 pith:FMGLTSQ6 submitted 2025-07-24 nlin.CG cs.FL

classification nlin.CGcs.FL MSC 37B1568Q80
keywords CellularAutomataCoarseGrainingFrequencyHistogramElementaryGameofLifeEmergentComputationComplexityArtificial
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper claims that a cheap pre-processing step—counting how often every small block of cells occurs in a cellular automaton's space-time diagram and thresholding at those frequencies—can compress the diagram into a binary mask that highlights rare, computationally relevant events while discarding repetitive background. The authors apply this frequency-histogram coarse graining to all 88 minimally distinct elementary cellular automata, to the two-dimensional Game of Life, and to an evolved multi-neighborhood rule, and publish the full visual atlas. They report that hidden structures become visible for chaotic and complex rules, that gliders in Game of Life collapse into compact markers of where computation is happening, and that the same idea can be applied recursively to study a system at multiple scales. The larger claim is that such coarse-graining makes emergent complexity easier to locate and quantify in large-scale systems, which could eventually guide evolution or learning toward more open-ended, adaptive behavior.

What carries the argument

The central object is the frequency histogram of fixed-size blocks ('supercells') over a single CA space-time diagram. For a chosen block size, the method counts each block pattern's occurrence probability $p_i$, builds the sorted list of thresholds $p_i + \delta$ with $\delta = 0.005$, and maps each block to 1 if its probability is below the active threshold and 0 otherwise; applying the thresholds in increasing order produces a ladder of progressively less restrictive coarse-grained views. This frequency-thresholding step is the whole mechanism: no rule-specific parameters are needed in 1D, and the rare blocks that survive low thresholds are identified with the particles, gliders, and other localized structures that computational-mechanics analyses treat as the carriers of computation.

What would settle it

Run the same ECA rule (say Rule 110) from many different random seeds and compare the FHCG masks: if two seeds produce similar raw dynamics but the highlighted rare blocks differ drastically, or if varying the block size or $\delta$ makes the extracted structures appear and vanish, the central claim that the method reveals intrinsic computation would be undercut.

Watch

Extended reading notes

Core claim

On the paper's own terms, the discovery is that frequency-histogram coarse graining (FHCG) effectively compresses cellular automata representations while highlighting rare events, making it easier to study emergent behaviors and their complexity. Concretely, the paper shows that when space-time diagrams are cut into small supercells (2×1 blocks in one dimension, 2×2 in two dimensions), the occurrence probabilities of block types form a histogram whose tails correspond to the rare structures that carry computation; thresholds placed just above each observed probability separate those rare blocks from the frequent background. The authors demonstrate this across the 88 minimum-equivalence ECA rules, where rules such as 18, 30, 90, and 110 reveal hidden structures, rule 54 exposes diagonal particles, and periodic class-II rules have their background filtered away, and in two dimensions where Game of Life gliders and other emergent structures remain locatable in a lower-dimensional, coarser image.

Load-bearing premise

The load-bearing premise is that the block frequencies measured in one 100×100 run from a single random initialization are stable enough to tell meaningful rare computation apart from mere background, and that the results do not hinge on the chosen block size, the offset $\delta = 0.005$, the simulation length, or the handpicked 2D thresholds.

Editorial extensions

If this is right

  • Any one-dimensional CA rule can be turned into a hierarchy of binary masks, one per threshold, without hand-tuning, because the thresholds are read off the histogram itself.
  • The 88-rule atlas lets one see which rules concentrate rare blocks into localized, particle-like structures and which spread them diffusely.
  • In 2D, FHCG compresses gliders and other Game of Life structures into compact shapes while preserving where the action is, so structure detection can be run on the coarse image.
  • Recursive application of FHCG could yield a scale-space description of a CA, letting the same tool track emergent behavior from fine to coarse levels.
  • If the method scales to neural or continuous CA, it could serve as a metric to guide evolution toward systems with more rare-event structure.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Because thresholds are computed from the same diagram they are applied to, 'rare' is defined per-run; an immediate test would be to check whether the coarse-grained masks agree across random seeds, block sizes, and simulation lengths before using the method as a general complexity probe.
  • The handpicked 2D thresholds (0.011 for Game of Life, 0.025 for the evolved rule) hint that the automatic delta-based threshold may be too naive in higher dimensions; a histogram-gap or significance criterion could make the method fully parameter-free and more robust.
  • A natural extension beyond the paper is to use the density or persistence of rare blocks under FHCG as a fitness function in an evolutionary search, and to test whether selection for that objective actually produces more open-ended behavior rather than simply more noise.
  • The link to artificial general intelligence is speculative, but the concrete, testable residue is that FHCG provides an inexpensive way to filter space-time diagrams before computing more expensive complexity measures.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 5 minor

Summary. The paper proposes Frequency-Histogram Coarse Graining (FHCG), a dimensionality-reduction method for cellular automaton space-time diagrams: fixed-size blocks are counted over a run, a threshold is derived from the block-frequency histogram, and rare blocks are highlighted in a coarsened representation. The authors apply FHCG to selected Elementary Cellular Automata (ECA), to the Game of Life, and to one evolved MNCA rule, and they claim to provide a systematic atlas of all 88 minimum-equivalent ECA rules in the appendix, with an interactive companion website. The main stated purpose is to make emergent computational structures (e.g., gliders, particles) easier to identify and to use such identification as a step toward open-ended evolution in artificial intelligence systems.

Significance. If the claimed exhaustive atlas and the interpretive link between rare blocks and emergent computation were fully supported, the paper would offer a simple and cheap visualization tool for locating candidate computational structures in CA space-time diagrams, with potential value for exploratory studies of artificial life and neural CA. The paper has useful ingredients: the method is easy to implement, the code and interactive portal are promised at public links, and the selected examples (Rule 30, Rule 110, Game of Life gliders) are visually suggestive as illustrations of the procedure. However, the central evidence for the paper's main deliverable—the "entire exploration" of the 88 ECA rules—is not present in the submitted artifact, and the core interpretive claim that rare blocks correspond to emergent computation is never validated against any external benchmark or against known particle/domain decompositions. As submitted, the contribution is an unverified methodology demonstration rather than a systematic study.

major comments (4)
  1. [Appendix (Tables 42–61 and 64–88)] The appendix does not contain the claimed systematic investigation of the 88 minimum-equivalent ECA rules. Tables 42–61 are all captioned "FHCG plots for ECA Rule 50" and Tables 64–88 are all captioned "FHCG plots for ECA Rule 126"; between these runs only Rule 110 (Table 62) and Rule 122 (Table 63) appear. The Abstract and the Proposed Methods section promise the entire exploration of coarse graining for the full ECA space, and the Appendix text states "one rule per page," but roughly half the appendix repeats two rule labels. The companion website link does not cure this defect, because the manuscript explicitly identifies the Appendix as the full results and does not document the exact parameters, seeds, or code used to generate any external dataset. This is a load-bearing gap: the systematic atlas is the paper's central deliverable, and it is not verifiable from the submitted manuscript.
  2. [Algorithm 1 and Proposed Methods] The thresholds are derived from the same space-time diagram to which they are applied: Algorithm 1 collects all blocks, computes their probabilities, and sets each threshold to a sorted probability plus δ=0.005. Thus any block whose probability falls below a chosen threshold is "rare" by construction, and the coarse-grained output is guaranteed to highlight the least frequent blocks of that single run. The paper never validates that these rare blocks correspond to particles, gliders, domains, or other structures of interest; it only asserts this for selected examples. A concrete fix would be to compare the highlighted regions with known particle/domain decompositions for rules such as 54 and 110 (e.g., the Hanson–Crutchfield analysis cited as [22]) and to report how the identified structures change with random seed, δ, block size, lattice size, boundary conditions, and simulation length.
  3. [Tables 89–90 (2D results)] The two-dimensional thresholds are explicitly handpicked: Table 89 states "chosen handpicked threshold for FHCG-Evo-MNCA is 0.011" and Table 90 states a handpicked threshold of 0.025. Unlike the 1D case, no automatic thresholding procedure is described for 2D, and no criterion is given for selecting these two values. The 2D results are therefore demonstrations rather than part of a systematic study, yet they are used in the Discussion to support the claim that FHCG preserves gliders and other computational structures in the Game of Life. Sensitivity of the 2D output to the threshold choice is not reported.
  4. [Experimental protocol (Proposed Methods and Appendix preamble)] The experimental protocol is under-specified for reproducibility. The appendix states a CA size of 100 cells and 100 time steps, but it does not state the boundary condition (periodic, fixed, or null), the random seed, or the precise initialization rule (e.g., independent Bernoulli draws with the stated percentages). Because the thresholds are computed from a single run, these details directly affect every histogram and every coarse-grained output in the appendix. Without them, the numerical thresholds listed in the tables (e.g., Threshold 1: 0.0066 in Table 1) cannot be reproduced or checked.
minor comments (5)
  1. [Algorithm 1 and text (process_FHCG)] There is an internal inconsistency in the thresholding rule: Algorithm 1 defines G(i) = 0 if pi ≥ α and G(i) = 1 if pi < α, whereas the step-by-step description of process_FHCG says that "values less than or equal to the threshold are set to 1 and others to 0." Please harmonize the two definitions and specify which side of the threshold is highlighted.
  2. [Algorithm 1] The pseudocode appears to generate one threshold per unique probability (the loop "foreach pi in unique_probabilities" adds pi + δ), yet the text and figures consistently describe three thresholds. Please clarify how the number of displayed thresholds is selected and why some rules show only one or two.
  3. [Figure 2] Several panels in Figure 2 are labeled "(e)" (e.g., Rule 90, Rule 54, Rule 57), which makes the panel references in the caption ambiguous; the panel labels should be corrected to a single sequence.
  4. [Throughout] There are several typographical errors, including "coase-graining" in the Related Work section, "evole" in the Cellular Automata background, and "emerge of a more general artificial intelligence" in the Abstract; these should be corrected.
  5. [References and links] The manuscript relies on external URLs for code and the appendix PDF, but it does not state the software versions or the exact commit/version of the repository. For an experimental paper whose main evidence is a corpus of figures, please include versioned code and, if possible, the generated data files in the submission.

Circularity Check

1 steps flagged · score 4.0 of 10

Rare-event highlighting is true by construction; the claimed all-88 ECA atlas is not present in the Appendix; no load-bearing self-citation.

  1. self definitional [Algorithm 1; Proposed Methods, process_FHCG step 4; Discussion of Results and Conclusion]
    "G(i) = ( 0, if pi ≥ α ; 1, if pi < α ). ... For each threshold, a modified grid is created where values less than or equal to the threshold are set to 1 and others to 0. ... Our method of FHCG effectively compresses the cellular automata representations while highlighting rare events"

    The algorithm sets exactly the blocks with empirical frequency below a threshold to foreground (1), and the paper's stated outcome is that FHCG 'highlights rare events.' A block is highlighted iff its frequency is below the threshold, so 'rare' is defined by the threshold and the highlighting is the thresholding operation itself. No independent notion of rarity or emergence is involved. The further claim that the highlighted blocks correspond to emergent computation or particles is a visual interpretation, not a derived result; thresholds are computed from the same space-time diagram to which they are applied.

full rationale

The method is a direct application of the external FHCG approach of Cisneros et al. [9] with automatic thresholds, and there is no load-bearing self-citation chain or imported uniqueness theorem. The only circular element is the self-definitional labeling of below-threshold blocks as 'rare events,' which is a true-by-construction description rather than an empirical prediction. Separately, the claimed systematic deliverable is missing: the Appendix tables 42–61 all repeat 'ECA Rule 50' and tables 64–88 all repeat 'ECA Rule 126,' so the submitted PDF does not contain the advertised exploration of all 88 minimum-equivalent ECA rules. That is a missing-support/correctness problem, not a circularity. Overall the derivation chain reduces only in the trivial 'rare = below threshold' sense, while the interpretive claims about emergent behavior remain unvalidated but not circular.

Assumptions & free parameters 5 free parameters · 4 assumptions · 0 invented entities

The method depends on several hand-chosen values: the block size, the offset delta, the simulation window, the initialization densities, and for the 2D cases explicitly handpicked thresholds. The most consequential assumption is that a single run's block-frequency histogram separates computation from background, which is a domain assumption built into the method rather than something the paper demonstrates.

free parameters (5)
  • delta (threshold offset) = 0.005
    Added to each block probability to form the automatic thresholds; chosen by hand with no sensitivity analysis.
  • block size = 2x1 for 1D CA, 2x2 for 2D CA
    The coarse-graining grain is assumed to be optimal or at least useful, but no other sizes are tested.
  • simulation size and length = grid size 100, 100 steps
    Every ECA example uses a 100 by 100 space-time window; the paper does not test stability with respect to these dimensions.
  • initial densities = 1%, 20%, 50%
    Three initialization densities are used; the choice is arbitrary and only one random configuration is shown per density.
  • handpicked 2D thresholds = 0.011 for Game of Life, 0.025 for evolved MNCA
    The paper explicitly states these are handpicked for the 2D examples, which means the filtering choice is tuned to produce the shown result.
assumptions (4)
  • standard math The 88 Wolfram-equivalence classes faithfully represent the behavior space of elementary cellular automata.
    Used when the paper claims to cover 'the 88 Minimum Equivalent ECA rules'. This is a standard result from Wolfram's classification.
  • domain assumption A single random initial configuration at a given density is representative of a rule's space-time behavior.
    The frequency histogram is computed from one run per density, with no stated random seed and no averaging over seeds.
  • ad hoc to paper Block-frequency below a threshold corresponds to emergent computation, and block-frequency above a threshold corresponds to uninteresting background.
    This is the central interpretive assumption of FHCG. The paper never validates it against an independent definition of computation or particle, such as the computational mechanics framework it cites.
  • domain assumption Binary 2x1 (or 2x2) block coarse graining preserves the structures of interest.
    The chosen block size and binary recoloring are assumed to retain gliders, particles, and other relevant patterns, but this is not tested or quantified.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Frequency-Histogram Coarse Graining in Elementary Cellular Automata and 2D CA." pith.science (2026). https://pith.science/paper/FMGLTSQ6

@misc{pith2026250718674,
  author       = {Pith},
  title        = {Pith review of: Frequency-Histogram Coarse Graining in Elementary Cellular Automata and 2D CA},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/FMGLTSQ6}},
  note         = {Machine review of arXiv:2507.18674}
}
read the original abstract

Cellular automata and other discrete dynamical systems have long been studied as models of emergent complexity. Recently, neural cellular automata have been proposed as models to investigate the emerge of a more general artificial intelligence, thanks to their propensity to support properties such as self-organization, emergence, and open-endedness. However, understanding emergent complexity in large scale systems is an open challenge. How can the important computations leading to emergent complex structures and behaviors be identified? In this work, we systematically investigate a form of dimensionality reduction for 1-dimensional and 2-dimensional cellular automata based on coarse-graining of macrostates into smaller blocks. We discuss selected examples and provide the entire exploration of coarse graining with different filtering levels in the appendix (available also digitally at this link: https://s4nyam.github.io/eca88/). We argue that being able to capture emergent complexity in AI systems may pave the way to open-ended evolution, a plausible path to reach artificial general intelligence.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

25 extracted references · 22 canonical work pages

  1. [9]

    Visualizing compu- tation in large-scale cellular automata

    Cisneros H, Sivic J, and Mikolov T. Visualizing compu- tation in large-scale cellular automata. The 2020 Con- ference on Artificial Life. MIT Press, 2020

  2. [22]

    Computational mechan- ics of cellular automata: An example

    Hanson JE and Crutchfield JP. Computational mechan- ics of cellular automata: An example. Physica D: Non - linear Phenomena 1997; 103:169–89

  3. [1]

    Why open-endedness matters

    Stanley KO. Why open-endedness matters. Artificial life 2019; 25:232–5

  4. [2]

    Perspectives on adaptation in natural and artificial systems

    Booker L. Perspectives on adaptation in natural and artificial systems. Vol. 8. Santa Fe Institute Studies on, 2005

  5. [3]

    AI-GAs: AI-generating algorithms, an alternate paradigm for producing general artificial intelligence

    Clune J. AI-GAs: AI-generating algorithms, an alternate paradigm for producing general artificial intelligence. arXiv preprint arXiv:1905.10985 2019

  6. [4]

    Lenia-biology of artificial life

    Chan BWC. Lenia-biology of artificial life. arXiv preprint arXiv:1812.05433 2018

  7. [5]

    Lenia and Expanded Universe

    Chan BWC. Lenia and Expanded Universe. The 2020 Conference on Artificial Life. MIT Press, 2020

  8. [6]

    Growing neural cellular automata

    Mordvintsev A, Randazzo E, Niklasson E, and Levin M. Growing neural cellular automata. Distill 2020; 5:e23

Show all 25 references
  1. [7]

    Towards self-organized control: Using neural cellular automata to robustly control a cart -pole agent

    Variengien A, Nichele S, Glover T, and Pontes-Filho S. Towards self-organized control: Using neural cellular automata to robustly control a cart -pole agent. arXiv preprint arXiv:2106.15240 2021

  2. [8]

    Self -Organizing Intelligent Matter: A blueprint for an AI generating algorithm

    Gregor K and Besse F. Self -Organizing Intelligent Matter: A blueprint for an AI generating algorithm

  3. [10]

    A new kind of science

    Wolfram S et al. A new kind of science. Vol. 5. Wolfram media Champaign, IL, 2002

  4. [11]

    Universality and complexity in cellular automata

    Wolfram S. Universality and complexity in cellular automata. Physica D: Nonlinear Phenomena 1984; 10:1–35

  5. [12]

    Theory and applications of cellular au - tomata

    Wolfram S. Theory and applications of cellular au - tomata. World Scientific 1986

  6. [13]

    Winning ways for your mathematical plays, volume 4

    Berlekamp ER, Conway JH, and Guy RK. Winning ways for your mathematical plays, volume 4. AK Peters/CRC Press, 2004

  7. [14]

    Understanding Multiple Neighborhood Cellular Automata

    Kraakman B. Understanding Multiple Neighborhood Cellular Automata. 2021

  8. [15]

    Evolving cellular automata with genetic algorithms: A review of recent work

    Mitchell M, Crutchfield JP, Das R, et al. Evolving cellular automata with genetic algorithms: A review of recent work. Proceedings EvCA’96. Vol. 8. Moscow. 1996

  9. [16]

    Compression-based investigation of the dynam- ical properties of cellular automata and other systems

    Zenil H. Compression-based investigation of the dynam- ical properties of cellular automata and other systems. Complex Systems 2010; 19:1–28

  10. [17]

    Measuring Phenotypic Struc - tural Complexity of Artificial Cellular Organisms: Ap - proximation of Kolmogorov Complexity with Lempel-Ziv Compression

    Nichele S and Tufte G. Measuring Phenotypic Struc - tural Complexity of Artificial Cellular Organisms: Ap - proximation of Kolmogorov Complexity with Lempel-Ziv Compression. Innovations in Bio-inspired Computing and Applications: Proceedings of the 4th International Con- feren...

  11. [18]

    Complexity: A guided tour

    Mitchell M. Complexity: A guided tour. Oxford university press, 2009

  12. [19]

    Life in Life

    Bradury P. Life in Life. Youtube. 2012. Available from: https://youtu.be/xP5-iIeKXE8

  13. [20]

    Evolving structures in complex systems

    Cisneros H, Sivic J, and Mikolov T. Evolving structures in complex systems. 2019 IEEE Symposium Series on Computational Intelligence (SSCI). IEEE. 2019 :230–7

  14. [21]

    Capturing emerging complexity in lenia

    Jain S, Shrestha A, and Nichele S. Capturing emerging complexity in lenia. Italian Workshop on Artificial Life and Evolutionary Computation. Springer. 2023 :41–53

  15. [23]

    A study on the composition of elementary cellular automata

    Castillo-Ramirez A and Magaña-Chavez MG. A study on the composition of elementary cellular automata. arXiv preprint arXiv:2305.02947 2023

  16. [24]

    Long- term evolutionary dynamics in heterogeneous cellular automata

    Medernach D, Kowaliw T, Ryan C, and Doursat R. Long- term evolutionary dynamics in heterogeneous cellular automata. Proceedings of the 15th annual conference on Genetic and evolutionary computation. 2013 :231–8 5 Jain and Nichele: Coarse Graining in CA. NMI, 10, 1–96, 2023 App...

  17. [2021]

    arXiv: 2101.07627 [cs.NE]

Pith tools

Reviewed August 15, 2026 · model on record in the stance chip above.