Public, free to read, reuse, and adapt — Kirk Patrick Miller's notice for this edition. Not a patent grant.
FLINT NEXT: Love Logic Proof v3 (the crossover) · c07
2ab17008ea · words 1339 · characters 60894–70419
Previous section · Next section
Exact section text · Full source · Source index
def banner(s):
print("\n" + "=" * 78 + "\n" + s + "\n" + "=" * 78)
# ---------------------------------------------------------------------------
# A. Computable proxy for K(C)
# ---------------------------------------------------------------------------
def compressed_bits(bitmatrix):
packed = np.packbits(bitmatrix.astype(np.uint8).ravel()).tobytes()
# raw LZMA stream (no container header) to reduce constant overhead
comp = lzma.compress(packed, format=lzma.FORMAT_RAW,
filters=[{"id": lzma.FILTER_LZMA2, "preset": 9 | lzma.PRESET_EXTREME}])
return 8 * len(comp)
def section_A():
banner("A. Proxy for K(C): LZMA-compressed size of exposure matrix E (|L| x |H|)")
rows = []
print(f"{'|L|':>5} {'|H|':>6} {'|L||H|':>8} | {'random':>8} {'ratio':>6} | "
f"{'Bern(.1)':>8} {'ratio':>6} | {'global':>7} {'split':>7}")
for L in (8, 32, 128):
for H in (64, 256, 1024):
n = L * H
E_rand = rng.integers(0, 2, size=(L, H))
E_b01 = (rng.random((L, H)) < 0.1).astype(int)
E_glob = np.ones((L, H), dtype=int) # same lie to everyone
E_split = np.zeros((L, H), dtype=int); E_split[:, : H // 2] = 1 # rule-based split
r = dict(L=L, H=H, LH=n,
random=compressed_bits(E_rand), bern01=compressed_bits(E_b01),
glob=compressed_bits(E_glob), split=compressed_bits(E_split))
rows.append(r)
print(f"{L:>5} {H:>6} {n:>8} | {r['random']:>8} {r['random']/n:>6.3f} | "
f"{r['bern01']:>8} {r['bern01']/n:>6.3f} | {r['glob']:>7} {r['split']:>7}")
# fit slope of compressed bits vs |L||H| for random E
x = np.array([r["LH"] for r in rows], float)
y = np.array([r["random"] for r in rows], float)
slope = float(np.polyfit(x, y, 1)[0])
yb = np.array([r["bern01"] for r in rows], float)
slope_b = float(np.polyfit(x, yb, 1)[0])
h01 = -(0.1 * math.log2(0.1) + 0.9 * math.log2(0.9))
print(f"\nLinear fit, random E: bits ~= {slope:.3f} * |L||H| (theory: >= 1 - o(1))")
print(f"Linear fit, Bernoulli(.1): bits ~= {slope_b:.3f} * |L||H| (entropy floor h(0.1) = {h01:.3f})")
print("Structured E (global lie / rule-based split) stays near-constant: the Omega(|L||H|)")
print("bound needs audience-specific, non-rule-based exposure. That is an assumption, not a theorem.")
RESULTS["A"] = dict(rows=rows, slope_random=slope, slope_bern01=slope_b, entropy_bern01=h01)
# ---------------------------------------------------------------------------
# B. Crossover model
# ---------------------------------------------------------------------------
def hazard(n, m, q0, q):
"""Per-round detection probability.
q0: per-observer chance an exogenous reality check contradicts the lie.
q : chance one cross-observer record comparison exposes an audience-specific lie.
m : fraction of other observers' records reachable through shared persistent memory."""
return 1.0 - (1.0 - q0) ** n * (1.0 - q) ** (m * n * (n - 1))
def lambertw0(z, tol=1e-15, maxit=200):
"""Principal branch W0 for real z >= -1/e (numpy/stdlib only, Halley iteration)."""
if z < -1.0 / math.e - 1e-15:
raise ValueError("z < -1/e")
if abs(z + 1.0 / math.e) < 1e-14:
return -1.0
w = math.log1p(z) if z > -0.3 else -1.0 + math.sqrt(2.0 * (1.0 + math.e * z))
for _ in range(maxit):
ew = math.exp(w)
f = w * ew - z
wp1 = w + 1.0
if abs(wp1) < 1e-300:
break
dw = f / (ew * wp1 - (w + 2.0) * f / (2.0 * wp1))
w -= dw
if abs(dw) < tol * (1.0 + abs(w)):
break
return w
def flows(T, G, c, kappa, h, Lp, Delta, delta=1.0):
"""Brute-force expected per-round advantage of deceiving (from round 0) over honesty.
Round d: if undetected at start (prob s^d): gain G, pay maintenance c*kappa*(d+1),
then detected with prob h and pay Lp immediately. If detected earlier: -Delta."""
out = np.empty(T)
surv = 1.0
for d in range(T):
f = surv * (G - c * kappa * (d + 1) - h * Lp) - (1.0 - surv) * Delta
out[d] = (delta ** d) * f
surv *= (1.0 - h)
return out
def D_closed(t, G, c, kappa, h, Lp, Delta):
"""Closed-form undiscounted cumulative advantage after t rounds (t may be real)."""
if h == 0.0:
return G * t - c * kappa * t * (t + 1) / 2.0
s = 1.0 - h
A = G - h * Lp + Delta
geo = (1.0 - s ** t) / h
arith = (1.0 - (t + 1) * s ** t + t * s ** (t + 1)) / (1.0 - s) ** 2
return A * geo - c * kappa * arith - Delta * t
def Dinf_closed(G, c, kappa, h, Lp, Delta, delta):
s = 1.0 - h
x = delta * s
A = G - h * Lp + Delta
return A / (1 - x) - c * kappa / (1 - x) ** 2 - Delta / (1 - delta)
def first_negative(cum, tol=1e-9):
"""cum[i] = D(i+1). Returns the first round count t >= 1 with D(t) < -tol."""
idx = np.where(cum < -tol)[0]
return int(idx[0] + 1) if idx.size else None
def bisect(f, lo, hi, it=200):
flo = f(lo)
for _ in range(it):
mid = 0.5 * (lo + hi)
fm = f(mid)
if (fm > 0) == (flo > 0):
lo, flo = mid, fm
else:
hi = mid
return 0.5 * (lo + hi)
def section_B():
banner("B1. Pure maintenance channel (no detection): t* = 2G/(c*kappa) - 1, delta* = 1 - c*kappa/G")
ok = tot = 0
ex = []
for G in (0.5, 1.0, 2.0, 5.0):
for ck in (0.001, 0.01, 0.05, 0.2):
t_cf = 2 * G / ck - 1
T = int(t_cf) + 50
cum = np.cumsum(flows(T, G, 1.0, ck, 0.0, 0.0, 0.0))
t_num = first_negative(cum)
t_pred = math.floor(t_cf) + 1 # first integer t with D(t)<0 (D(t_cf)=0)
tot += 1; ok += (t_num == t_pred)
# discounted
dstar = 1 - ck / G
dgrid = [d for d in (0.5, 0.9, 0.99, 0.999) if abs(d - dstar) > 1e-3 and 0 < d < 1]
for d in dgrid:
num = np.sum(flows(200000, G, 1.0, ck, 0.0, 0.0, 0.0, d)) if d < 0.9999 else None
tot += 1; ok += ((num < 0) == (d > dstar))
ex.append(dict(G=G, c_kappa=ck, t_closed=t_cf, t_first_int_neg=t_num, delta_star=dstar))
for e in ex[:6]:
print(f" G={e['G']:<4} c*kappa={e['c_kappa']:<6} t*(closed)={e['t_closed']:>9.2f} "
f"first integer t with D<0 (numeric)={e['t_first_int_neg']:>6} delta*={e['delta_star']:.4f}")
print(f" checks passed: {ok}/{tot}")
RESULTS["B1"] = dict(passed=ok, total=tot, examples=ex)
banner("B2. Pure detection channel (c=0): t* = a + W0(-ab e^{-ab})/b ; delta* = (G-hLp)/(G-hLp+h*Delta)")
ok = tot = 0
ex = []
q0, q = 0.002, 0.01
for n in (2, 5, 10, 20):
for m in (0.0, 0.25, 1.0):
h = hazard(n, m, q0, q)
for (G, Lp, Delta) in ((1.0, 2.0, 0.5), (3.0, 5.0, 1.0), (0.5, 0.0, 0.2)):
A = G - h * Lp + Delta
entry = dict(n=n, m=m, h=h, G=G, Lp=Lp, Delta=Delta)
if G - h * Lp <= 0:
entry.update(t_closed=0.0, note="never ahead (G <= h*Lp)")
cum = np.cumsum(flows(50, G, 0, 0, h, Lp, Delta))
tot += 1; ok += (cum[0] <= 0)
ex.append(entry); continue
a = A / (h * Delta)
b = -math.log(1 - h)
z = -a * b * math.exp(-a * b)
t_cf = a + lambertw0(z) / b
# continuous root of closed-form D(t), independent of W
t_root = bisect(lambda t: D_closed(t, G, 0, 0, h, Lp, Delta), 1e-9, 10 * a + 10)
T = int(t_cf) + 200
cum = np.cumsum(flows(T, G, 0, 0, h, Lp, Delta))
t_int = first_negative(cum)
tot += 1; ok += (abs(t_cf - t_root) < 1e-6 * max(1, t_cf))
tot += 1; ok += (t_int == math.floor(t_cf) + 1)
# closed-form D(t) at integers equals brute-force cumulative sum
ts = np.arange(1, T + 1)
Dcf = np.array([D_closed(t, G, 0, 0, h, Lp, Delta) for t in ts])
tot += 1; ok += bool(np.allclose(Dcf, cum, rtol=1e-9, atol=1e-9))
dstar = (G - h * Lp) / (G - h * Lp + h * Delta)
for d in (0.5, 0.8, 0.9, 0.95, 0.99):
if abs(d - dstar) < 1e-4:
continue
num = Dinf_closed(G, 0, 0, h, Lp, Delta, d)
brute = np.sum(flows(20000, G, 0, 0, h, Lp, Delta, d))
tot += 1; ok += ((num < 0) == (d > dstar)) and abs(num - brute) < 1e-6 * max(1, abs(num))
entry.update(t_closed=t_cf, t_root=t_root, t_first_int_neg=t_int, delta_star=dstar,
t_marginal=math.log(A / Delta) / b)
ex.append(entry)
print(f" q0={q0} (reality check), q={q} (cross-record check); G=1, Lp=2, Delta=0.5 rows:")
print(f" {'n':>3} {'m':>5} {'h(n,m)':>8} {'t*':>9} {'t_marg':>8} {'delta*':>8}")
for e in ex:
if e["G"] == 1.0 and "t_root" in e:
print(f" {e['n']:>3} {e['m']:>5} {e['h']:>8.4f} {e['t_closed']:>9.2f} "
f"{e['t_marginal']:>8.2f} {e['delta_star']:>8.4f}")
elif e["G"] == 1.0:
print(f" {e['n']:>3} {e['m']:>5} {e['h']:>8.4f} deception never ahead: G <= h*Lp")
print(f" checks passed: {ok}/{tot}")
RESULTS["B2"] = dict(passed=ok, total=tot, q0=q0, q=q, examples=ex)