Path 1 — Foundations · Lesson 5 of 7

How the UWCA Works

Four local passes. One sweep. One time step. And the UGP substrate becomes computationally universal.

The Question

In L04 you learned that the UWCA is intrinsic to the survivor space — its tiles are the natural building blocks of the space's topology, not machinery placed on top. But what does the UWCA actually do when it runs? How does a sweep of four local passes produce a new generation?

This lesson answers that question concretely — with actual register values, a complete worked example, and the theorem that guarantees it always works.

The Setup

Fix a tape of binary cells. Each cell position has its own prime. The cell holds a binary state — 0 or 1 — encoded as a residue in that prime's field. A neighborhood is a frozen triple (L, C, R) — the left neighbor, the center, and the right neighbor at the current time step.

p=3 0−1
p=5 10
p=7 1+1

Three-cell tape [0, 1, 1] with assigned primes. Each cell's state is a binary residue in its prime's field.

The goal of the UWCA: compute the next state of every cell simultaneously, using only local information — no cell looks beyond its immediate neighbors.

The Penalty Function

For each cell position i, define the penalty:

ei = 0  if  xi,next = R(Li, Ci, Ri)

ei = 1  otherwise

In plain language: the penalty is zero when the proposed next state for cell i equals what Rule 110 demands given the frozen neighborhood (L, C, R). The penalty is one when it doesn't match.

The UWCA looks for the assignment of next states that makes every cell's penalty simultaneously zero. This is not a minimization with a cost function — it is a constraint satisfaction. Every cell must be exactly right.

Local determinism — why there is always exactly one answer

Rule 110 is a function: for any (L, C, R), it outputs exactly one value. The binary alphabet has exactly two symbols: {0, 1}. Therefore, for any frozen neighborhood, exactly one of the two symbols satisfies ei = 0 — the one that equals R(L, C, R). The sweep never faces a choice. It never needs to backtrack.

The Four Passes (P1–P4)

The UWCA does not evaluate the penalty with a global lookup. Instead, it distributes the work across four local passes. Each cell carries a small set of working registers that are set, used, and cleared within a single time step.

Rule 110's five minterms (the input triples that produce output 1):

(1,1,0) (1,0,1) (0,1,1) (0,1,0) (0,0,1)

Any triple NOT in this list produces output 0. (Note: (1,1,1) → 0 and (1,0,0) → 0.)

1
P1 — Neighbor distribution

Each cell copies its neighbors' bits onto its own local working registers L and R. After P1, every cell holds its own current value (C) plus local copies of its neighbors' values.

No cell has looked beyond its immediate neighborhood yet. Everything is local.

Tape [0, 1, 1] after P1
CellC (own state)L (copied)R (copied)N (accumulator)
−100 ← boundary1 ← cell 00
010 ← cell −11 ← cell +10
+111 ← cell 00 ← boundary0

Blue values are the ones that changed in this pass. N is the next-bit accumulator, still zero.

2
P2 — Minterm detection

Each cell checks whether its local triple (L, C, R) matches any of Rule 110's five minterms. It sets a flag for each matching minterm. A cell can match at most one minterm (the minterms are disjoint).

Tape [0, 1, 1] — minterm check
Cell(L, C, R)Matches?Which minterm
−1(0, 0, 1)Yes(0,0,1)
0(0, 1, 1)Yes(0,1,1)
+1(1, 1, 0)Yes(1,1,0)

All three cells matched a minterm — all three will output 1. If a cell's triple is NOT in the five minterms (e.g., (1,1,1) or (1,0,0)), its minterm flag stays 0 and its output will be 0.

3
P3 — OR-accumulation

Each cell OR-accumulates its minterm flags into the next-bit accumulator N:

Ni = Mu₁i ∨ Mu₂i ∨ Mu₃i ∨ Mu₄i ∨ Mu₅i

Ni = 1 if and only if any minterm matched, which is exactly when Rule 110 outputs 1.

After P3 — N accumulator values
CellMinterm matched?N (next-bit accumulator)
−1Yes1
0Yes1
+1Yes1
4
P4 — Commit and clear

Each cell commits the accumulated next-bit to its main state register, then clears all working registers back to zero:

Ci ← Ni  ;  clear L, R, all minterm flags, N to 0
After P4 — new tape state
CellNew C (main state)LRN
−11000
01000
+11000

After P4, each cell is back to a clean state with only C set. The tape [0, 1, 1] has become [1, 1, 1]. All working registers are cleared — ready for the next time step.

Verify with the polynomial: p(0,0,1) = 1 ✓   p(0,1,1) = 1 ✓   p(1,1,0) = 1 ✓

Pass 1 of 4

Full Worked Example — Two Time Steps

Starting tape: [0, 1, 1] — cells at positions −1, 0, +1 with primes p=3, p=5, p=7. Fixed-zero boundary on both sides. Run P1→P2→P3→P4, then roll the window and run again.

Generation t = 0:

0−1
10
1+1

All four registers (C, L, R, N) initialized. C = tape values. L, R, N = 0.

CellCLRN
−10000
01000
+11000

P1 complete — each cell copied its neighbors:

CellCLRN
−10010
01010
+11100

Boundary cells outside the tape contribute 0.

P2 complete — minterm detection. Rule 110 minterms: (1,1,0) (1,0,1) (0,1,1) (0,1,0) (0,0,1)

Cell(L,C,R)Minterm?
−1(0,0,1)✓ (0,0,1)
0(0,1,1)✓ (0,1,1)
+1(1,1,0)✓ (1,1,0)

All three matched. They will all output 1. A cell whose triple is not a minterm — like (1,1,1) — would get no flag and output 0.

P3 complete — OR-accumulation into N:

CellCLRN (updated)
−10011
01011
+11101

Ni = 1 for all cells — each will commit 1 in P4.

P4 complete — commit N → C; clear all working registers:

CellC (new state)LRN
−11000
01000
+11000

New tape (generation t = 1):

1−1
10
1+1

Rolling the window — the t=1 tape becomes the new t=0:

t = 0 (old — discard):

0
1
1
↓ roll

t = 0 (new = former t=1):

1−1
10
1+1

The prime assignment shifts accordingly. The computation can continue indefinitely — each sweep produces one CA time step. No state needs to be stored externally.

Running P1–P4 on [1, 1, 1]:

Cell(L,C,R)Minterm?N
−1(0,1,1)✓1
0(1,1,1)✗ (not a minterm)0
+1(1,1,0)✓1

Generation t = 2:

1−1
00
1+1

Verify with polynomial:
p(0,1,1) = 1+1−1−0 = 1 ✓   p(1,1,1) = 1+1−1−1 = 0 ✓   p(1,1,0) = 1+0−0−0 = 1 ✓

Two complete time steps computed. The 4-pass mechanism and the polynomial give identical results — they are two descriptions of the same computation.

Step 1 of 7

What This Means: Computational Universality

The UWCA running on the binary sub-sector of the UGP survivor space implements Rule 110. This was proved by exhaustive case analysis and machine-certified in Lean 4.

In 2004, Matthew Cook proved that Rule 110 can simulate any Turing machine — any algorithm, any computation, on any finite input. This is called computational universality.

Therefore: the UGP substrate is computationally universal. It can, in principle, compute anything that any computer can compute.

The UWCA is not the same as Rule 110. Rule 110 is a specific CA rule — a lookup table on {0,1}³. The UWCA is the evaluation mechanism that runs that rule (and the full GTE dynamics) using prime-residue arithmetic on the survivor space. Rule 110 is a program. The UWCA is the machine it runs on.

A second, independent proof. The Rule-110 argument above is not the only way the Lean library establishes this. A completely separate proof shows the UGP substrate can simulate a register machine — a simple model of computation from 1960s computer science (Minsky, 1967) that was already known to be exactly as powerful as a Turing machine. This route doesn't go through Rule 110 or Cook's theorem at all; it rests on one named, textbook-standard axiom (that register machines and Turing machines are computationally equivalent). Two independent proofs, same conclusion.

The chain of reasoning

Step 1

The GTE polynomial on binary inputs equals Rule 110 on all 8 cases.

Step 2

The UWCA 4-pass sweep realizes this polynomial via local register operations.

Step 3

Rule 110 is Turing universal (Cook 2004).

Conclusion

The UGP substrate is Turing universal.

Key Takeaways

See Also

Lean 4 proofs (ugp-lean)
Source papers
Full tutorial (PDF)