Exact Worst-Case Dependency Fronts in Rule 110 and Finite-State Certification of Input Essentiality

We study the exact worst-case dependence of a future cell state on initial conditions in Elementary Cellular Automaton Rule 110. For the bi-infinite lattice, we prove that the essential initial coordinates for predicting the state of cell 0 after t synchronous updates lie in the interval [−(t − floor(t/3)), t], and that both endpoints are essential for every t ≥ 0. Consequently, the minimum contiguous observation window has exact width 2t + 1 − floor(t/3), with asymptotic growth rate 5t/3. The upper bound is established through a three-step exclusion property of the local transition rule. Sharpness is demonstrated using an explicitly constructed traveling single-bit defect on the period-four background (1011). Reproducible Python and TypeScript computations verify the finite local identities and defect recurrence. A separate computational investigation confirms that every coordinate within the proposed dependency interval is essential for all 0 ≤ t ≤ 2000, covering 3,337,668 time–position pairs using periodic backgrounds of period at most ten. The corresponding statement for arbitrary horizons remains an open conjecture. For finite periodic rings, we establish a finite-horizon criterion for persistent input essentiality and examine the divergence between decreasing image capacity and extensive dependence on initial conditions. The accompanying research artifacts include source code, computational verification records, and a Lean 4 formalization with a supplied successful compilation report. Keywords: elementary cellular automata, Rule 110, dependency propagation, input sensitivity, deterministic dynamical systems, causal cones, computational verification.

Authors

Publication Details

Journal
Zenodo (CERN European Organization for Nuclear Research)
Published
2026-11-18
DOI
https://doi.org/10.5281/zenodo.24334184
Primary Topic
Cellular Automata and Applications
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

Exact Worst-Case Dependency Fronts in Rule 110 and Finite-State Certification of Input Essentiality

Aleksandr Strand
4 links
Zenodo (CERN European Organization for Nuclear Research)
Cellular Automata and Applications
preprint

Exact Worst-Case Dependency Fronts in Rule 110 and Finite-State Certification of Input Essentiality

Aleksandr Strand
preprint en

Abstract

We study the exact worst-case dependence of a future cell state on initial conditions in Elementary Cellular Automaton Rule 110. For the bi-infinite lattice, we prove that the essential initial coordinates for predicting the state of cell 0 after t synchronous updates lie in the interval [−(t − floor(t/3)), t], and that both endpoints are essential for every t ≥ 0. Consequently, the minimum contiguous observation window has exact width 2t + 1 − floor(t/3), with asymptotic growth rate 5t/3. The upper bound is established through a three-step exclusion property of the local transition rule. Sharpness is demonstrated using an explicitly constructed traveling single-bit defect on the period-four background (1011). Reproducible Python and TypeScript computations verify the finite local identities and defect recurrence. A separate computational investigation confirms that every coordinate within the proposed dependency interval is essential for all 0 ≤ t ≤ 2000, covering 3,337,668 time–position pairs using periodic backgrounds of period at most ten. The corresponding statement for arbitrary horizons remains an open conjecture. For finite periodic rings, we establish a finite-horizon criterion for persistent input essentiality and examine the divergence between decreasing image capacity and extensive dependence on initial conditions. The accompanying research artifacts include source code, computational verification records, and a Lean 4 formalization with a supplied successful compilation report. Keywords: elementary cellular automata, Rule 110, dependency propagation, input sensitivity, deterministic dynamical systems, causal cones, computational verification.

Zenodo (CERN European Organization for Nuclear Research)
Cellular Automata and Applications
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon