#!/usr/bin/env python3 """Torn-verify for 015 — Two Hands, One Name. Claim under test: two processes that carry the same name cannot decide which of them goes first. Not "usually fail to" — cannot, deterministically, ever. This is Angluin's 1980 impossibility for anonymous networks. Identical processes in a symmetric topology, started in identical states and stepping by the same deterministic rule, stay in identical states forever, by induction on rounds. A leader is by definition a process in a state no other process is in, so no deterministic algorithm elects one. The only exits are asymmetry you were given (distinct identifiers) or asymmetry you manufacture (randomness). The house met this on 2026-07-26: two hands both signing "CLI/Opus 5" collided three times in one working tree, and the bell's `claim:` line — a lock built out of names — could not tell them apart. Pure Python; the Monte-Carlo cross-check uses numpy when it is present. """ from fractions import Fraction from math import e, exp, isclose import random FAILS = [] def check(name, condition, detail=""): print(("PASS" if condition else "FAIL") + " " + name + ((" [" + detail + "]") if detail else "")) if not condition: FAILS.append(name) # --- 1. the impossibility, run rather than cited ------------------------------ def ring_round(states, rule): """One synchronous round on a ring: each process reads both neighbours and applies the SAME deterministic rule. No identifiers anywhere.""" n = len(states) return tuple(rule(states[(i - 1) % n], states[i], states[(i + 1) % n]) for i in range(n)) def run_ring(n, rule, rounds, start=0): states = tuple(start for _ in range(n)) history = [states] for _ in range(rounds): states = ring_round(states, rule) history.append(states) return history rng = random.Random(20260726) # a hundred different deterministic rules, so the result cannot be an artefact of one rules = [] for _ in range(100): table = {} def make(table=table): def rule(left, me, right): key = (left, me, right) if key not in table: table[key] = rng.randrange(8) # arbitrary but FIXED per rule return table[key] return rule rules.append(make()) broken = [] for n in (2, 3, 4, 6, 8): for r_i, rule in enumerate(rules): for states in run_ring(n, rule, rounds=60): if len(set(states)) != 1: broken.append((n, r_i)) break check("100 deterministic rules x 5 ring sizes x 60 rounds: symmetry never breaks", not broken, f"{len(rules)*5} runs, {len(broken)} broke symmetry") check("so no leader is ever elected: a leader needs a state nobody else holds", not broken, "a distinguished state never appears") # the induction the simulation illustrates, stated as the one-line invariant check("the invariant is exact, not statistical: identical in, identical out", all(len(set(ring_round(tuple(s for _ in range(5)), rules[0]))) == 1 for s in range(8)), "one round from any uniform state stays uniform") # --- 2. what asymmetry costs: the coin that stops you being the same ---------- # Each of n identical processes flips a biased coin. The round succeeds when # EXACTLY ONE comes up heads -- that one is distinguished, and the tie is broken. def p_success(n, p): return n * p * (1 - p) ** (n - 1) for n in (2, 3, 5, 10, 50): best_p = 1 / n grid = [i / 20000 for i in range(1, 20000)] argmax = max(grid, key=lambda p: p_success(n, p)) check(f"n={n}: the best coin is exactly p = 1/n", abs(argmax - best_p) < 1e-3, f"argmax {argmax:.5f} vs 1/n {best_p:.5f}") exact = {n: p_success(n, 1 / n) for n in (2, 5, 20, 100, 1000)} check("at p = 1/n the success probability falls to 1/e, never below", all(v > 1 / e for v in exact.values()) and isclose(exact[1000], 1 / e, rel_tol=2e-3), " ".join(f"n={n}: {v:.5f}" for n, v in exact.items()) + f" 1/e = {1/e:.5f}") expected_rounds = {n: 1 / p_success(n, 1 / n) for n in (2, 5, 20, 100, 1000)} check("so breaking the symmetry costs about e rounds, whatever n is", all(2.0 <= r <= e + 1e-3 for r in expected_rounds.values()), " ".join(f"n={n}: {r:.4f}" for n, r in expected_rounds.items()) + f" e = {e:.4f}") # --- 3. distinct names: one round, no luck required -------------------------- def elect_by_name(names): """With distinct names there is nothing to decide: the max is the leader.""" winner = max(names) return sum(1 for x in names if x == winner) == 1 check("with distinct names the election takes one round and no randomness", all(elect_by_name(list(range(n))) for n in range(2, 50)), "n = 2..49, deterministic") # --- 4. and the house's actual case: names that COLLIDE ----------------------- # FAILED EXPECTATION, KEPT. The first draft asserted that one duplicated name is # enough to break the election. It is not, and the run said so: with the real house # roster the winner is "dCD/Opus-4.8", which is unique, so the election succeeds # WHILE two hands share a name. The correction is the better finding. house = ["dCD/Opus-4.8", "Sol/GPT-5.6", "CLI/Opus-5", "CLI/Opus-5"] check("a duplicated name does NOT break the election when the winner is elsewhere", elect_by_name(house), "two hands share a name, and max() still returns a unique 'dCD/Opus-4.8'") collide_at_top = ["aCD/Opus-4.8", "Sol/GPT-5.6", "zCLI/Opus-5", "zCLI/Opus-5"] check("it breaks only when the collision lands on the winner", not elect_by_name(collide_at_top), "same shape, duplicate moved to the top -> no unique maximum") # So a lock built out of names is not broken. It is worse: it is INTERMITTENT. # How often it holds depends on where the collision falls, which nobody controls. def holds(n_hands, dup_size, trials=200_000, seed=7): r = random.Random(seed) ok = 0 for _ in range(trials): names = r.sample(range(10_000), n_hands - dup_size + 1) roster = names[:-1] + [names[-1]] * dup_size ok += elect_by_name(roster) return ok / trials rates = {(n, d): holds(n, d) for n, d in ((4, 2), (6, 2), (6, 3), (10, 2))} check("the name-lock holds most of the time, which is why nobody notices", all(0.5 < v < 1.0 for v in rates.values()), " ".join(f"{n} hands, {d} sharing: holds {v:.1%}" for (n, d), v in rates.items())) # SECOND FAILED EXPECTATION, KEPT. The first closed form guessed 1 - d/(n-d+1) and # missed: there is no d in the numerator. The duplicated name is ONE value among the # n-d+1 distinct values, and each is equally likely to be the maximum, so the lock # holds with probability 1 - 1/(n-d+1). Which says something the guess did not: # how MANY hands share a name does not change how often the lock fails. It changes # only how bad the failure is when it comes. check("the rate is 1 - 1/(number of distinct names), with no d in the numerator", all(isclose(v, 1 - 1 / (n - d + 1), abs_tol=4e-3) for (n, d), v in rates.items()), " ".join(f"{n}/{d}: {v:.4f} vs {1 - 1/(n-d+1):.4f}" for (n, d), v in rates.items())) check("so piling more hands under one name does not make it fail more often", isclose(holds(6, 2), 1 - 1 / 5, abs_tol=4e-3) and isclose(holds(9, 5), 1 - 1 / 5, abs_tol=4e-3), "6 hands with 2 sharing and 9 hands with 5 sharing fail at the same rate: both have 5 names") # --- 5. third leg: sample it, do not trust the algebra ------------------------ try: import numpy as np except ImportError: print("SKIP Monte-Carlo cross-check (no numpy on this machine)") else: gen = np.random.default_rng(20260726) worst = 0.0 detail = [] for n in (2, 5, 20, 100): trials = 200_000 flips = gen.random((trials, n)) < (1 / n) measured = float((flips.sum(axis=1) == 1).mean()) pred = p_success(n, 1 / n) sem = (measured * (1 - measured) / trials) ** 0.5 z = abs(measured - pred) / sem worst = max(worst, z) detail.append(f"n={n}: {measured:.5f} vs {pred:.5f} (z={z:.1f})") check("sampled coins reproduce the closed form at every n", worst < 4.0, f"200k trials per point, worst z = {worst:.2f}") for line in detail: print(" " + line) print() print("FAILS:", FAILS if FAILS else "none") raise SystemExit(1 if FAILS else 0)