extractNeighborhood
plain-language theorem explainer
The definition extracts a three-cell local neighborhood from an infinite tape of cell states at a specified integer position. Complexity theorists modeling SAT resolution via cellular automata would reference this when proving that update rules depend only on nearest neighbors. It is implemented by direct record construction selecting the cells at offsets -1, 0, and +1.
Claim. Let $T : ℤ → CellState$ be a tape. For $i ∈ ℤ$, the extracted neighborhood is the triple with left cell $T(i-1)$, center cell $T(i)$, and right cell $T(i+1)$.
background
The module constructs cellular automata gadgets to evaluate SAT instances via local rules derived from Rule 110. Tape is the type ℤ → CellState representing an infinite sequence of cells, while Neighborhood is the structure holding the three consecutive cells at positions i-1, i, i+1. This local window enables deterministic, reversible updates that preserve ledger compatibility.
proof idea
Direct record construction that populates the Neighborhood fields by applying the tape function at the three adjacent integer positions.
why it matters
This definition supplies the neighborhood input required by the step function and the ca_is_local theorem, which together establish that every cell update depends only on its radius-1 neighborhood. It supports the module claim that SAT evaluation can be performed by a 1D CA in O(n^{1/3} log n) time while preserving locality for the Recognition Science ledger.
Switch to Lean above to see the machine-checked source, dependencies, and usage graph.