"""supply.py -- the element machine over a growing supply of windows: on a bounded supply it is a finite automaton reading its supply, on an unbounded one universal, with base extension or without it; over the supplies that follow a word v over {2, 3} by an unbounded tail opening past 3, base extension hands one program every v, and so decides whether it is a palindrome, which no one bare program does. QUESTION. A machine holds registers over a pool of windows Z/m. Its ops act window by window: add, subtract, multiply, write a constant. It reads one thing, the ZERO-TEST of a register, true when the register is 0 in every window. GROW appends a window whose modulus is the supply's next value m_g, every register born 0 there. The machine has no size read and no read naming a window. Which supplies make it universal, and what does BASE EXTENSION (writing into a new window the residue of a register's true value) add? THE OBJECT. A SUPPLY is a sequence m_0, m_1, ... of moduli >= 2. A REGISTER is a column of residues, one per window. The FRONTIER SINGLETON after a grow is the register that is 1 at the new window and 0 elsewhere: with ONES a register that is 1 at every earlier window, write T := 1, then F := T - ONES and ONES := T, all window by window. So the engine's GROW, which appends the window and writes F, is three native ops. THE ARGUMENT (written before the engine). (1) A BOUNDED SUPPLY IS FINITE-STATE. Every op maps each window's COLUMN (its modulus and the registers' residues there) by one function of that column, GROW adds the zero column (then the window-by-window writes above), and the zero-test of r asks whether every column has 0 at r. So the configuration is carried by (instruction, the SET of columns present): how many windows share a column is never read. With every m_g <= C the columns lie in a finite set, the quotient is finite, and halting decides. What it uses is a bounded alphabet, no read naming a window, and no read of multiplicity, together. (1') AMENDED after the first run killed P1 (entered then, before the second run). GROW's modulus is m_g, g the number of windows, which the set of columns forgets: on the supply 2, 3, 2, 3, ... the set alone has two successors. What carries the run is (instruction, set of columns) together with the supply from g on. So on a supply bounded by C the machine is a finite automaton that reads the supply one letter per grow. Halting decides when the supply is eventually periodic, the phase joining the finite quotient. It does not decide on a bounded supply at large: with m_g = 2 + [g in S], the program of f + 1 grows that then asks whether its singleton added to itself is zero halts iff f is in S, so for a noncomputable S no procedure decides halting on that supply. (2) THE POINTED COUNTER. Hold a count v in a register V as the residue v in ONE window, the POINTED one, 0 elsewhere, with its singleton P saved and m_P its modulus. DEC is V := V - P. The zero-test of V is exact while v < m_P. INC grows a window, F its singleton, moves the value there in unary through a work register W (loop V := V - P, W := W + F until V is zero), adds F, and points at F. If the supply has m_g > (the number of grows so far, this one included) at every g, each count sits below its window's modulus, so two pointed counters run a two-counter machine (Minsky 1967, cited): the machine is universal with no import. A supply capped at C lies at count C. (3) THE DOUBLING COUNTER. On any unbounded supply: INC tests zero(V + P), which is true exactly when v = m_P - 1, the window full; then it GROWS and, after every grow, compares the new m_F against 2 m_P by two tallies stepped in lockstep, one on P's window and one on F's, F outlasting when P's tally wraps twice before F's wraps once; it grows until F outlasts, moves the value across, points at F, and adds one. An unbounded supply always yields a window past 2 m_P, so every compare loop ends and the count stays below its window's modulus at every step. Two such counters are Minsky's machine on every unbounded supply, monotone or not. On a supply capped at C, a full window never finds a successor, and the grow budget runs out. (4) THE PRICE. The pointed counter's INC at value v spends v unary steps, so counting to T spends T(T - 1)/2 of them; a value never exceeds its INC count, so the bound is tight. The quadratic factor is a time cost and crosses no class line. (5) WHY BASE EXTENSION IS NOT NATIVE. A straight-line composite of window-by-window ops is window-by-window, so on a window born at 0 it yields a function of that window's own column, fixed at its birth, while the value's residue there depends on the run. Only a loop through the zero-test crosses windows, and the counters shown pay the value in unary time; no lower bound over all programs is claimed. On a bounded supply, bound B, base extension adds one component to the state, the true values mod lcm(2..B), unread by the zero-test and moved by the ring ops, and each write is a function of it, so the machine stays a finite automaton. Without base extension a DENSE counter (x held in every window) lies: a window born when the count was c0 holds, under adds and integer multipliers, (c - U c0) mod m, U the product of the multipliers since its birth (the difference of two affine runs is multiplied and never added to), and a write of 0 re-syncs it. (6) THE NORMAL FORM. Along a run with op word w_1 .. w_t, the column of a window born at time tau with modulus m is the free evaluation over Z of the suffix w_(tau+1) .. w_t from the zero column, the birth grow's singleton 1, reduced mod m: reduction mod m is a ring map, constants commute with it, and a later grow writes 0 there. So a window's content is a function of its birth time and its modulus alone; the pool is a delay line of the op word, sampled mod the supply. After a run's last grow the configuration lies in a finite set, so a run that grows finitely often halts or repeats a configuration, and simulating until either decides it: halting reduces to whether the run grows forever. (7) THE PALINDROME FAMILY. v a word of length 2n over {2, 3}, then one modulus M > 2^(2n), then any tail. BX r sets r's residue at the newest window to r's true value mod its modulus. The BX program reads 2 and 3 as bits 0 and 1 (zero(F + F), then zero(F + F + F)) until a modulus past 3, keeps X = sum b_i 2^(2n-i) and Y = sum b_i 2^(i-1) as true values, binary numerals below 2^(2n) equal iff v is a palindrome, so X = Y iff X = Y mod M; at M it base-extends X - Y, halts iff (X - Y)F is zero, and else loops with no grow. A bare program's run is carried by (instruction, set of columns) and the supply from the next grow on, on any supply ((1')); after n grows over u in {2, 3}^n it sits in one of at most S = I 2^(2^R + 3^R) states, I instructions and R registers. A run that never makes its n-th grow has read only u, so it treats u u^R and u w (w != u^R) alike; otherwise, once 2^n > S, halves u != u' leave one state, and u u^R and u' u^R, with one M and one tail, run alike from there: one is a palindrome and one is not. The prefix's windows persist past M but are columns of that shared state. (8) THE WHOLE PREFIX. With X := 2X + b from 0 and P := 2P from 1, X < 2^(2n) = P < M, so BX X and BX P put X and P themselves in M's window, and X F and P F are pointed counters there ((2)); the doubling counters of (3) keep every count below its window's modulus on the unbounded tail, so a Minsky machine (cited, as in (2)) reads v from them, |v| = log2 P and v the |v|-digit numeral X, and halts iff v lies in any given r.e. language; where M and the tail are computed from v the run is computable, so the halting read decides nothing past r.e. there, the map v -> (M, tail) one computable map. (M and the tail are read too: a program can test whether M = P + 1, so a supply choosing M, or the tail, word by word by a noncomputable set hands that set over.) (9) NO PROMISE. v as in (7), then a tail opening past 3 and unbounded, no modulus promised. Beside X, Y and P the program keeps N = |v| (N := N + 1 a letter) and K = N! (K := K N). Every m <= N divides N!, so K nonzero at a window, read by BX K and a zero-test of K F, puts its modulus past N, where BX N makes N F a pointed counter; such a window comes, since m > N! leaves K nonzero. From it on, at each window it doubles a pointed counter from 1, N times, each doubling a unit transfer zero-tested after every unit: no wrap puts the modulus past 2^N = P > |X - Y|, and there one BX of X - Y and one zero-test decide, X F and P F pointed, so (8)'s readout runs from that window on. ADDED after P1-P5 were read, and written here after its first run, whose print it matches (the slate was not frozen first): P6 section_normal: on 60 seeded random programs of 400 steps on the sqrt, successor and 2, 3, 2, 3, ... supplies, every window at every 37th step that is not a zero-test equals its suffix replayed alone from the zero column at its own modulus; the replay with the birth singleton dropped differs somewhere (the positive control, added after P6's first print). K6 a checkpoint off its replay kills (6). FROZEN before (7)'s engine, after P1-P6 had run: P7c section_extension: 2332 halts and 2333 runs forever (a configuration repeated with no grow between, which is exact). P7 the BX program, M = 2^(2n) + 1 and the tail M + 1, M + 2, ..., halts on exactly the palindromes over every v at n = 1..6 (5460 words). P7p the plant, Y read most significant first too, so Y = X: P7's count of wrong words must print 4^n - 2^n at each n. P8 the same program with its BX dropped: the distinct states after n grows over all 2^n halves, n = 1..8, printed, a colliding pair found by n = 6 and the count at n = 8 below 256; on u u^R and u' u^R its (windows, instruction, set of columns) sequences from the n-th grow on are equal and its verdicts agree, while the BX program's verdicts differ (and, added after the first print as the comparator's control, its sequences part from the shared state). K7 a word at n <= 6 on which the BX program's verdict is not "is a palindrome" kills (7)'s first half as implemented. K8 a colliding pair whose sequences differ after the n-th grow, or whose bare verdicts differ, kills (7)'s carry step. FROZEN before (8)'s code, after P7-P8 had run: P9 for every v at n = 1..4 (340 words) the readout program, X and P base-extended at M and each times F stepped down to 0, counts X and 2^(2n), which decode to v; with its BX dropped it counts 0 and 0 and returns no word. K9 a word not returned kills the read-out; the bare readout returning any word kills it as a control. FROZEN before (9)'s code, after P9 had run: PAc section_nopromise, on (7)'s promise tails: 2332 halts, 2333 runs forever. PA halts on exactly the palindromes, every v at n = 1..3 (84 words), on T1 = 4, 5, 6, ... and on T2 = 4 five times, then 6, 12, 24, 120, 720, then 5, 6, 7, .... PAw the deciding window, the first in tail order past 2^(2n) at or after the first window not dividing (2n)!: 5, 17, 65 on T1 and 6, 120, 65 on T2 at n = 1, 2, 3. PAp the plant, the factorial certificate dropped (the first tail window taken as past N), halts on some non-palindrome. KA a wrong word, or a deciding window off PAw, kills (9) as built; the plant with no wrong word voids the run. THE PREDICTIONS (fixed before the engine ran). P1 section_bounded: 400 seeded random programs of 12 instructions (add, subtract, multiply, write 0 or 1, grow, zero-test) on the supply 2, 3, 2, 3, ..., run 3000 steps each; the map from (instruction, set of columns) to the next such pair is a function across every run, and every run's pair sequence is eventually periodic from its first repeat. P1' section_bounded (fixed before the second run): over 300 such programs of 1500 steps (the code runs 150 of 1000), (instruction, set of columns) has one successor within each program on the supply of 2s, and so does (instruction, set of columns, g mod 2) on 2, 3, 2, 3, ..., every run periodic from its first repeat; the set alone on 2, 3, 2, 3, ... clashes or goes aperiodic somewhere (the positive control). P2 section_pointed: halts-iff-even (x = 0..6), a transfer and a round trip on pointed counters match a reference two-counter interpreter step for step on the primes, on the even moduli 4, 6, 8, ... and on the successor supply 2, 3, 4, ...; on the successor supply capped at 8 a counter's zero-test first lies at count 8. P3 section_price: counting 0 to T by one pointed counter spends exactly T(T - 1)/2 unary steps for T = 1..60. P4 section_doubling: one doubling counter counts 0 to 50 and back to 0 with every zero-test truthful and the register equal to the true count on the supply isqrt(g) + 2, on the supply g + 2 at even g and 2 at odd g, and 0 to 9 and back on max(2, bit length of g); B := 3A from A = 30 then A := B ends at (90, 0) on the first; on the supply of 2s the first full window exhausts a 20000-grow budget at count 1. The code runs the gate's sizes of finding 4. P5 section_freeze: a dense counter under 300 seeded adds and unit multipliers with grows between, no sync, holds (c - U c0) mod m at every window at every step, and lies at least once. THE KILLS (observables, fixed before the engine ran). K1 a key of P1 with two successors kills (1). K2 a step of P2 on an uncapped supply at which a counter's residue differs from the reference kills (2); the capped supply not lying at 8 kills the positive control, and P2 is not read. K3 any unary-step count in P3 off T(T - 1)/2 kills (4). K4 an untruthful zero-test in P4 on an unbounded supply kills (3); the supply of 2s not failing kills its control. K5 a window of P5 off the formula kills (5)'s freeze clause. [Ruled after a later reading: P5 and P6 had replayed their own arithmetic, P5 an induction on a harness list and P6 the engine's step at the same modulus, so neither could fail. P5 now runs the dense counter's ops through the engine's window step, and P6 replays each suffix over Z and reduces once. P4' runs the three two-counter programs on two doubling counters.] THE DESIGN. Pure Python. The engine stores a register as its nonzero windows, which is exact because the programs of (2)-(4) write no nonzero constant and the singletons have one window; section_bounded uses a dense engine, every register a full column. The count a harness compares against is kept outside the machine and is never read by the program, which branches on zero-tests alone. FINDINGS (entered after the runs, from their printed output). 1. P1 KILLED on the first run, on the supply 2, 3, 2, 3, ...: 15 of 400 runs were not periodic from their first repeat, so the set of columns is not a quotient there. (Its clash count, 820532, was also inflated by a harness error, one successor map shared across programs; the aperiodic runs are within one program and stand.) Hence (1'). P1' hit on the second run: 0 clashes and 0 aperiodic runs over 150 programs on the 2s with the set alone and on 2, 3, 2, 3, ... with the phase added; the set alone on 2, 3, 2, 3, ... gives 867 clashes and 4 aperiodic runs. 2. P2 hit: 361 steps over 21 runs equal the reference on each of the three supplies; capped at 8 the first lie is at count 8. 3. P3 hit: exactly T(T - 1)/2 unary steps at every T to 60. 4. P4 hit. The first run met the sizes as frozen: 0 -> 50 -> 0 on isqrt(g) + 2 with 0 lies in 8650 grows, and B := 3A from 30 then A := B at (90, 0) in 8651 grows. The gate runs 0 -> 30 -> 0 (2026 grows) and B := 3A from 10 (2027); the parity supply runs 0 -> 50 -> 0 in 61 grows, the bit-length supply 0 -> 9 -> 0 in 1025; the supply of 2s exhausts its budget at count 1. 5. P5 hit: 30 windows over 300 steps, 0 off the formula, the counter lying. 6. P6 hit: 10679 window checkpoints, 0 off; without the birth singleton 141 are off. 7. P7c, P7 and P7p hit: 2332 halts and 2333 loops; wrong words per n [0, 0, 0, 0, 0, 0] over 5460; the plant [2, 12, 56, 240, 992, 4032], 4^n - 2^n. 8. P8 hit: distinct states after n grows [2, 4, 8, 16, 22, 24, 24, 24], no half stopping early; the first pair at n = 5, 2232222322 and 3222222322, equal for the 49 steps after the 5th grow, both halting; the BX program halts on one and loops on the other, its steps parting from the shared state. 9. P9 hit: 340 of 340 words returned with BX, 0 without, the bare counts at most 0 and 0 (printed since a later reading, which also made P8's comparator control find a step where the BX runs share windows and instruction and differ in columns alone). Tiers: (1'), (3), (5), (6) and (7) are theorems, proved above; (2) and (8) are theorems given Minsky's; (4) is a theorem for the pointed counter, proved by its transfer loop and exact at T = 1..60. At the later reading, P4' (the three programs on two doubling counters) equals the reference on two of the doubling supplies; P5 through the engine, 0 off; P6 over Z, the counts printed below. PA to PAp held after one engine fix: a tail grow left ONE at 0 in the new window, so every copy through ONE read 0 there and the size test passed falsely (16 wrong words at n = 3 on each tail); ONE is now rewritten after each tail grow, as in the letter loop. Then 0 wrong words on both tails, the deciding windows as frozen, and the plant halting on 12 non-palindromes of n = 3 on T1 and 4 on T2, none below. RUN RECORD. 23 checks, 11.1 s, peak 12 MB (the first run, at the frozen sizes, 57 s); with (9), 30 checks, 44.9 s, peak 210 MB; with P8's pair asserted, 31 checks, 44.8 s, peak 208.9 MB. """ import random import sys from itertools import product from math import isqrt CHECKS = [] def check(name, ok, detail=""): CHECKS.append(bool(ok)) print(f" {'PASS' if ok else 'FAIL'} {name}" + (f" ({detail})" if detail else "")) def section(title): print() print(title) # ---------------------------------------------------------------------- # the sparse engine class Machine: def __init__(self, supply, budget=None): self.sup, self.m, self.R = supply, [], {} self.budget = budget def reg(self, r): return self.R.setdefault(r, {}) def grow(self, into): """Append the next window; `into` becomes its singleton.""" if self.budget is not None and len(self.m) >= self.budget: raise RuntimeError("grow budget exhausted") g = len(self.m) self.m.append(self.sup(g)) self.R[into] = {g: 1} def op(self, d, a, b, sign): A, B, out = self.reg(a), self.reg(b), {} for w in set(A) | set(B): x = (A.get(w, 0) + sign * B.get(w, 0)) % self.m[w] if x: out[w] = x self.R[d] = out def add(self, d, a, b): self.op(d, a, b, 1) def sub(self, d, a, b): self.op(d, a, b, -1) def clear(self, d): self.R[d] = {} def copy(self, d, a): self.R[d] = dict(self.reg(a)) def zero(self, r): return not self.reg(r) def value(self, r): """The harness's read: the one nonzero residue, or 0.""" v = self.reg(r) return next(iter(v.values())) if v else 0 class Pointed: """A count held in one window, moved in unary on every INC.""" def __init__(self, M, name): self.M, self.n = M, name self.V, self.P, self.W, self.F = (name + s for s in "VPWF") self.passes = 0 M.grow(self.P) M.clear(self.V) def inc(self): M = self.M M.grow(self.F) M.clear(self.W) while not M.zero(self.V): M.sub(self.V, self.V, self.P) M.add(self.W, self.W, self.F) self.passes += 1 M.add(self.W, self.W, self.F) M.copy(self.V, self.W) M.copy(self.P, self.F) def dec(self): self.M.sub(self.V, self.V, self.P) def jz(self): return self.M.zero(self.V) class Doubling: """A count moved only when its window is full, to a window past twice its modulus; a compare after every grow.""" def __init__(self, M, name): self.M = M self.V, self.P, self.W, self.F, self.T, self.A, self.B = ( name + s for s in "VPWFTAB") M.grow(self.P) M.clear(self.V) def outlasts(self): M, wraps = self.M, 0 M.clear(self.A) M.clear(self.B) while True: M.add(self.A, self.A, self.P) M.add(self.B, self.B, self.F) if M.zero(self.B): return False if M.zero(self.A): wraps += 1 if wraps == 2: return True def inc(self): M = self.M M.add(self.T, self.V, self.P) if M.zero(self.T): while True: M.grow(self.F) if self.outlasts(): break M.clear(self.W) while not M.zero(self.V): M.sub(self.V, self.V, self.P) M.add(self.W, self.W, self.F) M.copy(self.V, self.W) M.copy(self.P, self.F) M.add(self.V, self.V, self.P) def dec(self): self.M.sub(self.V, self.V, self.P) def jz(self): return self.M.zero(self.V) # ---------------------------------------------------------------------- # two-counter programs EVEN = [("DEC", 0, 1, 3), ("DEC", 0, 0, 2), ("INC", 1, 2), ("HALT",)] TRANSFER = [("DEC", 0, 1, 2), ("INC", 1, 0), ("HALT",)] TRIP = [("DEC", 0, 1, 2), ("INC", 1, 0), ("DEC", 1, 3, 4), ("INC", 0, 2), ("HALT",)] def minsky_ref(prog, x, steps): q, c, trace = 0, [x, 0], [] for _ in range(steps): trace.append((q, c[0], c[1])) ins = prog[q] if ins[0] == "HALT": break if ins[0] == "INC": c[ins[1]] += 1 q = ins[2] elif c[ins[1]] == 0: q = ins[3] else: c[ins[1]] -= 1 q = ins[2] return trace def minsky_machine(prog, x, steps, supply, kind): M = Machine(supply) cs = [kind(M, "x"), kind(M, "y")] for _ in range(x): cs[0].inc() q, trace = 0, [] for _ in range(steps): trace.append((q, M.value(cs[0].V), M.value(cs[1].V))) ins = prog[q] if ins[0] == "HALT": break c = cs[ins[1]] if ins[0] == "INC": c.inc() q = ins[2] elif c.jz(): q = ins[3] else: c.dec() q = ins[2] return trace def primes(): ps, n = [], 2 while len(ps) < 400: if all(n % p for p in ps if p * p <= n): ps.append(n) n += 1 return ps PRIMES = primes() # ---------------------------------------------------------------------- # sections def dense_run(prog, supply, steps, period): """Dense engine; returns the sequence of (pc, set of columns, number of windows mod the supply's period).""" nreg = 4 cols, pc, keys = [], 0, [] for _ in range(steps): keys.append((pc, frozenset(cols), len(cols) % period)) ins = prog[pc] k = ins[0] if k == "GROW": m = supply(len(cols)) cols = [c[:1] + tuple(0 if i == ins[1] else c[1 + i] for i in range(nreg)) for c in cols] cols.append((m,) + tuple(1 % m if i == ins[1] else 0 for i in range(nreg))) pc = ins[2] elif k == "JZ": z = all(c[1 + ins[1]] == 0 for c in cols) pc = ins[2] if z else ins[3] else: d, a, b, nxt = ins[1], ins[2], ins[3], ins[4] new = [] for c in cols: m, r = c[0], list(c[1:]) if k == "ADD": r[d] = (r[a] + r[b]) % m elif k == "SUB": r[d] = (r[a] - r[b]) % m elif k == "MUL": r[d] = r[a] * r[b] % m else: r[d] = b % m new.append((m,) + tuple(r)) cols, pc = new, nxt return keys def random_program(rng, n=12, nreg=4): prog = [] for _ in range(n): k = rng.choice(["ADD", "SUB", "MUL", "CONST", "GROW", "JZ", "JZ"]) if k == "GROW": prog.append(("GROW", rng.randrange(nreg), rng.randrange(n))) elif k == "JZ": prog.append(("JZ", rng.randrange(nreg), rng.randrange(n), rng.randrange(n))) elif k == "CONST": prog.append(("CONST", rng.randrange(nreg), 0, rng.randrange(2), rng.randrange(n))) else: prog.append((k, rng.randrange(nreg), rng.randrange(nreg), rng.randrange(nreg), rng.randrange(n))) return prog def census(supply, period, keep_phase, seed=1, n=150, steps=1000): """Per-program successor clashes and aperiodic runs.""" rng = random.Random(seed) clash = aperiodic = grew = keys_seen = 0 for _ in range(n): prog = random_program(rng) keys = dense_run(prog, supply, steps, period) if not keep_phase: keys = [k[:2] for k in keys] grew += any(k[1] for k in keys) succ = {} for a, b in zip(keys, keys[1:]): if succ.setdefault(a, b) != b: clash += 1 keys_seen += len(succ) first = {} for t, k in enumerate(keys): if k in first: p = t - first[k] aperiodic += any(keys[s] != keys[s - p] for s in range(t, len(keys))) break first[k] = t return clash, aperiodic, grew, keys_seen def section_bounded(): section("(1) a bounded supply is a finite automaton on its word") for name, sup, per, phase in ( ("2s, set alone", lambda g: 2, 1, False), ("2,3 alternating, set and phase", lambda g: 2 + g % 2, 2, True)): clash, aper, grew, ks = census(sup, per, phase) check(f"P1' {name}: one successor, periodic from the first " f"repeat", clash == 0 and aper == 0, f"{ks} keys over 150 programs, {grew} of which grew, " f"{clash} clashes, {aper} aperiodic") clash, aper, grew, ks = census(lambda g: 2 + g % 2, 2, False) check("P1' 2,3 alternating, set alone: the phase is read " "(positive control)", clash > 0 or aper > 0, f"{clash} clashes, {aper} aperiodic") def section_pointed(): section("(2) the pointed counter on three supplies, and a cap") supplies = [("primes", lambda g: PRIMES[g]), ("even", lambda g: 2 * g + 4), ("successor", lambda g: g + 2)] for name, sup in supplies: ok, n = True, 0 for prog in (EVEN, TRANSFER, TRIP): for x in range(7): ref = minsky_ref(prog, x, 60) got = minsky_machine(prog, x, 60, sup, Pointed) ok &= ref == got n += len(ref) check(f"P2 {name}: the machine equals the reference", ok, f"{n} steps over 21 runs") M = Machine(lambda g: min(g + 2, 8)) c, lie = Pointed(M, "x"), None for v in range(1, 12): c.inc() if c.jz() != (v == 0): lie = v break check("P2 capped at 8, the zero-test first lies at count 8 " "(positive control)", lie == 8, f"first lie at {lie}") def section_price(): section("(4) the price: T(T - 1)/2 unary steps to count to T") bad = 0 for T in range(1, 61): M = Machine(lambda g: g + 2) c = Pointed(M, "x") for _ in range(T): c.inc() bad += c.passes != T * (T - 1) // 2 or M.value(c.V) != T check("P3 exactly T(T - 1)/2 unary steps for T = 1..60", bad == 0, f"{bad} off") def faithful(sup, top, budget=None): M = Machine(sup, budget) c, lies, true = Doubling(M, "x"), 0, 0 for v in list(range(1, top + 1)) + list(range(top - 1, -1, -1)): if v > true: c.inc() else: c.dec() true = v lies += (c.jz() != (true == 0)) or M.value(c.V) != true return lies, len(M.m) def section_doubling(): section("(3) the doubling counter on every unbounded supply") sups = [("isqrt(g) + 2", lambda g: isqrt(g) + 2, 30), ("g + 2 or 2 by parity", lambda g: g + 2 if g % 2 == 0 else 2, 50), ("max(2, bit length)", lambda g: max(2, g.bit_length()), 9)] for name, sup, top in sups: lies, grows = faithful(sup, top) check(f"P4 {name}: 0 -> {top} -> 0 faithful", lies == 0, f"{lies} lies, {grows} grows") M = Machine(lambda g: isqrt(g) + 2) a, b = Doubling(M, "a"), Doubling(M, "b") for _ in range(10): a.inc() while not a.jz(): a.dec() for _ in range(3): b.inc() while not b.jz(): b.dec() a.inc() check("P4 B := 3A from 10, then A := B, ends at (30, 0)", (M.value(a.V), M.value(b.V)) == (30, 0), f"({M.value(a.V)}, {M.value(b.V)}), {len(M.m)} grows") # not on the bit length: EVEN's odd starts count to 58, held first by # the doubling chain's window 95, which the bit length supplies at # g = 2^94 for name, sup, _ in sups[:2]: ok, n = True, 0 for prog in (EVEN, TRANSFER, TRIP): for x in range(7): ref = minsky_ref(prog, x, 60) got = minsky_machine(prog, x, 60, sup, Doubling) ok &= ref == got n += len(ref) check(f"P4' {name}: two doubling counters equal the reference", ok, f"{n} steps over 21 runs") M = Machine(lambda g: 2, budget=20000) c, at = Doubling(M, "x"), None for v in range(1, 5): try: c.inc() except RuntimeError: at = v - 1 break check("P4 on the supply of 2s the budget runs out at count 1 " "(positive control)", at == 1, f"exhausted at count {at}") def section_freeze(): """The dense counter in register 0, a constant written to register 1 and added or multiplied in, grows naming register 2; every window stepped by step_column, the engine's one op on one window.""" section("(5) the freeze: a dense counter without base extension") rng = random.Random(7) cols, born, U = [], [], [] c, bad, lied = 0, 0, False pool = PRIMES[3:40] def run(ins, grew=False): return [(col[0],) + step_column(col[1:], ins, col[0], grew and w == len(cols) - 1) for w, col in enumerate(cols)] for step in range(300): r = rng.random() if r < 0.2 and len(cols) < 30: cols.append((pool[len(cols)],) + (0,) * 4) cols = run(("GROW", 2, 0), grew=True) born.append(c) U.append(1) elif r < 0.6: a = rng.randrange(1, 50) c += a cols = run(("CONST", 1, 0, a, 0)) cols = run(("ADD", 0, 0, 1, 0)) else: u = rng.choice([1, 2, 3]) c *= u cols = run(("CONST", 1, 0, u, 0)) cols = run(("MUL", 0, 0, 1, 0)) U = [x * u for x in U] for col, c0, x in zip(cols, born, U): h, m = col[1], col[0] bad += h != (c - x * c0) % m lied |= h != c % m check("P5 every window holds (c - U c0) mod m, and the counter lies", bad == 0 and lied, f"{len(cols)} windows over 300 steps, " f"{bad} off the formula") def step_column(col, ins, m, born_here): """One op on one window's column; `born_here` marks the grow that appends this window, whose singleton is 1 there.""" k, r = ins[0], list(col) if k == "GROW": r[ins[1]] = 1 % m if born_here else 0 elif k == "ADD": r[ins[1]] = (r[ins[2]] + r[ins[3]]) % m elif k == "SUB": r[ins[1]] = (r[ins[2]] - r[ins[3]]) % m elif k == "MUL": r[ins[1]] = r[ins[2]] * r[ins[3]] % m elif k == "CONST": r[ins[1]] = ins[3] % m return tuple(r) def free_eval(word, singleton, bits=4096): """The op word evaluated over Z from zero registers, its first op a grow writing 1 at the register it names when `singleton`, else 0; None once a register passes `bits` bits.""" r = [0] * 4 for s, ins in enumerate(word): k = ins[0] if k == "GROW": r[ins[1]] = 1 if singleton and s == 0 else 0 elif k == "ADD": r[ins[1]] = r[ins[2]] + r[ins[3]] elif k == "SUB": r[ins[1]] = r[ins[2]] - r[ins[3]] elif k == "MUL": r[ins[1]] = r[ins[2]] * r[ins[3]] if r[ins[1]].bit_length() > bits: return None elif k == "CONST": r[ins[1]] = ins[3] return tuple(r) def section_normal(): section("(6) a window holds the free evaluation of its own suffix") rng = random.Random(6) supplies = [("sqrt", lambda g: isqrt(g) + 2), ("successor", lambda g: g + 2), ("2,3 alternating", lambda g: 2 + g % 2)] points = bad = blind = huge = 0 for name, sup in supplies: for _ in range(20): prog = random_program(rng) cols, born, trace, pc = [], [], [], 0 for t in range(400): ins = prog[pc] trace.append(ins) if ins[0] == "GROW": born.append(t) cols.append((sup(len(cols)),) + (0,) * 4) pc = ins[2] elif ins[0] == "JZ": z = all(c[1 + ins[1]] == 0 for c in cols) pc = ins[2] if z else ins[3] continue else: pc = ins[4] cols = [c[:1] + step_column(c[1:], ins, c[0], w == len(cols) - 1 and ins[0] == "GROW" and born[-1] == t) for w, c in enumerate(cols)] if t % 37 == 0: for c, b in zip(cols, born): # replay the suffix alone over Z, from the zero # column, then reduce once at the window's modulus x = free_eval(trace[b:], True) y = free_eval(trace[b:], False) if x is None or y is None: huge += 1 continue points += 1 bad += tuple(v % c[0] for v in x) != c[1:] blind += tuple(v % c[0] for v in y) != c[1:] check("P6 every window equals its suffix evaluated over Z and reduced " "at its own modulus", bad == 0 and points > 1000, f"{points} window checkpoints over 60 programs, {bad} off, " f"{huge} past 4096 bits skipped") check("P6 control: the replay without its birth singleton differs", blind > 0, f"{blind} checkpoints off") EXT_REGS = 7 F, T, ONE, X, Y, P, D = range(EXT_REGS) def assemble(lines, bare=False): """Ops and labels to a program: a trailing label on an op is its jump, else it falls through; a JZ's None is the next op. `bare` drops every BX.""" at, ops = {}, [] for x in lines: if isinstance(x, str): at[x] = len(ops) elif not (bare and x[0] == "BX"): ops.append(x) prog = [] for i, op in enumerate(ops): if op[0] == "JZ": prog.append(("JZ", op[1]) + tuple(i + 1 if t is None else at[t] for t in op[2:])) elif op[0] == "HALT": prog.append(op) elif isinstance(op[-1], str): prog.append(op[:-1] + (at[op[-1]],)) else: prog.append(op + (i + 1,)) return prog def ext_program(plant=False, bare=False, readout=False): """Reads the letters 2 and 3 as bits 0 and 1 until a modulus past 3, keeping X (most significant first) and Y (least first) as true values, then base-extends X - Y into that window and halts iff it is 0 there. The plant reads Y most significant first too; the bare program drops every BX. The readout program instead base-extends X and P there and steps each, times F, down to 0, then halts.""" y0 = [("ADD", Y, Y, Y)] if plant else [] y1 = ([("ADD", Y, Y, Y), ("ADD", Y, Y, ONE)] if plant else [("ADD", Y, Y, P)]) return assemble( [("CONST", P, 0, 1), "read", ("GROW", F), ("CONST", ONE, 0, 1), ("ADD", T, F, F), ("JZ", T, "bit0", None), ("ADD", T, T, F), ("JZ", T, "bit1", "top"), "bit0", ("ADD", X, X, X), *y0, ("ADD", P, P, P, "read"), "bit1", ("ADD", X, X, X), ("ADD", X, X, ONE), *y1, ("ADD", P, P, P, "read"), "top", *(READOUT if readout else [("SUB", D, X, Y), ("BX", D), ("MUL", T, D, F), ("JZ", T, "halt", "loop")]), "halt", ("HALT",), "loop", ("JZ", T, "loop", "loop")], bare) READOUT = [("BX", X), ("BX", P), ("MUL", D, X, F), "cx", ("JZ", D, "rp", None), ("SUB", D, D, F, "cx"), "rp", ("MUL", D, P, F), "cp", ("JZ", D, "halt", None), ("SUB", D, D, F, "cp")] def ext_run(prog, supply, until=None, steps=20000, regs=EXT_REGS): """Dense engine with true values and BX r, which sets r's residue at the newest window to r's true value there. Returns ("halt" | "loop" | "reached" | None, keys), keys the (windows, pc, set of columns) before each step; "loop" is a configuration repeated with no grow between, so the run never halts; "reached" stops at the until-th grow, with the state there.""" cols, true, pc, keys, seen = [], [0] * regs, 0, [], set() for _ in range(steps): key = (len(cols), pc, frozenset(cols)) if until is not None and len(cols) == until: return "reached", key keys.append(key) full = (pc, tuple(cols), tuple(true)) if full in seen: return "loop", keys seen.add(full) ins = prog[pc] k = ins[0] if k == "HALT": return "halt", keys if k == "GROW": m, r = supply(len(cols)), ins[1] cols = [c[:1 + r] + (0,) + c[2 + r:] for c in cols] cols.append((m,) + tuple(1 % m if i == r else 0 for i in range(regs))) true[r] = 0 pc = ins[2] seen.clear() # every later configuration has more windows elif k == "JZ": z = all(c[1 + ins[1]] == 0 for c in cols) pc = ins[2] if z else ins[3] elif k == "BX": r, c = ins[1], cols[-1] cols[-1] = c[:1 + r] + (true[r] % c[0],) + c[2 + r:] pc = ins[2] else: d, a, b, pc = ins[1:] cols = [c[:1] + step_column(c[1:], ins, c[0], False) for c in cols] true[d] = (true[a] + true[b] if k == "ADD" else true[a] - true[b] if k == "SUB" else true[a] * true[b] if k == "MUL" else b) return None, keys def word_supply(v): """v, then M = 2^len(v) + 1, then M + 1, M + 2, ...""" M = 2 ** len(v) + 1 return lambda g: v[g] if g < len(v) else M + g - len(v) NL, K, G, A, C, E = range(7, 13) def nopromise_program(plant=False): """Reads v as ext_program does, keeping beside X, Y and P the true values N = |v| and K = N!. Past v it base-extends K into each new window until K is nonzero there, so the modulus is past N and N·F a pointed counter (the plant takes the first tail window); then at that window and each later one it doubles a pointed counter from 1, N times, zero-testing after every unit, and at the first window where nothing wraps, past 2^N, it base-extends X - Y and halts iff that is 0 there.""" cert = ([] if plant else ["cert", ("BX", K), ("MUL", T, K, F), ("JZ", T, "skip", "got"), "skip", ("GROW", F), ("CONST", ONE, 0, 1, "cert")]) return assemble( [("CONST", P, 0, 1), ("CONST", K, 0, 1), "read", ("GROW", F), ("CONST", ONE, 0, 1), ("ADD", T, F, F), ("JZ", T, "bit0", None), ("ADD", T, T, F), ("JZ", T, "bit1", "top"), "bit0", ("ADD", X, X, X), ("ADD", P, P, P, "len"), "bit1", ("ADD", X, X, X), ("ADD", X, X, ONE), ("ADD", Y, Y, P), ("ADD", P, P, P), "len", ("ADD", NL, NL, ONE), ("MUL", K, K, NL, "read"), "top", ("SUB", D, X, Y), *cert, "got", ("MUL", G, F, ONE), ("BX", NL), ("MUL", A, NL, F), "test", ("MUL", C, F, ONE), ("MUL", T, A, ONE), "dbl", ("JZ", T, "sized", None), ("SUB", T, T, G), ("CONST", E, 0, 0), "tr", ("JZ", C, "trdone", None), ("SUB", C, C, F), ("ADD", E, E, F), ("JZ", E, "wrap", None), ("ADD", E, E, F), ("JZ", E, "wrap", "tr"), "trdone", ("MUL", C, E, ONE, "dbl"), "wrap", ("GROW", F), ("CONST", ONE, 0, 1, "test"), "sized", ("BX", D), ("MUL", T, D, F), ("JZ", T, "halt", "loop"), "halt", ("HALT",), "loop", ("JZ", T, "loop", "loop")]) def tail_supply(v, tail): """v, then the tail's moduli in order: no modulus promised.""" return lambda g: v[g] if g < len(v) else tail(g - len(v)) def tail_t1(i): return 4 + i T2_HEAD = [4] * 5 + [6, 12, 24, 120, 720] def tail_t2(i): return T2_HEAD[i] if i < len(T2_HEAD) else 5 + i - len(T2_HEAD) def section_nopromise(): section("(9) base extension with no modulus promised") good, plant = nopromise_program(), nopromise_program(plant=True) run = lambda prog, sup: ext_run(prog, sup, steps=400000, regs=13) ctl = [run(good, word_supply(v))[0] for v in ((2, 3, 3, 2), (2, 3, 3, 3))] check("PAc control: on the promise tails 2332 halts, 2333 runs forever", ctl == ["halt", "loop"], f"{ctl}") for name, tail in (("T1", tail_t1), ("T2", tail_t2)): wrong, wrongp, where = [], [], {} for n in range(1, 4): bad = badp = 0 for v in product((2, 3), repeat=2 * n): want = "halt" if v == v[::-1] else "loop" verdict, keys = run(good, tail_supply(v, tail)) bad += verdict != want where.setdefault(n, set()).add(tail(keys[-1][0] - 1 - len(v))) badp += (want == "loop" and run(plant, tail_supply(v, tail))[0] == "halt") wrong.append(bad) wrongp.append(badp) dec = [sorted(where[n]) for n in range(1, 4)] check(f"PAw {name}: the deciding window per n = 1..3", dec == ([[5], [17], [65]] if name == "T1" else [[6], [120], [65]]), f"read {dec}") check(f"PA {name}: halts on exactly the palindromes, n = 1..3", sum(wrong) == 0, f"wrong words per n {wrong} of 4, 16, 64") check(f"PAp {name}: the plant without the factorial is caught", sum(wrongp) > 0, f"non-palindromes halting per n {wrongp}") def section_extension(): section("(7) base extension reads a palindrome no bare program can") good = ext_program() ctl = [ext_run(good, word_supply(v))[0] for v in ((2, 3, 3, 2), (2, 3, 3, 3))] check("P7c control: 2332 halts, 2333 runs forever", ctl == ["halt", "loop"], f"{ctl}") def wrong(prog): out = [] for n in range(1, 7): out.append(sum( ext_run(prog, word_supply(v))[0] != ("halt" if v == v[::-1] else "loop") for v in product((2, 3), repeat=2 * n))) return out w, wp = wrong(good), wrong(ext_program(plant=True)) check("P7 the BX program halts on exactly the palindromes, n = 1..6", sum(w) == 0, f"wrong words per n {w} over " f"{sum(4 ** n for n in range(1, 7))}") check("P7p plant (Y read most significant first) is caught", wp == [4 ** n - 2 ** n for n in range(1, 7)], f"wrong words per n {wp}") bare = ext_program(bare=True) counts, early, pair = [], 0, None for n in range(1, 9): states = {} for u in product((2, 3), repeat=n): res = ext_run(bare, lambda g, u=u: u[g], until=n) if res[0] != "reached": early += 1 continue states.setdefault(res[1], []).append(u) counts.append(len(states)) if pair is None: pair = next(((n,) + tuple(us[:2]) for us in states.values() if len(us) > 1), None) print(f" bare program: distinct states after n grows, n = 1..8: " f"{counts} ({early} halves stopped before the n-th grow)") check("P8 a colliding pair by n = 6, below 256 states at n = 8", pair is not None and pair[0] <= 6 and counts[-1] < 256, f"pair at n = {pair[0] if pair else None}, {counts[-1]} at 8") if pair is None: return n, u, u2 = pair a, b = u + u[::-1], u2 + u[::-1] va, ka = ext_run(bare, word_supply(a)) vb, kb = ext_run(bare, word_supply(b)) ia = next(i for i, k in enumerate(ka) if k[0] == n) ib = next(i for i, k in enumerate(kb) if k[0] == n) same = ka[ia:] == kb[ib:] # the comparator's control: the BX runs share the state at the n-th # grow too, and part where BX writes, at a step with the same windows # and instruction, the columns alone differing xa, kxa = ext_run(good, word_supply(a)) xb, kxb = ext_run(good, word_supply(b)) split = kxa[ia] == kxb[ib] and any( p[:2] == q[:2] and p[2] != q[2] for p, q in zip(kxa[ia:], kxb[ib:])) word = lambda v: "".join(map(str, v)) check("P8 two halves meet one state; the bare runs agree from it, " "the BX runs do not", same and va == vb and xa != xb and split, f"n = {n}: {word(a)} and {word(b)}, {len(ka) - ia} steps " f"after the n-th grow {'equal' if same else 'DIFFER'}, bare " f"{va}/{vb}; BX {xa}/{xb}, its steps " f"{'parted' if split else 'NOT PARTED'}") def returned(prog): """Words v at n = 1..4 that the readout's two counts decode to, and the largest of each count.""" cx, cp = [i for i, op in enumerate(prog) if op[:4] == ("SUB", D, D, F)] back = top_x = top_q = 0 for n in range(1, 5): for v in product((2, 3), repeat=2 * n): verdict, keys = ext_run(prog, word_supply(v)) x = sum(k[1] == cx for k in keys) q = sum(k[1] == cp for k in keys) top_x, top_q = max(top_x, x), max(top_q, q) L = q.bit_length() - 1 back += (verdict == "halt" and L > 0 and q == 1 << L and x < q and tuple(2 + int(c) for c in format(x, f"0{L}b")) == v) return back, top_x, top_q got = returned(ext_program(readout=True)) lost = returned(ext_program(readout=True, bare=True)) check("P9 base-extending X and P at M hands over v; the bare readout " "counts 0 and 0 and returns none", got[0] == 340 and lost == (0, 0, 0), f"{got[0]} of 340 words returned with BX, {lost[0]} without, " f"the bare counts at most {lost[1]} and {lost[2]}") def main(): section_bounded() section_pointed() section_price() section_doubling() section_freeze() section_normal() section_extension() section_nopromise() print() print(f"{sum(CHECKS)}/{len(CHECKS)} checks passed") sys.exit(0 if all(CHECKS) else 1) if __name__ == "__main__": main()