pith. sign in

arxiv: 2605.22762 · v1 · pith:5XMOBGITnew · submitted 2026-05-21 · 🧮 math.DS

Minimality, transitivity and sensitivity of non-uniform cellular automata

Supreeti Kamilya , Jarkko Kari , Katariina Paturi This is my paper

Pith reviewed 2026-05-22 03:12 UTC · model grok-4.3

classification 🧮 math.DS
keywords non-uniform cellular automataminimalitytransitivitysensitivityodometerdynamical systemssymbolic dynamics
0
0 comments X

The pith

A two-dimensional non-uniform cellular automaton can be minimal and transitive without sensitivity to initial conditions.

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

Standard cellular automata satisfy that transitivity implies sensitivity to initial conditions. The paper examines whether this holds for non-uniform cellular automata, where finitely many different local rules can be assigned to different cells. It constructs a two-dimensional example that is minimal, which forces transitivity, yet fails to be sensitive. The example starts from a nearly uniform odometer on infinite sequences over three symbols, with a rule change only at the first position, then lifts the idea to two dimensions. The authors also prove a positive result: when the assignment of rules across cells is recurrent, transitivity does force sensitivity.

Core claim

The authors construct a two-dimensional non-uniform cellular automaton that is minimal, hence transitive, but not sensitive to initial conditions. The construction relies on an odometer-like system over the space of sequences in {0,1,2}^N that uses a different local rule only at the first cell and remains minimal despite this non-uniformity. They show that recurrent assignments of local rules restore the implication from transitivity to sensitivity.

What carries the argument

The nearly uniform odometer non-uniform cellular automaton on {0,1,2}^N with a modified local rule only at the first cell, extended to two dimensions to produce a minimal but insensitive system.

If this is right

  • Transitivity implies sensitivity when the assignment of local rules is recurrent.
  • Minimality of a non-uniform cellular automaton does not guarantee sensitivity.
  • The classical implication from transitivity to sensitivity is specific to the uniform case.
  • Non-uniformity allows dynamical properties to separate in ways forbidden for ordinary cellular automata.

Where Pith is reading between the lines

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

  • Uniformity of the local rule may be the essential ingredient that links transitivity and sensitivity in one dimension.
  • Similar nearly uniform constructions could separate other properties such as mixing or entropy in non-uniform settings.
  • The result raises the question of which dynamical features survive when uniformity is relaxed only at finitely many or sparsely distributed cells.

Load-bearing premise

The specific odometer construction with a rule change confined to the first cell remains minimal even though it is not sensitive.

What would settle it

An explicit computation showing that the constructed two-dimensional NUCA actually has sensitive dependence on initial conditions, or that the one-dimensional odometer fails to be minimal.

Figures

Figures reproduced from arXiv: 2605.22762 by Jarkko Kari, Katariina Paturi, Supreeti Kamilya.

Figure 1
Figure 1. Figure 1: The evolution of the first ten cells for 18 time steps in the three state odometer. Initially all cells are in state 0. In the following we prove that, for every n ≥ 1, the patterns in the first n cells cycle through all the 3n words in {0, 1, 2} n. This happens regardless of the states to the right, as the neighborhood of the NUCA does not involve any cells to the right of a cell. It follows that the thre… view at source ↗
Figure 2
Figure 2. Figure 2: Two identical sections of trace Tx with only symbols 0 and 1, and a 0 at the beginning of one section in trace Tx+1 and 1 at the beginning of the other. This forces each cell in the sections of trace Tx+1 to have different symbols. Lemma 1. Let x ∈ N, {a, b} = {1, 2}, and let 0 ≤ i ≤ j, k > 0, and i ′ = i + k, j ′ = j + k. Suppose Tx[i, j]#b = 0, Tx[i, j] = Tx[i ′ , j′ ] and {Tx+1(i), Tx+1(i ′ )} = {0, a}.… view at source ↗
Figure 3
Figure 3. Figure 3: Structure and labeling scheme for a period of the trace Tx. We show that then the trace Tx+1 has period 3p where for all i ∈ N, Tx+1(3pi) = 0 and Tx+1[α3i , α′ 3i+1]#1 = Tx+1[β3i+1, β′ 3i+2]#2 = 2n + 1, Tx+1[α3i , α′ 3i+1]#2 = Tx+1[β3i+1, β′ 3i+2]#1 = 0. Suppose for some i ∈ N, Tx+1(3pi) = 0 (and hence Tx(3pi) = 0). This is obvi￾ously true when i = 0. Then Tx+1(3pi+ 1) = 0 and because Tx(A3i) is a 1-block,… view at source ↗
Figure 4
Figure 4. Figure 4: Illustration of the argument for why the period in trace Tx forces the trace Tx+1 to have a similar but longer period. In the trace Tx the coloured blocks labeled with 1 and 2 are 1-blocks and 2-blocks respectively. The numbers below in blue and red (left and right) are the number of 1 and 2 symbols in the denoted section of trace Tx+1 respectively. Then because T0 has a period of this kind of length 3, ev… view at source ↗
Figure 5
Figure 5. Figure 5: (a) A spiral ordering s : N −→ Z 2 . The cell marked grey is the origin s(0) = (0, 0). For every k, the k’th cell along the spiral is the cell s(k). (b) The rule distribution θ of the NUCA: The grey cell uses the local rule g, while cells with an arrow use f with the neighbor in the direction of the arrow [PITH_FULL_IMAGE:figures/full_fig_p010_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Illustration, in dimension d = 1, of the argument for why any cell at the centre of a copy of the rule patters θ|[−nr,nr]d must repeat in the trace after n steps. Any configuration that agrees with c within D will have a trace of period n at cell 0. Then for any pattern xay extending symbol a by nr cells in all directions, after some time some configuration in Cyl(c, D) will have xay at the origin. Any con… view at source ↗
read the original abstract

Every transitive cellular automaton (CA) is sensitive to initial conditions. We study this implication in the more general context of non-uniform cellular automata (NUCA) with finitely many different local update rules assigned to cells. We construct a two-dimensional NUCA that is minimal -- and hence transitive -- but that is not sensitive to initial conditions. The construction is based on an odometer NUCA on $\{0,1,2\}^\mathbb{N}$ which is nearly uniform in the sense that only the first cell uses a different local rule. Then we show that if the assignment of local rules in the cells is recurrent then transitivity implies sensitivity.

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.

Referee Report

2 major / 2 minor

Summary. The manuscript constructs a two-dimensional non-uniform cellular automaton (NUCA) that is minimal (hence transitive) but not sensitive to initial conditions, providing a counterexample to the implication that holds for uniform cellular automata. The construction proceeds by first defining a nearly uniform odometer NUCA on {0,1,2}^N in which only the local rule at the first cell differs from the standard addition-with-carry rule modulo 3, then lifting the example to two dimensions. The paper additionally proves that when the assignment of local rules across cells is recurrent, transitivity does imply sensitivity.

Significance. If the central construction is verified, the result supplies a concrete separation between minimality/transitivity and sensitivity in the NUCA setting, clarifying the boundary between uniform and non-uniform systems. The explicit odometer-based construction and the positive theorem for recurrent rule assignments are strengths that offer testable examples for further work in symbolic dynamics.

major comments (2)
  1. [§3] §3 (one-dimensional construction): the argument that the modified odometer NUCA remains minimal must explicitly verify that altering the local rule only at position 0 preserves orbit density under carry propagation. The product-topology density claim for every initial configuration is load-bearing for the counterexample; without a detailed check that the first-cell modification does not trap orbits in a proper closed invariant subset, the minimality assertion is not yet secured.
  2. [§4] §4 (two-dimensional lift): the passage from the one-dimensional nearly uniform NUCA to the two-dimensional example must confirm that both minimality and the failure of sensitivity survive the product construction. It is unclear from the current exposition whether the boundary modification at the first cell interacts with the second dimension in a way that could restore sensitivity or destroy density.
minor comments (2)
  1. Notation for the local rules (especially the distinction between the standard carry rule and the modified rule at site 0) would benefit from an explicit table or diagram showing the update for a few sample configurations.
  2. A short remark on the precise definition of 'recurrent assignment' used in the positive theorem would improve readability for readers outside the immediate subfield.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading of the manuscript and for identifying points where the exposition of the constructions requires additional detail. We respond to each major comment below.

read point-by-point responses

  1. Referee: [§3] §3 (one-dimensional construction): the argument that the modified odometer NUCA remains minimal must explicitly verify that altering the local rule only at position 0 preserves orbit density under carry propagation. The product-topology density claim for every initial configuration is load-bearing for the counterexample; without a detailed check that the first-cell modification does not trap orbits in a proper closed invariant subset, the minimality assertion is not yet secured.

    Authors: We agree that the minimality argument in §3 would be strengthened by an explicit verification of orbit density after the local-rule modification at position 0. In the revised manuscript we will insert a dedicated lemma that tracks carry propagation explicitly: for any finite initial segment and any target configuration, we exhibit a finite sequence of inputs whose carries reach the modified cell and then propagate to realize the desired finite pattern, thereby showing that no proper closed invariant subset can contain an orbit. This addition will make the density claim fully rigorous without altering the underlying construction. revision: yes

  2. Referee: [§4] §4 (two-dimensional lift): the passage from the one-dimensional nearly uniform NUCA to the two-dimensional example must confirm that both minimality and the failure of sensitivity survive the product construction. It is unclear from the current exposition whether the boundary modification at the first cell interacts with the second dimension in a way that could restore sensitivity or destroy density.

    Authors: We acknowledge that the interaction between the one-dimensional boundary modification and the second coordinate is not spelled out in sufficient detail. In the revision we will add a short subsection that treats the two-dimensional system as a product of the one-dimensional nearly-uniform NUCA with a uniform minimal odometer on the second coordinate. We will prove that (i) minimality is preserved because every finite cylinder in the product can be reached by independently controlling the first coordinate (via the already-established density) and the second coordinate (via its uniform minimality), and (ii) non-sensitivity is inherited because any perturbation that fails to propagate in the first coordinate remains invisible in the product metric, regardless of the uniform dynamics in the second coordinate. This will confirm that the boundary effect does not restore sensitivity. revision: yes

Circularity Check

0 steps flagged

Explicit construction of minimal non-sensitive 2D NUCA is self-contained with no circularity

full rationale

The paper's central result is an explicit construction of a two-dimensional NUCA that is minimal (hence transitive) but not sensitive, built from a nearly uniform odometer on {0,1,2}^N with a modified local rule only at the first cell. Minimality is shown by direct verification that every orbit remains dense in the product topology under carry propagation, and non-sensitivity follows immediately from the boundary modification preserving certain invariant subsets. This is a self-contained mathematical argument with no fitted parameters renamed as predictions, no self-definitional loops, and no load-bearing self-citations that reduce the claim to unverified prior inputs. The subsequent theorem on recurrent rule assignments implying sensitivity from transitivity is likewise proved independently from the construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper relies on standard facts from symbolic dynamics and cellular automata theory to establish minimality and transitivity; no new free parameters or invented entities are introduced in the abstract.

axioms (1)
  • standard math Standard properties of odometers and minimality implying transitivity in symbolic dynamical systems
    Used to conclude that the constructed NUCA is transitive and to separate it from sensitivity.

pith-pipeline@v0.9.0 · 5636 in / 1172 out tokens · 46286 ms · 2026-05-22T03:12:58.174586+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

10 extracted references · 10 canonical work pages

  1. [1]

    Acta Informatica , volume =

    Supreeti Kamilya and Jarkko Kari , title =. Acta Informatica , volume =

    work page

  2. [2]

    Natural Computing , volume =

    Katariina Paturi and Jarkko Kari , title =. Natural Computing , volume =

    work page

  3. [3]

    22nd International Conference on Unconventional Computation and Natural Computation (UCNC 2025) , pages =

    Katariina Paturi , title =. 22nd International Conference on Unconventional Computation and Natural Computation (UCNC 2025) , pages =. 2026 , volume =

    work page 2025

  4. [4]

    The American Mathematical Monthly , volume =

    Bruno Codenotti and Luciano Margara , title =. The American Mathematical Monthly , volume =

    work page

  5. [5]

    Ergodic Theory and Dynamical Systems , author=

    Languages, equicontinuity and attractors in cellular automata , volume=. Ergodic Theory and Dynamical Systems , author=

    work page

  6. [6]

    Myhill, John , journal=

    work page

  7. [7]

    Proceedings of Symposia in Applied Mathematics , volume=

    Machine models of self-reproduction , author=. Proceedings of Symposia in Applied Mathematics , volume=

    work page

  8. [8]

    Yorke , title =

    Joseph Auslander and James A. Yorke , title =. Tohoku Mathematical Journal , number =

    work page

  9. [9]

    2005 , issn =

    Theory of cellular automata: A survey , journal =. 2005 , issn =

    work page 2005

  10. [10]

    2005 , author =

    Homogeneity of surjective cellular automata , journal =. 2005 , author =

    work page 2005