Delphi.science

A beeping busy beaver machine for the Σ₂ form of P vs NP

Source: github.com/GregoryMorse/NP-complete/tree/67dadf083847b72f71…

Gregory Morse

Palomar Registrypalomar/PALOMAR-2026-11-11-000006Nov 11, 2026cs.CCscore 0

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…

RepositoryJSONText

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

API

curl /api/v1/records/palomar/PALOMAR-2026-11-11-000006
curl -X POST /api/v1/records/palomar/PALOMAR-2026-11-11-000006/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/palomar/PALOMAR-2026-11-11-000006/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'