The GTE Polynomial Step by Step
One formula replaces an entire lookup table — and on binary inputs, it is Rule 110. That is a theorem, not a design choice.
The Question
A cellular automaton (CA) updates each cell by looking at its neighbors and consulting a lookup table. Rule 110, for example, has 8 entries — one for each possible combination of three binary neighbors. To compute the next state of any cell, you find the matching row and read off the output.
The UGP framework does something different. Instead of a table, it uses a single arithmetic formula — the same formula for every cell, every step, every state. The question is: how can one formula replace a table? And why does it turn out to give exactly Rule 110 when the inputs happen to be binary?
The Idea: A Window That Slides
Start with a tape of cells. Each cell holds a value.
To compute the next state of cell i, look at three cells: the one to the left
(L), the center cell itself (C), and the one to the right
(R). This triplet is the neighborhood.
Current tape — computing the next state of position 2:
L = 1 (left neighbor) · C = 3 (center) · R = 2 (right neighbor)
The formula
For any neighborhood (L, C, R), the next state of the center cell is:
computed mod 7 (the result wraps around when it reaches 7)
What each term means
| Term | Meaning |
|---|---|
| C | The center cell's current value — always contributes |
| R | The right neighbor — also contributes directly |
| −CR | Subtract their product — cancels when both are 1 |
| −LCR | Subtract all three — additional cancellation when all are 1 |
A quick check
For the demo tape above (L=1, C=3, R=2):
p(1, 3, 2)
= 3 + 2 − (3×2) − (1×3×2)
= 3 + 2 − 6 − 6
= −7
= 0 (mod 7)
The center cell (value 3) updates to 0 in the next generation.
Wait — 7 states or 8?
Each cell holds one value from the 7-element field GF(7): {0, 1, 2, 3, 4, 5, 6}. That is 7 possible states per cell, not 8. The polynomial operates over this 7-element set.
All 7 possible cell states in GF(7).
When cells are restricted to binary values {0, 1}, there are 2³ = 8 possible (L, C, R) input triples — that is where the Rule 110 truth table's 8 rows come from. The number 8 counts input triples, not cell states.
(0,0,0)(0,0,1)(0,1,0)(0,1,1)
(1,0,0)(1,0,1)(1,1,0)(1,1,1)
All 8 binary input triples — the 8 rows in the Rule 110 table.
Worked Example A — Binary Tape
Start with a tape of five cells. All states are 0 or 1. Cells outside the tape are treated as 0 (fixed-zero boundary). Step through the computation one cell at a time.
Initial tape:
We will compute p(L, C, R) for each of the five cells. Cells outside the tape count as 0.
Cell 0: The left neighbor is outside the tape, so L = 0.
= 0 + 1 − (0×1) − (0×0×1)
= 0 + 1 − 0 − 0
= 1
Cell 0 becomes 1.
Cell 1:
= 1 + 1 − (1×1) − (0×1×1)
= 1 + 1 − 1 − 0
= 1
Cell 1 becomes 1.
Cell 2:
= 1 + 0 − (1×0) − (1×1×0)
= 1 + 0 − 0 − 0
= 1
Cell 2 becomes 1.
Cell 3:
= 0 + 1 − (0×1) − (1×0×1)
= 0 + 1 − 0 − 0
= 1
Cell 3 becomes 1.
Cell 4: The right neighbor is outside the tape, so R = 0.
= 1 + 0 − (1×0) − (0×1×0)
= 1 + 0 − 0 − 0
= 1
Cell 4 becomes 1.
Before and after:
Generation t:
Generation t+1:
All five cells computed to 1. You can verify each against the Rule 110 truth table — (0,0,1)→1, (0,1,1)→1, (1,1,0)→1, (1,0,1)→1, (0,1,0)→1. All match.
Worked Example B — 7-State Tape
Now use states from the full GF(7) alphabet: {0, 1, 2, 3, 4, 5, 6}. The polynomial is identical — the only difference is that the result is taken mod 7, so it wraps around when it reaches 7 or goes negative.
Initial tape: [0, 3, 5, 2, 0] — fixed-zero boundary.
Same formula. Same procedure. The only new step: when the raw sum is outside {0,…,6}, reduce it modulo 7. A negative number like −7 reduces to 0 (because −7 + 7 = 0). A number like −33 reduces to 2 (because −33 + 35 = 2, and 35 = 7 × 5).
Cell 0: L = 0 (boundary), C = 0, R = 3.
= 0 + 3 − (0×3) − (0×0×3)
= 0 + 3 − 0 − 0
= 3 (no mod needed)
→ 3
Cell 1: L = 0, C = 3, R = 5.
= 3 + 5 − (3×5) − (0×3×5)
= 3 + 5 − 15 − 0
= −7
mod 7: −7 + 7 = 0 → 0
Cell 2 — the interesting one: L = 3, C = 5, R = 2.
= 5 + 2 − (5×2) − (3×5×2)
= 5 + 2 − 10 − 30
= −33
mod 7: need a multiple of 7 that brings −33 into {0…6}
7 × 5 = 35, and −33 + 35 = 2
→ 2
The raw sum is −33. Add enough multiples of 7 to reach a positive value in {0,…,6}. Since 7×5 = 35, we get −33 + 35 = 2.
Cell 3: L = 5, C = 2, R = 0.
= 2 + 0 − (2×0) − (5×2×0)
= 2 → 2
Cell 4: L = 2, C = 0, R = 0 (boundary).
= 0 + 0 − 0 − 0 = 0 → 0
Generation t:
Generation t+1:
The 7-state polynomial evolves freely through all of {0,…,6}. Non-binary values appear after just one step, even from a tape that started with only a few non-zero cells.
The Rule 110 Connection
When every cell holds only 0 or 1, the polynomial
p(L,C,R) = C + R − CR − LCR stays in {0, 1} — no mod-7 wrapping
ever happens. Check all 8 binary input triples and compare to Rule 110:
| L | C | R | p(L,C,R) | Rule 110 | Match |
|---|
The polynomial was not designed to reproduce Rule 110. It was selected by minimum description length from all 7-state, radius-1 rules consistent with the UGP invariants. The fact that its binary restriction equals Rule 110 is a consequence — proved by exhaustive case analysis and machine-certified in Lean 4.
Why does this matter?
Rule 110 is computationally universal — it can simulate any Turing machine (proved by Matthew Cook, 2004). Since the GTE polynomial equals Rule 110 on binary inputs, the UGP substrate is also computationally universal. The arithmetic itself can compute anything. This is the content of Lesson 5.
Key Takeaways
-
The formula
p(L,C,R) = C + R − CR − LCRcomputes the next state of any cell from its neighborhood (L, C, R), using arithmetic instead of a lookup table. The result is taken mod 7 — it wraps when it reaches 7 or goes negative. - The polynomial operates over GF(7), a 7-element field: states {0, 1, 2, 3, 4, 5, 6}. That is 7 states per cell. The number 8 is the count of binary input triples (L,C,R) — not the state count.
- On binary inputs {0, 1}, the polynomial gives exactly the Rule 110 truth table on all 8 binary cases. This is a theorem — not a design choice — machine-certified in Lean 4 with zero sorry.
- Non-binary states (2–6) are also valid inputs. The same formula handles the full GTE dynamics. The binary case is the restriction to a 2-symbol sub-sector of the 7-state system.
- Cells outside the tape are treated as 0 (fixed-zero boundary convention).
- The polynomial operates over GF(7), but what exactly is a "cell state" — why seven values, and why this arithmetic? That question is the subject of L04.
-
Two levels — certificate and field.
The polynomial
p(L,C,R)is GTE's Level 1 algebraic certificate: it certifies which structures physics must contain. The physical universe is the Level 2 ΦMDL field (ℒ = ½(∂μΦ)² − (m²/49)(1 − cos 7Φ) + ℒgauge); elementary particles are BPS kink solitons of that field, not cells of a CA. Path 3 covers the ΦMDL field and how particles emerge from it (L12, L14).
See Also
uwca_sweep_implements_rule110— view on GitHub ↗uwca_simulates_rule110_real— view on GitHub ↗