// verify.mjs — the checks behind the stratum "The Sentence That Says It Can't
// Be Proved" (/strata/godel-incompleteness/).
//
//   node research/godel-incompleteness/verify.mjs
//
// What this establishes, all independently of the page's own code:
//   1. ARITHMETIZATION is exact and DECODABLE. Each sample formula is encoded by
//      Gödel's prime-power scheme into a single BigInt, and that integer is
//      factored back to recover the formula symbol-for-symbol. This is the
//      injectivity the whole construction rests on: a statement about formulas
//      becomes a statement about numbers, with nothing lost.
//   2. The two hand-checkable numbers the page advertises are right
//      (0=0 → 270, S0=S0 → 808500).
//   3. SELF-REFERENCE is real and cheating-free. The quine in quine.js prints
//      its own source byte-for-byte (run it, compare to the file). This is the
//      computability twin of the diagonal lemma (Kleene's recursion theorem).
//
// What this deliberately does NOT do, and the page says so: it does not build the
// arithmetical Proof(m,n) predicate or derive the Gödel sentence inside a formal
// system — that is a machine-checked development, not a verifier. The scope here
// is the two gears (numbering + self-reference) and the exact statements; the
// rest is cited (chiefly Franzén 2005). See README.md.

'use strict';
import { readFileSync } from 'node:fs';
import { execFileSync } from 'node:child_process';
import { fileURLToPath } from 'node:url';
import { dirname, join } from 'node:path';
import { hered, val, treeEq, ordCmp, step, render } from './goodstein.mjs';

const HERE = dirname(fileURLToPath(import.meta.url));

let fails = 0;
const ok = (name, cond, extra = '') => {
  if (!cond) fails++;
  console.log(`${cond ? '  ok  ' : 'FAIL  '}${name}${extra ? '   ' + extra : ''}`);
};

// --- the SAME convention the page uses (must stay in lock-step) -------------
const CODE = { '0':1,'S':2,'=':3,'+':4,'×':5,'(':6,')':7,'¬':8,'∧':9,
               '∨':10,'→':11,'∀':12,'∃':13,'x':14,'y':15 };
const SYM = Object.fromEntries(Object.entries(CODE).map(([k, v]) => [v, k]));

function primes(n) {
  const ps = [];
  let c = 2;
  while (ps.length < n) {
    let prime = true;
    for (const q of ps) { if (q * q > c) break; if (c % q === 0) { prime = false; break; } }
    if (prime) ps.push(c);
    c++;
  }
  return ps;
}

// Gödel number of a formula = product over positions k of  p_k ^ code(symbol_k).
function godel(syms) {
  const ps = primes(syms.length).map(BigInt);
  let g = 1n;
  for (let i = 0; i < syms.length; i++) g *= ps[i] ** BigInt(CODE[syms[i]]);
  return g;
}

// Decode by prime factorisation: the exponent of the k-th prime is the k-th code.
function decode(g) {
  const ps = primes(64).map(BigInt);
  let n = g, out = '';
  for (let i = 0; i < ps.length && n > 1n; i++) {
    let e = 0n;
    while (n % ps[i] === 0n) { n /= ps[i]; e++; }
    const s = SYM[Number(e)];
    if (s === undefined) return null;
    out += s;
  }
  return out;
}

console.log('— GEAR ONE: arithmetization is exact and decodable —');

// Six samples (the same set the page's "check" panel names).
const SAMPLES = ['0=0', 'S0=0', 'S0=S0', '¬(0=S0)', '∀x(x=x)', '∀x∃y(y=Sx)'];
for (const f of SAMPLES) {
  const syms = Array.from(f);
  const g = godel(syms);
  const back = decode(g);
  ok(`encode/decode round-trip: ${f}`, back === f,
     `${g.toString().length}-digit number → ${back}`);
}

// The two hand-checkable values the page quotes explicitly.
ok('0=0 → 270 (2¹·3³·5¹)', godel(Array.from('0=0')) === 270n,
   godel(Array.from('0=0')).toString());
ok('S0=S0 → 808500 (2²·3¹·5³·7²·11¹)', godel(Array.from('S0=S0')) === 808500n,
   godel(Array.from('S0=S0')).toString());

// Injectivity spot-check: two different formulas never collide.
ok('distinct formulas → distinct numbers (S0=0 ≠ 0=S0)',
   godel(Array.from('S0=0')) !== godel(Array.from('0=S0')));

console.log('\n— GEAR TWO: self-reference is real and cheating-free —');

// Run the quine in a fresh node process and compare its output to its own bytes.
const quinePath = join(HERE, 'quine.js');
const source = readFileSync(quinePath, 'utf8');
const printed = execFileSync(process.execPath, [quinePath], { encoding: 'utf8' });
ok('quine.js prints its own source, byte-for-byte', printed === source,
   `${source.length} source bytes vs ${printed.length} printed`);
// And it genuinely takes no input / reads no file — it is data + double-use only.
ok('quine source contains no file/read access (no fs, no readFile)',
   !/require|readFile|import\s|process\.argv|fs\b/.test(source));

console.log('\n— GEAR FOUR: a real, natural truth PA cannot prove (Goodstein) —');

// (a) small sequences terminate at exactly the right step (exact BigInt arithmetic).
function lengthTo0(m, capSteps = 100000, capDigits = 600) {
  let V = BigInt(m), b = 2, n = 0;
  while (V > 0n) {
    if (n > capSteps || V.toString().length > capDigits) return Infinity;
    const s = step(V, b); V = s.next; b = s.nb; n++;
  }
  return n;
}
ok('Goodstein G(1) reaches 0 in 1 step', lengthTo0(1) === 1);
ok('Goodstein G(2) reaches 0 in 3 steps', lengthTo0(2) === 3);
ok('Goodstein G(3) reaches 0 in 5 steps', lengthTo0(3) === 5, '(3,3,3,2,1,0)');

// (b) the famous launches, exact.
ok('G(4) opens 4 → 26 → 41 → 60 → 83', (() => {
  let V = 4n, b = 2; const seq = [V];
  for (let i = 0; i < 4; i++) { const s = step(V, b); V = s.next; b = s.nb; seq.push(V); }
  return seq.join(',') === '4,26,41,60,83';
})());
ok('G(16) step 1 explodes to 3^27 − 1 = 7,625,597,484,986',
   step(16n, 2).next === 7625597484986n && (3n ** 27n) === 7625597484987n);

// Cantor normal form puts finite coefficients on the right, including in exponents.
ok('ordinal display at G(4) steps 3 and 4 uses right coefficients',
   render(hered(60n, 5), 'ω') === 'ω^(2)·2 + ω·2' &&
   render(hered(83n, 6), 'ω') === 'ω^(2)·2 + ω + 5');
ok('ordinal display also puts coefficients on the right inside exponents',
   render(hered(3n ** 6n, 3), 'ω') === 'ω^(ω·2)');
ok('integer display retains the ordinary coefficient convention',
   render(hered(60n, 5), '5') === '2·5^(2) + 2·5');

// (c) the base-bump leaves the hereditary tree UNCHANGED (so the ordinal it names is unchanged) —
//     it is the −1 alone that lowers the ordinal.
let bumpOK = true;
for (let m = 1; m <= 40 && bumpOK; m++) {
  let V = BigInt(m), b = 2;
  for (let k = 0; k < 60 && V > 0n && V.toString().length < 400; k++) {
    const t = hered(V, b); const bumped = val(t, b + 1);
    if (!treeEq(t, hered(bumped, b + 1))) { bumpOK = false; break; }
    V = bumped - 1n; b++;
  }
}
ok('base-bump preserves the hereditary tree (m = 1..40, 60 steps each)', bumpOK);

// (d) THE PROOF ENGINE: the shadow ordinal (CNF base ω) strictly decreases at EVERY step,
//     even while the integer skyrockets. Well-ordering then forces termination.
let ordOK = true, checked = 0, where = '';
for (let m = 1; m <= 40 && ordOK; m++) {
  let V = BigInt(m), b = 2;
  for (let k = 0; k < 60 && V > 0n && V.toString().length < 400; k++) {
    const before = hered(V, b);
    const s = step(V, b);
    const after = hered(s.next, s.nb);
    if (s.next > 0n && ordCmp(after, before) >= 0) { ordOK = false; where = `m=${m},k=${k}`; break; }
    checked++; V = s.next; b = s.nb;
  }
}
ok('shadow ordinal STRICTLY DECREASES every step', ordOK, `(${checked} steps checked${where ? ', failed ' + where : ''})`);

// (e) the integer rises while the ordinal falls — both shown, on the same step (G(16)).
ok('G(16): integer ↑ (16 → 7.6e12) while ordinal ↓ (ω^ω^ω strictly down)', (() => {
  const before = hered(16n, 2);                 // ω^(ω^ω)
  const s = step(16n, 2);                        // integer jumps to 7,625,597,484,986
  const after = hered(s.next, s.nb);
  return s.next > 16n && ordCmp(after, before) < 0 && render(before, 'ω') === 'ω^(ω^(ω))';
})());

console.log('\n— STATED, NOT COMPUTED HERE (cited; see README.md) —');
console.log('  · Goodstein\'s theorem (every sequence ends at 0)   Goodstein 1944');
console.log('  · Goodstein is UNPROVABLE in Peano arithmetic       Kirby & Paris 1982');
console.log('  · ε₀ is the proof-theoretic ordinal of PA            Gentzen 1936/1943');
console.log('  · First & Second incompleteness theorems        Gödel 1931; Rosser 1936');
console.log('  · Presburger arithmetic complete & decidable     Presburger 1929');
console.log('  · Real closed fields complete & decidable        Tarski 1951');
console.log('  · the seven misuse corrections                     Franzén 2005');

console.log(`\n${fails === 0 ? 'ALL CHECKS PASSED' : fails + ' CHECK(S) FAILED'}`);
process.exit(fails === 0 ? 0 : 1);
