{"id":"palomar/PALOMAR-2026-11-11-000006","url":"https://github.com/GregoryMorse/NP-complete/tree/67dadf083847b72f7177e1f96897d4f49547aea3/formal","json":"https://data.palomar-registry.org/entries/PALOMAR-2026-11-11-000006-v1.json","repo":"https://github.com/GregoryMorse/NP-complete","tags":["cs.CC","math.LO","msc:68Q15","msc:03D10","msc:68V15"],"score":0,"title":"A beeping busy beaver machine for the Σ₂ form of P vs NP","trust":"high","domain":"cs.CC","source":"palomar","authors":["Gregory Morse"],"reviews":0,"subject":"cs.CC","summary":"Explicit one-tape, two-symbol Turing machines with a designated beep state (Aaronson's beeping busy beaver convention), given as literal transition tables, together with core-Lean proofs (no Mathlib) that each machine, run from the blank tape, beeps only finitely often exactly when a stated Sigma_2 sentence holds. The flagship machine (278 states) is equivalent to the Sigma_2 form of P = NP: some candidate program decides a fixed self-padded NP-complete language within a polynomial clock on every instance. The equivalence of that sentence with P = NP is also proved in Lean…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"verified":true,"discussed":0,"published":"2026-11-11","reactions":{},"formalized":true}