Complete ergodicity in one-dimensional reversible cellular automata

Naoto Shiraishi; Shinji Takesue

arxiv: 2408.06691 · v2 · submitted 2024-08-13 · 🌊 nlin.CG · cond-mat.stat-mech

Complete ergodicity in one-dimensional reversible cellular automata

Naoto Shiraishi , Shinji Takesue This is my paper

Pith reviewed 2026-05-23 22:29 UTC · model grok-4.3

classification 🌊 nlin.CG cond-mat.stat-mech

keywords cellular automataergodicityreversible CAone-dimensionalboundary-drivenperiodic boundary conditionsstate classificationdynamical systems

0 comments

The pith

All ergodic rules are identified for one-dimensional reversible cellular automata with three to five states.

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

The paper investigates exactly ergodic boundary-driven semi-infinite cellular automata. It establishes a complete classification of ergodic rules for systems with three, four, and five states. Analytic proofs confirm ergodicity for twelve rules with three states and 118320 rules with five states under any ergodic periodic boundary condition. Numerical checks show all remaining rules are non-ergodic under at least one boundary condition. The ergodic rules are grouped into patterns that display different ergodic structures.

Core claim

For cellular automata with three states, exactly twelve rules prove ergodic under any ergodic and periodic boundary condition. For five states, 118320 rules meet the same criterion. All other rules with three to five states fail to be ergodic with some boundary condition. These ergodic cases are classified into several patterns that exhibit a variety of ergodic structures.

What carries the argument

Analytic proofs of ergodicity for selected rules combined with numerical verification of non-ergodicity for the rest, applied under boundary-driven semi-infinite conditions with periodic boundaries.

If this is right

An exhaustive list exists of all ergodic rules for three-state and five-state reversible cellular automata.
Ergodic rules fall into multiple distinct patterns with varying structures.
Non-ergodic rules lose the ergodic property under at least one choice of boundary condition.
The classification covers every rule for these small state numbers.

Where Pith is reading between the lines

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

The same combination of analytic and numerical methods could be applied to rules with six or more states if computation scales.
The identified patterns of ergodic structure may connect to mixing rates in other discrete reversible systems.
Complete ergodicity lists could guide selection of rules for modeling conserved quantities in lattice simulations.

Load-bearing premise

The chosen definitions of ergodicity and the specific ergodic periodic boundary conditions are sufficient to classify every rule exhaustively.

What would settle it

A rule with five states shown to be ergodic under every ergodic periodic boundary condition yet absent from the listed 118320, or one of the listed rules failing ergodicity under a tested condition.

read the original abstract

Exactly ergodicity in boundary-driven semi-infinite cellular automata (CA) are investigated. We establish all the ergodic rules in CA with 3, 4, and 5 states. We analytically prove the ergodicity for 12 rules in 3-state CA and 118320 rules in 5-state CA with any ergodic and periodic boundary condition, and numerically confirm all the other rules non-ergodic with some boundary condition. We classify ergodic rules into several patterns, which exhibit a variety of ergodic structure.

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

The paper gives a full classification of ergodic rules for 3-5 state 1D reversible CA, with analytical proofs for over 100k cases in 5 states and numerics for the rest.

read the letter

The core result is an exhaustive list of which reversible rules with 3, 4, or 5 states are ergodic in their boundary-driven semi-infinite setup. They prove ergodicity analytically for 12 rules in the 3-state case and 118320 in the 5-state case, then use numerics to label the remaining rules non-ergodic under at least one boundary condition. They also group the ergodic ones into patterns showing different structures. That enumeration and the scale of the analytical proofs are the concrete advance; prior work had not produced a complete catalog for these sizes. The proofs themselves look like the strongest part, since they cover a large fraction of the 5-state rules without relying on simulation. The numerical side for the non-ergodic claims is thinner. The space for 5 states grows exponentially, so any finite sampling or orbit check can only test a tiny slice. Without the exact decision criteria or the range of boundary conditions and trajectory lengths used, it is hard to be sure no ergodic rule slipped through as non-ergodic. The abstract does not detail those checks, which leaves the completeness claim resting partly on unstated procedure. This is narrow-scope work aimed at specialists in cellular automata and discrete statistical mechanics. Readers who need a reference list of small-state ergodic rules will find it directly useful if the numerics check out. It is worth sending to referees so they can verify the proof techniques and the numerical protocol in detail.

Referee Report

2 major / 2 minor

Summary. The paper investigates exactly ergodicity in boundary-driven semi-infinite one-dimensional reversible cellular automata. It claims to establish all ergodic rules for 3-, 4-, and 5-state CA by analytically proving ergodicity for 12 rules in the 3-state case and 118320 rules in the 5-state case under any ergodic periodic boundary condition, numerically confirming that all remaining rules are non-ergodic under at least one such boundary condition, and classifying the ergodic rules into patterns that exhibit a variety of ergodic structures.

Significance. If the analytical proofs hold and the numerical classification is shown to be exhaustive, the result would deliver a complete enumeration of ergodic reversible CA in these small state spaces, which is a substantial contribution to the study of ergodicity in discrete dynamical systems. The explicit analytical proofs covering 118320 five-state rules constitute a clear strength, as does the attempt at an exhaustive classification rather than a partial survey.

major comments (2)

[Numerical verification] Numerical verification procedure (implicit in the abstract and the claim of complete classification): the decision criteria for declaring a rule non-ergodic via simulation are not specified. For 5-state automata the configuration space size is 5^N; without an explicit, exhaustive test (e.g., exhaustive enumeration of conserved quantities for small N or a proven mixing-time bound), finite sampling cannot guarantee that every non-ergodic rule has been detected or that slowly mixing ergodic rules have not been misclassified.
[Analytical proofs for 5-state CA] Definition of 'ergodic and periodic boundary condition' used in the analytical proofs: the manuscript must state precisely how these boundary conditions are constructed and verify that the proofs apply uniformly to every such condition without hidden restrictions that would reduce the claimed scope.

minor comments (2)

The abstract should include a concise statement of the precise definition of ergodicity employed (e.g., with respect to which measure or on which space).
Notation for the state alphabet size and the rule numbering convention should be introduced once and used consistently throughout.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and valuable comments on our manuscript. We address each major comment point by point below and agree that clarifications are needed.

read point-by-point responses

Referee: [Numerical verification] Numerical verification procedure (implicit in the abstract and the claim of complete classification): the decision criteria for declaring a rule non-ergodic via simulation are not specified. For 5-state automata the configuration space size is 5^N; without an explicit, exhaustive test (e.g., exhaustive enumeration of conserved quantities for small N or a proven mixing-time bound), finite sampling cannot guarantee that every non-ergodic rule has been detected or that slowly mixing ergodic rules have not been misclassified.

Authors: We agree the numerical criteria require explicit description. Our approach for the remaining rules used exhaustive enumeration of reachable states for small N (up to 8) to detect conserved quantities or restricted components, combined with longer runs for larger N to identify clear invariants. This detects non-ergodicity reliably because non-ergodic rules exhibit detectable invariants even at small N, while slow mixing would still reach the full component in exhaustive small-N checks. We will add a dedicated methods subsection specifying the exact criteria, N ranges, run lengths, and why this avoids misclassification of ergodic rules. revision: yes
Referee: [Analytical proofs for 5-state CA] Definition of 'ergodic and periodic boundary condition' used in the analytical proofs: the manuscript must state precisely how these boundary conditions are constructed and verify that the proofs apply uniformly to every such condition without hidden restrictions that would reduce the claimed scope.

Authors: We will revise Section 2 to provide a precise definition: an ergodic periodic boundary condition is any periodic extension of the local rule that preserves the absence of boundary-induced invariants (i.e., the dynamics on the circle matches the infinite-line ergodicity class). The analytical proofs rely only on local transition properties and global invariants that are independent of the specific periodic length or phase, as long as the BC is ergodic by this definition. We will add a short verification paragraph confirming uniformity across all such BCs with no hidden restrictions. revision: yes

Circularity Check

0 steps flagged

No circularity; classification rests on independent analytical proofs and numerical verification.

full rationale

The paper states it analytically proves ergodicity for 12 rules (3-state) and 118320 rules (5-state) under specified boundary conditions, then numerically confirms the remainder as non-ergodic. No quoted steps reduce a claimed result to a fitted parameter, self-definition, or self-citation chain; the central claims are presented as direct consequences of the proofs and exhaustive checks rather than by construction from the inputs. This is the expected non-circular outcome for a classification paper relying on explicit derivations.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract-only review provides no explicit free parameters, invented entities, or non-standard axioms; the work relies on standard definitions of cellular automata, reversibility, and ergodicity from prior literature.

pith-pipeline@v0.9.0 · 5609 in / 1189 out tokens · 22907 ms · 2026-05-23T22:29:47.418966+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

13 extracted references · 13 canonical work pages

[1]

Boltzmann, Einige allgemeine S¨ atze ¨ uber W¨ armegleichgewicht, Sitzungsberichte der Akademie der Wis- senschaften Mathematisch-Naturwissenschaftliche Klasse, 63, 679 (1871)

L. Boltzmann, Einige allgemeine S¨ atze ¨ uber W¨ armegleichgewicht, Sitzungsberichte der Akademie der Wis- senschaften Mathematisch-Naturwissenschaftliche Klasse, 63, 679 (1871)

work page
[2]

Walters, An Introduction to Ergodic Theory , Springer (1982)

P. Walters, An Introduction to Ergodic Theory , Springer (1982)

work page 1982
[3]

K. E. Petersen, Ergodic theory, Cambridge University Press (1989)

work page 1989
[4]

Rannou, Numerical Study of Discrete Plane Area-Preserving Mappings, Astron

F. Rannou, Numerical Study of Discrete Plane Area-Preserving Mappings, Astron. & Astrophys., 31, 289–301 (1974)

work page 1974
[5]

Sz´ asz ed., Hard Ball Systems and the Lorentz Gas, Springer-Verlag, Heidelberg (2000)

D. Sz´ asz ed., Hard Ball Systems and the Lorentz Gas, Springer-Verlag, Heidelberg (2000)

work page 2000
[6]

A. J. Lichtenberg and M. A. Lieberman, Regular and Chaotic Dynamics 2nd ed., Springer-Verlag, New York (1992)

work page 1992
[7]

Markus and K

L. Markus and K. R. Meyer, Generic Hamiltonian dynamical systems are neither integrable nor ergodic, Memoirs of the Amer. Math. Soc., 144, 1–52 (1978)

work page 1978
[8]

Takesue, Reversible cellular automata and statistical mechanics, Phys

S. Takesue, Reversible cellular automata and statistical mechanics, Phys. Rev. Lett., 59, 2499 (1987)

work page 1987
[9]

Hattori and S

T. Hattori and S. Takesue, Additive Conserved Quantities in Discrete-Time Lattice Dynamical Systems, Physica D, 49, 295–322 (1991)

work page 1991
[10]

Delacourt and N

M. Delacourt and N. Ollinger, Permutive One-Way Cellular Automata and the Finiteness Problem for Automaton Groups . In J. Kari, F. Manea, and I. Petre, (eds) Unveiling Dynamics and Complexity . CiE

work page
[11]

Lecture Notes in Computer Science, 10307 (2017)

work page 2017
[12]

Wolfram, Statistical mechanics of cellular automata, Rev

S. Wolfram, Statistical mechanics of cellular automata, Rev. Mod. Phys., 55, 601 (1983)

work page 1983
[13]

Appendix

Tam´ as Gombor and Bal´ azs Pozsgay, Superintegrable cellular automata and dual unitary gates from Yang- Baxter maps, SciPost Phys.,12, 102 (2022). Appendix. A List of structures of ergodic CA In this Appendix, we list the structures of all rules of ergodic CA. With the knowledge of this structure and the classiﬁcation, one will write down the proof of er...

work page 2022

[1] [1]

Boltzmann, Einige allgemeine S¨ atze ¨ uber W¨ armegleichgewicht, Sitzungsberichte der Akademie der Wis- senschaften Mathematisch-Naturwissenschaftliche Klasse, 63, 679 (1871)

L. Boltzmann, Einige allgemeine S¨ atze ¨ uber W¨ armegleichgewicht, Sitzungsberichte der Akademie der Wis- senschaften Mathematisch-Naturwissenschaftliche Klasse, 63, 679 (1871)

work page

[2] [2]

Walters, An Introduction to Ergodic Theory , Springer (1982)

P. Walters, An Introduction to Ergodic Theory , Springer (1982)

work page 1982

[3] [3]

K. E. Petersen, Ergodic theory, Cambridge University Press (1989)

work page 1989

[4] [4]

Rannou, Numerical Study of Discrete Plane Area-Preserving Mappings, Astron

F. Rannou, Numerical Study of Discrete Plane Area-Preserving Mappings, Astron. & Astrophys., 31, 289–301 (1974)

work page 1974

[5] [5]

Sz´ asz ed., Hard Ball Systems and the Lorentz Gas, Springer-Verlag, Heidelberg (2000)

D. Sz´ asz ed., Hard Ball Systems and the Lorentz Gas, Springer-Verlag, Heidelberg (2000)

work page 2000

[6] [6]

A. J. Lichtenberg and M. A. Lieberman, Regular and Chaotic Dynamics 2nd ed., Springer-Verlag, New York (1992)

work page 1992

[7] [7]

Markus and K

L. Markus and K. R. Meyer, Generic Hamiltonian dynamical systems are neither integrable nor ergodic, Memoirs of the Amer. Math. Soc., 144, 1–52 (1978)

work page 1978

[8] [8]

Takesue, Reversible cellular automata and statistical mechanics, Phys

S. Takesue, Reversible cellular automata and statistical mechanics, Phys. Rev. Lett., 59, 2499 (1987)

work page 1987

[9] [9]

Hattori and S

T. Hattori and S. Takesue, Additive Conserved Quantities in Discrete-Time Lattice Dynamical Systems, Physica D, 49, 295–322 (1991)

work page 1991

[10] [10]

Delacourt and N

M. Delacourt and N. Ollinger, Permutive One-Way Cellular Automata and the Finiteness Problem for Automaton Groups . In J. Kari, F. Manea, and I. Petre, (eds) Unveiling Dynamics and Complexity . CiE

work page

[11] [11]

Lecture Notes in Computer Science, 10307 (2017)

work page 2017

[12] [12]

Wolfram, Statistical mechanics of cellular automata, Rev

S. Wolfram, Statistical mechanics of cellular automata, Rev. Mod. Phys., 55, 601 (1983)

work page 1983

[13] [13]

Appendix

Tam´ as Gombor and Bal´ azs Pozsgay, Superintegrable cellular automata and dual unitary gates from Yang- Baxter maps, SciPost Phys.,12, 102 (2022). Appendix. A List of structures of ergodic CA In this Appendix, we list the structures of all rules of ergodic CA. With the knowledge of this structure and the classiﬁcation, one will write down the proof of er...

work page 2022