The recovery chart
The knife edge run backwards: what buys universality
back, priced in re-imports — and a last cell that splits the price by
face.
The machine here is the growth apparatus of the
Growth section, and it has two faces: the
depth face, where the state is read as a vector of exponents
(window p ↦ its exponent vp in the modulus
N) and every move multiplies N, and the element
face, where the ring's elements move under its arithmetic while
the window set grows. Universality has exactly two ingredients
(Minsky): an exact zero-test — branch, revisitably, on a
counter being zero — and a borrow, a move that lowers a counter
while reading its value as it descends. The tower owns the zero-test
natively — channel presence p | N is reduction at the
finite place, an intra-window read — and deletes the borrow with the
archimedean place, so the depth face sits one import below
Turing-complete
(the knife edge).
Each door below
is graded by what it lets the machine read of a value as it
moves. The first candidate invariant — universal iff the destroyed
value is read at the deleted archimedean place — is false: the first
door buys universality with zero archimedean contact. What survives as
the currency is the derived down-move — some readable quantity a move
lowers while a test reads it — and that quantity need not be stored
anywhere: it can be synthesized as the difference of two rising
ladders, and the element face manufactures it natively, a sparse
counter under a frontier-riding pointer (the frontier rider, below).
Only the depth face keeps the currency locked: its door still sells
possibility, while the element doors sell per-step exactness.
The doors
The comparison
threshold rule
Fatten the growth machine — moves multiply the modulus, depths
monotone, still no decrement — and upgrade its tests from presence
reads to three-way depth comparisons
sign(α·vp − β·vq −
γ). The purchase is quantized: nothing, then everything. All
tests reading one comparison direction v2 −
v3 (any offsets, presence reads elsewhere) leave
the machine bisimilar to a one-counter machine: halting stays
decidable. A second independent comparison — at any number of windows
from two: across three or more as two differences, disjoint pairs
the same way, and at exactly two as a second ratio on the one pair
(below) — is Minsky-complete: with
X = v2 − v3, Y =
v3 − v5, increments and two
equality reads run a two-counter Minsky machine step-exactly —
every move a multiplication, no depth ever lowered, halting
transfers — so the door opens onto full universality, not merely an
undecidable question. The borrow synthesis: no ladder is ever
lowered, but on the derived counter v2 −
v3 the move INC3 is a value-reading
down-move — two increments plus a comparison equal one destruction,
at zero archimedean import. The mirror: exact-configuration
reachability stays decidable (monotone runs to a fixed target are
bounded) while halting goes undecidable.
Scope. The bisimulation and the step-exact
simulation are run-verified; one-counter decidability and Minsky
universality are cited. Depth beyond 1 means local rings, not
residue fields — the door re-imports the depth axis the
construction truncates. At exactly two windows the linear route is
closed (the cone lemma: two monotone depths' moves span a
two-generator cone in any linear encoding, at most a half-plane,
which cannot carry both directions of two independent counters),
and the cell is closed by a nonlinear one. Two windows p,
q with tests at the ratios 1:1 and α:β (lowest
terms, α > β); the register is the common
depth u at home, vp =
vq = u; a c-step raises
vp, a d-step raises vq,
and a test fires when its form α·vp
− β·vq − γ reads zero. The one-walk gadget
(d-steps until α·vp =
β·vq fires, c-steps home) multiplies
by α/β only when β | u and lands off the
exponent lattice otherwise — a wall of the gadget's, not the cell's.
A cyclic pattern of a c-steps and b
d-steps drops the α:β form by the constant
D = bβ − aα per cycle and lands home at
α(b−a)/D · u plus an offset
fixed by the firing position alone: every pattern is a
generalized-Collatz instruction whose multiplier is chosen. Two
patterns close the cell. The read, k repetitions of
cβ−1dα−1, fires
for every u (its d-steps cover every residue modulo
α−β), lands at α·u and reads u
mod k off the firing substep — a residue read whose only
cost is the junk factor α. The multiplier, the block
a = pβ − qα, b = α(p−q),
lands at (p/q)·u exactly on q | u
for every p/q ≥ α−β+1 with q
coprime to αβ (below that threshold a class can go unfired:
×9/5 compiles at 3:2, ×11/7 does not), its offset zeroed by a
finite table read at a detector offset. A FRACTRAN program — a
list of fractions, a step multiplying the register by the first
whose denominator divides it and halting when none does;
Turing-complete (Conway) — over primes coprime to αβ, each
fraction padded by a power of a junk prime (a factor of α) to
that threshold (padding changes no divisibility test), then runs
step-exact: read
u mod qi, multiply when it divides, halt
when none does. Conway's multiplier program runs in 25 steps on
two windows at 3:2, its trace stripped of the junk prime equal to a
reference interpreter's at every step. The two pattern laws are
proved, the compile is run-verified, FRACTRAN universality is
cited. So the threshold is the second ratio at any number of
windows from two.
verifiers:
explore_second_ruler.py,
explore_two_place_universality.py
The forgetful
borrow rule
A borrow grants power only if it is value-reading. Reset — clear
a whole window, the general overflow — zeroes a counter reading
nothing on the descent, so paired with the native zero-test (no
decrement) the machine collapses past decidable to finite-state:
(control, zero-pattern) is a bisimulation quotient, halting is
finite-graph reachability, decided exactly even for reset
oscillators whose naive forward simulation never ends. Restore a
plain decrement and the same quotient goes unsound —
v → v−1 flips the sign iff v was exactly 1,
the read that un-quotients the value. Safe destruction is real and
total: a window can be wiped freely without importing one bit of
undecidability. The dangerous borrow is the remembering one — the
danger is the reading, not the destruction.
Scope. Generalizes to bounded-threshold
tests (invariant min(v, T), quotient Q ×
{0..T}k). Reset-net undecidability
(increment + decrement + reset, no zero-test) is a joint effect,
cited (Dufourd–Finkel–Schnoebelen 1998); this corner removes the
decrement, which is exactly why it falls to finite-state.
verifier:
explore_reset_corner.py
The base-extension
borrow rule
The ring's native error correction is a height cut — codewords are
the elements below a data bound D — and the cut is not
dynamics-invariant, so any state-evolution use must re-derive
parity per step: base extension, setting a window from the
CRT lift of the synced others — the integer their residues
jointly name. That re-derivation, taken as a
machine primitive, is a borrow, and the machine equipped with it
runs full universality — though with the bare class universal (the
frontier rider, below), what the door itself sells is per-step
exactness: an O(1) lift certificate against the rider's unary time.
On element registers over a growing squarefree window set,
subtraction and the zero-test are already native; what is missing is
exactness — a window adjoined mid-run is born offset, and the
unsynced zero-test lies in both directions (a false zero at the
wrap, a false nonzero from the freeze). Base extension is exactly
the missing sync: grow-and-extend before each increment keeps every
register's lift equal to its counter, the zero-test reads true
integer zero, and a two-counter Minsky machine runs step-exactly —
on residue fields, no depth axis. The keystone lemma: base
extension is not computable by state-independent ring operations —
every such composite is channel-local by CRT, so on a window born
with a constant it returns a constant, while lift(x) mod
p is not constant in x. A program can still rebuild a
lift residue from any window source it can name —
bounded-source extension is native; what no fixed program reaches
is extension from an unboundedly growing source (the addressing
wall: finitely many window names and handle registers against
unboundedly many windows). The contrast with dictionary codes
(the snap-back guarantee) is
operational, not informational: the height-cut syndrome is the
aperiodic predicate lift < D, its re-derivation
non-ring-computable, while a dictionary syndrome is channel-local
and preserved by binding itself — self-checking is free on the
decidable side; self-locating is the whole tax.
Scope. The step-exact simulation and the
two lies are run-verified; Minsky universality is cited. The
keystone lemma is proved for state-independent ring-op composites
(any polynomial map, any register count). The door-free machine —
growth, ring ops, channel reads, no base extension — is settled
universal: the frontier rider, next.
verifier:
explore_ecc_borrow.py
The bare class and its allocator
The frontier rider:
the bare element class is universal
rule
The door-free element machine — growth, ring operations, channel
reads, no base extension — is Turing-universal with no import at
all. The construction is sparse: a counter lives as a residue in
one pointed window and as literal zero everywhere else,
the pointer an idempotent register re-seated on the growth frontier
at every increment. One increment = one grow, so the pointed
prime — the (3+g)-th after g grows, hence ≥
g+4 — always exceeds the count: the value stays strictly
below every prime that reads it, and the native zero-test never
gets the chance to lie. Two exact Minsky counters run bare this
way. Born-at-zero — the no-door clause itself — is the encoding's
free sync: an unpointed window's intended content is zero,
so fresh windows are born correct. The tempting lemma here —
periodic reads cannot assemble an aperiodic
borrow — is false as stated: a periodic read is exact below its
period, and growth mints periods (the prime staircase
pn > n) faster than any native count
climbs. And the tower is incidental to all of this: the identical
protocol asks only for an unbounded supply of fresh writable
registers born at zero, each new one outrunning the running count
(mg > g). Primality, coprimality, the
fields, the CRT reading all go unused — the same two counters run
step-exact on the even tower (every window composite, no field) and
on the plain successor supply 2, 3, 4, …; the prime staircase is one
instance of the supply condition, not its source. The borrow that
buys universality is the allocator, not the arithmetic.
The price is time, and its size is exact: moving a counter of
value v is a transfer loop of v passes, so counting to
N costs N(N−1)/2 against the door's N —
the speed-up unbounded, the gap quadratic (bare ≤ door², tight).
Quadratic is polynomial, so every coarse class — decidable, P, NP,
PSPACE — is closed under it: the door sells efficiency, not
possibility. A quadratic factor is still a real fine-grained
separation — the deterministic time hierarchy sees it — so the
purchase is a genuine cost, just never a class jump. And one
blow-up sits above the door, shared by both models: a
two-counter machine that Gödel-simulates a Turing machine pays the
encoding's cost (Schroeppel) whether or not its carrier is synced;
the door removes only the per-step carrier-sync layer.
Scope. The simulation is step-exact on a
seed battery and a 2000-operation random schedule; a wrap control
exhibits the periodic lie the pointer discipline prevents; Minsky
universality is cited. The substrate-free protocol is checked
step-exact on the even and successor supplies; the quadratic price
is measured directly (counting to N, bare against door) —
both rule tier. Three walls stand beside it —
popcount factors through the lift, static masks stop at the program
text, dense markings die at the wrap — and the rider dodges them
rather than breaks
(explore_bare_class.py);
the keystone lemma is untouched — the rider never rebuilds a lift
residue.
verifiers:
explore_frontier_rider.py,
explore_minimal_carrier.py,
explore_unary_price.py
With the tower reduced to its allocator — an unbounded supply of
fresh writable registers born at zero — the remaining question is how
fast the registers must grow. Write mg for the size
of the g-th register minted; the machine's class is set by the
growth rate of mg.
The supply law: the
boundary is the linear rate rule
A bounded supply is finite-state. With every window of
size at most C, read the state by column: with r
registers, a window is an r-tuple over a fixed alphabet,
every native operation acts identically on every column, and the
sole readout — the zero-test — sees only whether some
column carries a bit. The whole configuration is the control state
plus the set of present column-tuples: finitely many
states, ultimately periodic, decidable. The unbounded-width
register vectors are a mirage — bounded alphabet, no addressing
beyond the frontier singleton — the one freshest window — no
multiplicity read — and the
registers here reset, so this is a sibling of the growth
machine's decidability (monotonicity), not a rung below it: that
machine is decided by well-structure, this one by boundedness.
A linear supply is universal. A carry across two addressed
windows is already native — increment, then let the zero-test read
the wrap — and a positional counter with frozen lower base
Wd — the product of the moduli of the windows
holding its lower digits — has capacity at most
Wd·mfrontier, the frozen base
times the freshest window's modulus (the cap lemma:
only the top digit migrates to fresher windows; migrating a lower
digit rescales the higher weights by an unknown ratio, which is not
in the class). The base Wd is a free program
constant, so any mg = Ω(g) supply clears
the bar — verified at mg = ⌈g/3⌉, where
the single rider wraps — and mg > g is
the one-digit corner of the universal side. A sublinear supply
is capped. On mg = ⌈√g⌉ the same
counter caps at exactly Wd², and every scheme
tried dies the same way, by born-at-zero: a fresh window carries
no value information, and the only native load into it is the unary
transfer, bounded by one modulus, so no construction grows exact
capacity online — the residue-vector counter (value held as
residues across all windows) dies at the lcm freeze, a grown window
being born 0 rather than the value's residue.
The capped side is a third decidable class, matching neither
pole: its moduli grow without bound (not finite-state) and its
registers reset (not monotone). The mechanism under born-at-zero is
bandwidth: every arithmetic operation is componentwise, so
value crosses windows only through the zero-test — one bit out —
and the frontier singleton — one unit in. Two consequences, measured
at the horizons run and conjectured in general: an addressed value
that faithfully tracks a count
is bounded by a program constant — the raw residue is not, since a
masked componentwise value can put any residue at an addressed
window and read it back one bit at a time through the zero-test —
and a faithful register's zero-test fires at a period fixed by the
program — growing extends the period, and a data-dependent freeze
is the very counter it was meant to build.
Scope. Bounded ⇒ finite-state is run-verified
through an exact bisimulation quotient (abstract trace = concrete
trace on a program battery; window sizes 2, 3, 4). On the universal
side the single-rider corner is proved; the linear extension exhibits
one multi-digit counter running uncapped on mg =
⌈g/3⌉, and the two-counter step is by composition with the
rider's mechanism, not a separately re-run battery (Minsky
universality cited); the cap lemma, the carry gadget, and the lcm
freeze are proved by construction. That no construction
counts on a sublinear supply remains conjectured, and with it the
decidability of the o(g) class on a tame supply — one
whose own arithmetic no program can read a halting fact out of; which
supplies are tame is the landing dichotomy's to classify, on
the delay line. The two are not the
same claim, the supply's own arithmetic being a second channel and an
untame one carrying halting facts outright. What has changed is the
ground under the conjecture: born-at-zero is proved there, so it no
longer rests on an argued principle, and what is left open is the
single residual the proof isolates.
verifiers:
explore_bit_supply.py,
explore_sqrt_supply.py,
explore_decidable_side.py
The hand and the read surface
The ratchet
theorem rule
Add an external hand pushing the growth between machine steps —
a policy graded by its read set: blind (a fixed schedule),
machine-grade (the machine's own read kinds), door-grade (anything
determining the true value: depth comparisons, lift reads, or full
watching since birth). On the depth face pushes are absolutely
inert: depths never decrease, so every depth-face read atom
(presence, threshold) is a ratchet, flipping at most once
per run — a program with
k atoms receives at most k flag-flips from
any hand, omniscient or uncomputable, over its whole run,
and the fate map over all hands factors through a finite branch
tree; both hand-game questions (does some hand, does every hand,
make it halt?) are decidable. The comparison door cannot be
smuggled through move-only pushes: the hand can know the
comparison stream, it cannot tell it — the read-side twin
of the addressing wall. Bandwidth is the read surface's property:
the same publishing protocol that dies at flag exhaustion on the
depth face runs forever through one element-face mailbox, channel
reads being periodic and re-readable. A door-grade hand runs
full universality through a door-free machine — the watching
hand syncs each grown window by one native add whose
parameter carries its knowledge: base extension performed
by the intervener, re-priced like the door itself — with the bare
class universal, the sync sells O(1) exactness, not possibility.
Below the door nothing moves: a blind hand mints
no exactness the machine's own repertoire lacks, and a finite-state
machine-grade hand composes away into the machine's own control.
Pushes program the basin, never the class; the hand's reads are the
whole purchase.
Scope. The monotonicity argument is general
for the modelled class — finite control, finite-state hands below
the door, arbitrary blind schedules; on ratchet-only read surfaces
the inertness holds for any hand whatsoever. The deciders, the flag
budget, and the step-exact simulation are run-verified; Minsky
universality is cited.
verifier:
explore_interactive_hand.py
The read
surface rule
Couple a finite-control machine to a genuinely universal core —
a two-counter program on the frontier rider — through k
one-shot flags: at most k boundary events ever cross, and
both boundary-quantified fate questions (does some, does every,
boundary behavior halt the machine?) are answered by enumerating a
finite branch tree with zero core steps, while which leaf
the core realizes is the core's own reachability, undecidable in
general. Through one re-readable mailbox the same core leaks whole:
a two-state machine mirrors its parity stream, one boundary event
per step. The crossing has an exact toll: carrying value v
across the boundary bare costs v transfer passes — quadratic
cumulative over a run — against the door's one synced write per
step. And the read grammar alone does not confine: a flip's timing
is boundary information, and one flag carries the halting problem
into any machine unbounded enough to store the clock — a waiting
counter transcribes the flip time, a budgeted simulation turns it
into a halting witness, so the some-schedule question equals the
halting problem while every frozen-boundary question about the same
machine stays decidable. Ratchet boundaries confine machines of
finite timing resolution — finite-control (the branch tree) or
flag-word-driven (timing-blind) — and any class closed under
product with a finite lattice of one-shot flags; the timing
construction shows they do not confine in general.
Scope. The confinement enumeration is
exhaustive for flag-word-driven machines and the toll is checked at
every step of every run, over a battery of cores with known
behavior; the timing construction is a theorem given Minsky's
halting theorem, its mechanics run-verified exhaustively at probe
scale.
verifiers:
explore_read_surface.py,
explore_flip_timing.py
Across the chart the machine class is set by the composite read
set — machine plus hand — and never by who moves or what is pushed:
every door is a read import. But the last cell split the chart's
currency by face. On the element face the bare class is universal, so
possibility was never for sale there: the element doors — a lift
certificate, a synced window — buy per-step exactness, O(1) where the
bare machine pays unary time. The depth face still sells possibility:
its native reads are ratchets, its
bare class is decidable, and every universality purchase there is an
aperiodic read import (one comparison slope buys nothing; the second
buys everything). Decidability lives at the interface, jointly:
questions posed through a ratchet-only boundary by a machine of
finite timing resolution stay decidable whatever sits behind it —
such a boundary admits at most its atom count in flips over a whole
run, a finite influence tree — while a boundary exposing re-readable
reads is wide enough to carry everything, though re-readability
alone does not force the loss (the forgetful borrow's re-readable
sign read stays finite-state), and grammar alone does not close the
questions (one flag's timing, above). One level below the doors the
allocator repeats the shape as a rate: bounded supply finite-state,
linear universal, sublinear capped — with the supply's own arithmetic
the one channel left open.
One
level below the supply law the capped side has a structure theorem of
its own — the window pool is a delay line of the operation stream, not
writable memory, which reduces deciding halting there to certifying that
a run grows forever — a certificate scheme discharging that on all but
one program of a measured population, and a three-verdict decider whose
third verdict hands back a question about the supply's own arithmetic,
the one channel the cap leaves open:
The delay line.