Logical independence: Difference between revisions
Move table of N_T values to its own section now that it has gotten really huge ... perhaps we should delete small theories until they have any actual results? |
|||
| (27 intermediate revisions by 4 users not shown) | |||
| Line 1: | Line 1: | ||
For any recursively enumerable and arithmetically sound axiomatic theory T, there exists an integer <math>N_T</math> such that T cannot prove the values of BB(n) for any <math>n \ge N_T</math>. Let <math>N_T</math> denote the least such integer. For [[wikipedia:Zermelo–Fraenkel_set_theory|Zermelo–Fraenkel set theory]] (ZF), this value is known to be in the range: | |||
<math display="block">6 \le N_{ZF} \le 209</math> | |||
This lower bound comes from the fact that [[BB(5)]] has been proven in Rocq.<ref group="footnote">The fact that this theorem has been proven in Rocq technically does not imply that the theorem must be provable in ZF, because the consistency strength of Rocq is actually higher than that of ZF. However, the BB(5) proof does not use any techniques that could not be formalized within ZF.</ref> The upper bound comes from an explicit TM which halts if and only if ZFC has a finite proof of contradiction. Assuming ZF is consistent and sound, then it cannot prove whether or not it is consistent, hence it cannot prove whether or not this specific TM halts. | |||
Harvey Friedman spoke of embedding consistency statements within turing machines in a [https://fomarchive.ugent.be/2004-March/008003.html 2004 posting] on the "Foundations of Mathematics" mailing list. Scott Aaronson conjectured in his [[Busy Beaver Frontier]] survey that <math>N_{ZF} \le 20</math> and <math>N_{PA} \le 10</math>, where <math>PA</math> refers to the theory of [https://en.wikipedia.org/wiki/Peano%20axioms Peano Arithmetic]. Scott also mentioned (crediting Oscar Cunningham for the observation) that if there is an n-state machine that halts if and only if T is inconsistent, then <math>PA</math> + “BB(n) = b” can prove the consistency of T, where b is the true value of BB(n).<ref name=":0">Scott Aaronson. 2020. [https://www.scottaaronson.com/papers/bb.pdf The Busy Beaver Frontier]. SIGACT News 51, 3 (August 2020), 32–54. https://doi.org/10.1145/3427361.3427369</ref> | |||
== Results by Theory == | |||
Most normal theories form a linear ordering with respect to consistency strength. All theories in the table below follow that linear order from top to bottom. Thus for any row X below Y, <math>N_X \le N_Y</math>. Rows are empty if no better results is known than the result inherited from a previous row. | |||
{| class="wikitable" | |||
! Theory | ! Theory | ||
! | ! Upper bound on <math>N_T</math> (states) | ||
|- | |- | ||
| ZF+Berkeley cardinal | | ZF+Berkeley cardinal | ||
| Line 10: | Line 20: | ||
| 493 | | 493 | ||
|- | |- | ||
| Zermelo-Fraenkel set theory | | Zermelo-Fraenkel set theory (ZF) / ZFC | ||
| | | 209 | ||
|- | |- | ||
| New Foundations / Mac Lane | | New Foundations + Axiom of Counting | ||
| 201 | |||
|- | |||
| Zermelo set theory | |||
| 209 (via ZF)<ref group="footnote">Zermelo set theory is a subtheory of ZF. For the version with Choice, the same upper bound follows from inclusion in ZFC and [[#Axiom of Choice|the equality of the ZF and ZFC thresholds]].</ref> | |||
|- | |||
| New Foundations (NF) / Mac Lane | |||
| 192 | | 192 | ||
|- | |- | ||
| Peano arithmetic | | Peano arithmetic (PA) | ||
| | | 196 (direct)<br />192 (conditional, via NF)<ref group="footnote">The 196-state PA construction also gives an upper bound for every row below PA. The smaller bound uses the proposed NF-to-PA transfer discussed in [[#Peano Arithmetic (PA)|the PA section]].</ref> | ||
|- | |- | ||
| PRA | | PRA / <math>I\Sigma_1</math> / <math>\mathrm{RCA}_0</math> / <math>\mathrm{WKL}_0</math> | ||
| | | | ||
|- | |||
| <math>\mathrm{EA}^{+}</math> | |||
| | |||
|- | |- | ||
| EFA | | EFA | ||
| | | | ||
|- | |- | ||
| | | <math>I\Delta_0+\Omega_1</math> / <math>S_2</math> | ||
| | | | ||
|- | |||
| <math>T^1_2</math> / <math>S^2_2</math> | |||
| | |||
|- | |||
| <math>\mathrm{PV}_1</math> / <math>S^1_2</math> | |||
| | |||
|- | |||
| <math>I\Delta_0</math> | |||
| | |||
|- | |||
| Open induction (<math>\mathrm{IOpen}</math>) | |||
| | |||
|- | |||
| <math>\mathrm{PA}^{-}</math> (discretely ordered semirings) | |||
| | |||
|- | |||
| Robinson arithmetic (<math>Q</math>) | |||
| | |||
|- | |||
| Tarski–Mostowski–Robinson <math>R</math> | |||
| | |||
|- | |||
| <math>R_0</math> | |||
| | |||
|} | |} | ||
== Axiom of Choice == | == Axiom of Choice == | ||
| Line 50: | Line 84: | ||
Although not a traditional turing machine, in 2012 Merlin Carl and Boris Z. Moroz constructed a [[Diophantine Equation]] which had solutions if and only if NBG (Von Neumann–Bernays–Gödel set theory) is inconsistent. NBG is a conservative extension of ZFC, so solving this equation is independent of ZFC.<ref>Carl, M., & Moroz, B. Z. (2012). ''On a Diophantine representation of the predicate of provability.'' Zapiski Nauchnykh Seminarov POMI, 407, 77-104. (Republished in 2014 in the Journal of Mathematical Sciences) [https://webdoc.sub.gwdg.de/ebook/serien/e/mpi_mathematik/2006/129.pdf (preprint)]</ref> | Although not a traditional turing machine, in 2012 Merlin Carl and Boris Z. Moroz constructed a [[Diophantine Equation]] which had solutions if and only if NBG (Von Neumann–Bernays–Gödel set theory) is inconsistent. NBG is a conservative extension of ZFC, so solving this equation is independent of ZFC.<ref>Carl, M., & Moroz, B. Z. (2012). ''On a Diophantine representation of the predicate of provability.'' Zapiski Nauchnykh Seminarov POMI, 407, 77-104. (Republished in 2014 in the Journal of Mathematical Sciences) [https://webdoc.sub.gwdg.de/ebook/serien/e/mpi_mathematik/2006/129.pdf (preprint)]</ref> | ||
== Zermelo–Fraenkel set theory (ZF) == | |||
There is no one authoritative source on the history of TMs independent of ZF, this is our best understanding of the history of TMs found. The results before 2026 are taken from Scott Aaronson's blog announcements and Busy Beaver Frontier or self-reported by the individuals who discovered them. The Aaronson-Yedida machine used a compiler called ''Laconic'', which was then updated with NQL or "Not Quite Laconic", while the 432 machines use a compiler built by Andrew J. Wade. Many machines after 2026 have been generated by AI without a formal compiler. | There is no one authoritative source on the history of TMs independent of ZF, this is our best understanding of the history of TMs found. The results before 2026 are taken from Scott Aaronson's blog announcements and Busy Beaver Frontier or self-reported by the individuals who discovered them. The Aaronson-Yedida machine used a compiler called ''Laconic'', which was then updated with NQL or "Not Quite Laconic", while the 432 machines use a compiler built by Andrew J. Wade. Many machines after 2026 have been generated by AI without a formal compiler. | ||
| Line 138: | Line 173: | ||
|[https://github.com/VladimirReshetnikov/ProveIt/tree/c9dc79323429112c698100f3226a6e4d56c8b782/Computability/BusyBeaver/Research/ZFC/k225-formal Github] | |[https://github.com/VladimirReshetnikov/ProveIt/tree/c9dc79323429112c698100f3226a6e4d56c8b782/Computability/BusyBeaver/Research/ZFC/k225-formal Github] | ||
|[https://github.com/VladimirReshetnikov/ProveIt/tree/c9dc79323429112c698100f3226a6e4d56c8b782/Computability/BusyBeaver/Research/ZFC/k225-formal/verification/k215 Rocq file] | |[https://github.com/VladimirReshetnikov/ProveIt/tree/c9dc79323429112c698100f3226a6e4d56c8b782/Computability/BusyBeaver/Research/ZFC/k225-formal/verification/k215 Rocq file] | ||
|- | |||
|209 | |||
|12 Nov 2026 | |||
|James Chang formalized with ChatGPT | |||
|[https://github.com/jamesyc/BusyBeaver/commit/286324f9ad106bbeab32b70404e7a82be2cd660d Github]([https://discord.com/channels/960643023006490684/960643023530762341/1570618968060858439 discord message]) | |||
|[https://github.com/jamesyc/BusyBeaver/tree/main/ZF209/ProofSources Lean] | |||
|- | |- | ||
|211 | |211 | ||
| Line 148: | Line 189: | ||
Wade's 432-state champion also omits the [[wikipedia:Axiom_of_regularity|axiom of regularity]], as ZF-regularity is also equiconsistent with ZF. | Wade's 432-state champion also omits the [[wikipedia:Axiom_of_regularity|axiom of regularity]], as ZF-regularity is also equiconsistent with ZF. | ||
== New Foundations (NF) == | |||
''New Foundations'' is a formal theory created by W.V.O. Quine in 1937, based around the principle of stratified comprehension of sets. It is known to be stronger than Peano Arithmetic and second-order arithmetic, but weaker than ZF. The Github page contains a proof in Lean that it is equiconsistent with Mac Lane set theory, which is a novel result as of the time of writing (November 2026). Mac Lane set theory is far more mainstream than NF, so the following machine could be seen as an efficient way of determining which Busy Beaver value MAC cannot verify. | ''New Foundations'' is a formal theory created by W.V.O. Quine in 1937, based around the principle of stratified comprehension of sets. It is known to be stronger than Peano Arithmetic and second-order arithmetic, but weaker than ZF. The Github page contains a proof in Lean that it is equiconsistent with Mac Lane set theory, which is a novel result as of the time of writing (November 2026). Mac Lane set theory is far more mainstream than NF, so the following machine could be seen as an efficient way of determining which Busy Beaver value MAC cannot verify. | ||
| Line 172: | Line 213: | ||
|- | |- | ||
|192 | |192 | ||
| | |16 November 2026 | ||
|@wlad-svennik | |@wlad-svennik | ||
| | | | ||
| Line 178: | Line 219: | ||
|} | |} | ||
=== User-friendly theory === | |||
The TM searches for an inconsistency in the theory "'''FunctionNF'''". It is defined to equal stratified λ-calculus minus pairing, minus case-expressions, plus full functional extensionality, plus an equality checker.<pre>Terms t ::= x | t u | λx.t | (s ≐ t) | ⊤ | ⊥ | The TM searches for an inconsistency in the theory "'''FunctionNF'''". It is defined to equal stratified λ-calculus minus pairing, minus case-expressions, plus full functional extensionality, plus an equality checker.<pre>Terms t ::= x | t u | λx.t | (s ≐ t) | ⊤ | ⊥ | ||
| Line 197: | Line 239: | ||
The logic is ordinary first-order logic with equality, so unstratified ''formulas'' are allowed. Only λ is restricted. | The logic is ordinary first-order logic with equality, so unstratified ''formulas'' are allowed. Only λ is restricted. | ||
It's not obvious, but the above suffices to prove the ''Axiom of Infinity'', i.e. that the set of natural numbers exists and has all of its expected properties. It's then possible to define the set of real numbers in any of the usual ways, and do nearly all of extant mathematics. | |||
=== NF vs Mac Lane vs other set theories === | |||
The Github link contains proofs in Lean that: | The Github link contains proofs in Lean that: | ||
| Line 208: | Line 253: | ||
So overall, the machine halts iff there exists an inconsistency in ''any'' of the above theories. Regardless, Mac Lane set theory is actually ''weaker'' than NF in terms of ''intepretability strength'', as opposed to just consistency strength. | So overall, the machine halts iff there exists an inconsistency in ''any'' of the above theories. Regardless, Mac Lane set theory is actually ''weaker'' than NF in terms of ''intepretability strength'', as opposed to just consistency strength. | ||
''' | If we add the ''Axiom of Counting'' (AxCount) to NF, which is the rather tautological-looking axiom<blockquote><nowiki>For any finite set S, |S| = |{{x}</nowiki> : x ∈ S}| (i.e. the number of elements of S doesn't change when you replace each element x with the singleton {x})</blockquote>then it's sufficient to prove Con(Z). As of the time of this writing (November 2026) we've used this to obtain a machine that is smaller (201 states) than any machine of Zermelo-strength or above. | ||
ZFC can prove Con(NF + AxCount). | |||
=== Implementation theory: The combinatory calculus === | |||
FunctionalNF is not implemented directly. Instead, a massively leaner form is implemented, in the form of a [https://en.wikipedia.org/wiki/combinatory_logic combinatory logic] which consists of just three nonlogical primitives: | FunctionalNF is not implemented directly. Instead, a massively leaner form is implemented, in the form of a [https://en.wikipedia.org/wiki/combinatory_logic combinatory logic] which consists of just three nonlogical primitives: | ||
* Binary application <math>xy</math>, associated to the left. | * Binary application <math>xy</math>, associated to the left. | ||
* A constant <math>q</math>. This is a fixed-point tester. | * A constant <math>q</math>. This is a fixed-point tester. | ||
* A binary function <math>H(x,y)</math>. This is a | * A binary function <math>H(x,y)</math>. This is a merger between the ''K'' combinator and a [https://en.wikipedia.org/wiki/skolem_function Skolem function] for function extensionality. | ||
Define the convenient shorthands | Define the convenient shorthands | ||
| Line 258: | Line 306: | ||
In particular, <math>K(x)y=x</math> follows immediately from axiom 1. It is not a separate axiom. | In particular, <math>K(x)y=x</math> follows immediately from axiom 1. It is not a separate axiom. | ||
=== Fragment of First-Order Logic === | |||
Notably, we '''do not''' implement the whole of First-Order Logic: The quantifier ∀ can be defined ''internally'' to CombNF / FunctionalNF. Moreover, we don't even implement variables thanks to our use of combinatory logic. The only fragment of First-Order Logic we implement consists of "=", the above function symbols, and propositional logic. This is similar to [https://en.wikipedia.org/wiki/primitive_recursive_arithmetic Primitive Recursive Arithmetic] and [https://en.wikipedia.org/wiki/system_T System T]. | Notably, we '''do not''' implement the whole of First-Order Logic: The quantifier ∀ can be defined ''internally'' to CombNF / FunctionalNF. Moreover, we don't even implement variables thanks to our use of combinatory logic. The only fragment of First-Order Logic we do implement consists of "=", the above function symbols, and propositional logic. This is similar to [https://en.wikipedia.org/wiki/primitive_recursive_arithmetic Primitive Recursive Arithmetic] and [https://en.wikipedia.org/wiki/system_T System T]. | ||
Observe that:<blockquote>∀ := λP.(P ≐ λx.⊤) | |||
¬ := λp.(p ≐ ⊥) | |||
∃ := λP. ¬ (∀ λx. ¬ (P x))</blockquote> | |||
=== What the symbols do === | |||
<math>q</math> is an equality tester: | <math>q</math> is an equality tester: | ||
| Line 289: | Line 342: | ||
The formalized proof for this machine's NF-undecidability is formalized as an ''external'' Lean metatheorem rather than a completed PA-internal derivation. As of this publication, a fresh independent clean build and community review have not been reported. | The formalized proof for this machine's NF-undecidability is formalized as an ''external'' Lean metatheorem rather than a completed PA-internal derivation. As of this publication, a fresh independent clean build and community review have not been reported. | ||
== Peano Arithmetic (PA) == | |||
The ZF bound applies to PA because ZF proves the arithmetical theorems of PA. In turn, a proof of an exact Busy Beaver value in any theory listed below PA would give a PA proof of that same value. For <math>n \ge 196</math>, a proof of <math>BB(n)=b</math> would let PA decide whether the 196-state machine halts by padding it to <math>n</math> states and checking its first <math>b</math> steps. | |||
{| class="wikitable" | {| class="wikitable" | ||
| Line 306: | Line 358: | ||
|[https://github.com/LegionMammal978/turing_machine_explorer/blob/main/pa.py Github] | |[https://github.com/LegionMammal978/turing_machine_explorer/blob/main/pa.py Github] | ||
| | | | ||
|- | |||
|196 | |||
|12 Nov 2026 | |||
|James Chang formalized with ChatGPT | |||
|[https://github.com/jamesyc/BusyBeaver/commit/64ff1b3047b951b25129d4ab897ccf1728b66dbf Github] | |||
|[https://github.com/jamesyc/BusyBeaver/tree/main/PA196/ProofSources Lean] | |||
|- | |||
|} | |} | ||
This machine takes Wade's ZF champion and replaces the set theory axioms with one axiom schema of "adjunction + separation", which has been shown to interpret PA.<ref>https://mathoverflow.net/questions/508137/interpreting-pa-with-only-adjunction-separation/508161</ref> | This machine takes Wade's ZF champion and replaces the set theory axioms with one axiom schema of "adjunction + separation", which has been shown to interpret PA.<ref>https://mathoverflow.net/questions/508137/interpreting-pa-with-only-adjunction-separation/508161</ref> | ||
=== Large cardinals | The 192-state entries use the proposed transfer of the NF result to PA under the assumption that Mac Lane set theory is consistent. The published Lean theorem establishes in the metatheory that the machine halts exactly when NF proves a contradiction.<ref>[https://github.com/wlad-svennik/notes/releases/tag/nf192-countdown New Foundations: 192-state countdown machine and Lean verification], release notes.</ref> To obtain the 192-state bound for PA, one also needs to show that PA cannot prove this particular machine runs forever. For example, it would suffice to derive in PA that its nonhalting implies the consistency of PA, and then apply Gödel's second incompleteness theorem. The separate 196-state construction directly establishes that PA proves neither halting nor nonhalting for its machine.<ref>James Chang, [https://github.com/jamesyc/BusyBeaver/commit/64ff1b3047b951b25129d4ab897ccf1728b66dbf PA196 proof package].</ref> | ||
=== Weaker arithmetical theories === | |||
Even <math>R_0</math>, a proper subtheory of Tarski–Mostowski–Robinson <math>R</math>, proves every true individual halting assertion because it proves all true <math>\Sigma_1</math> sentences in the usual language of arithmetic.<ref>Taishi Kurahashi and Albert Visser, [https://doi.org/10.1017/jsl.2024.84 Certified Σ₁-Sentences], §2, Theorem 2.3.</ref> Between Robinson arithmetic <math>Q</math> and bounded induction <math>I\Delta_0</math> lie <math>\mathrm{PA}^{-}</math>, the theory of discretely ordered semirings, and <math>\mathrm{IOpen}</math>, which adds induction for quantifier-free formulas.<ref>Kazuyuki Tanaka, [https://hep.tsinghua.edu.cn/~liwj/AU2024-lec03-08.pdf Logic and Computation I, Part 3a. Formal Arithmetic], Corollary 3.43.</ref> Further up, <math>\mathrm{EA}^{+}</math> adds total superexponentiation to EFA. It proves the consistency of <math>I\Delta_0</math>, which EFA cannot prove.<ref>Samuel R. Buss, [https://mathweb.ucsd.edu/~sbuss/ResearchWeb/handbookII/ChapterII.pdf First-Order Proof Theory of Arithmetic], §4.3.</ref> | |||
Theories grouped in one arithmetic row have the same Busy Beaver threshold. For fixed standard <math>n</math> and <math>b</math>, a counterexample to <math>BB(n)\le b</math> is a halting computation of an <math>n</math>-state machine lasting more than <math>b</math> steps. A proposed computation can be checked in polynomial time in the length of its complete history. When <math>BB(n)=b</math> is true, a particular halting run witnesses the matching lower bound. | |||
With this explicit history coding, <math>\mathrm{PV}_1</math> and <math>S^1_2</math> agree on the universal equations expressing the upper bounds. Full bounded arithmetic <math>S_2</math> and <math>I\Delta_0+\Omega_1</math> agree on sentences in their common arithmetical language.<ref>Jan Krajíček, [https://www.karlin.mff.cuni.cz/~krajicek/kniha.pdf Bounded Arithmetic, Propositional Logic, and Complexity Theory], Lemma 5.2.15 and Theorem 5.3.4.</ref> Buss's conservation theorem similarly gives <math>T^1_2</math> and <math>S^2_2</math> the same provable upper bounds.<ref>Samuel R. Buss, [https://mathweb.ucsd.edu/~sbuss/ResearchWeb/BAaxioms/camera.pdf Axiomatizations and Conservation Results for Fragments of Bounded Arithmetic].</ref> Finally, <math>I\Sigma_1</math>, <math>\mathrm{RCA}_0</math> and <math>\mathrm{WKL}_0</math> agree with PRA on <math>\Pi^0_2</math> arithmetic sentences, which suffices for all four to share a threshold.<ref>Jeremy Avigad, [https://www.andrew.cmu.edu/user/avigad/Papers/omegasubmodels.pdf Notes on Π¹₁-conservativity, ω-submodels, and the collection schema], §2.</ref> | |||
== Large cardinals == | |||
These tables are for theories stronger than ZFC. | These tables are for theories stronger than ZFC. | ||
Latest revision as of 03:06, 19 November 2026
For any recursively enumerable and arithmetically sound axiomatic theory T, there exists an integer such that T cannot prove the values of BB(n) for any . Let denote the least such integer. For Zermelo–Fraenkel set theory (ZF), this value is known to be in the range:
This lower bound comes from the fact that BB(5) has been proven in Rocq.[footnote 1] The upper bound comes from an explicit TM which halts if and only if ZFC has a finite proof of contradiction. Assuming ZF is consistent and sound, then it cannot prove whether or not it is consistent, hence it cannot prove whether or not this specific TM halts.
Harvey Friedman spoke of embedding consistency statements within turing machines in a 2004 posting on the "Foundations of Mathematics" mailing list. Scott Aaronson conjectured in his Busy Beaver Frontier survey that and , where refers to the theory of Peano Arithmetic. Scott also mentioned (crediting Oscar Cunningham for the observation) that if there is an n-state machine that halts if and only if T is inconsistent, then + “BB(n) = b” can prove the consistency of T, where b is the true value of BB(n).[1]
Results by Theory
Most normal theories form a linear ordering with respect to consistency strength. All theories in the table below follow that linear order from top to bottom. Thus for any row X below Y, . Rows are empty if no better results is known than the result inherited from a previous row.
| Theory | Upper bound on (states) |
|---|---|
| ZF+Berkeley cardinal | 1399 |
| ZF+subtle cardinal | 493 |
| Zermelo-Fraenkel set theory (ZF) / ZFC | 209 |
| New Foundations + Axiom of Counting | 201 |
| Zermelo set theory | 209 (via ZF)[footnote 2] |
| New Foundations (NF) / Mac Lane | 192 |
| Peano arithmetic (PA) | 196 (direct) 192 (conditional, via NF)[footnote 3] |
| PRA / / / | |
| EFA | |
| / | |
| / | |
| / | |
| Open induction () | |
| (discretely ordered semirings) | |
| Robinson arithmetic () | |
| Tarski–Mostowski–Robinson | |
Axiom of Choice
Due to Shoenfield's absoluteness theorem, it is known that any TM proven non-halting in ZFC can also be proven non-halting in ZF (and the converse is trivially true), therefore
Therefore we refer to ZF and throughout this article since adding the Axiom of Choice does not have any effect on Turing machine decidability.
History
In a broad sense, the concept of a mechanical or computable procedure that was equivalent to the consistency of a formal theory was discovered by Kurt Gödel's incompleteness theorem, which is notable for introducing a meta-mathematical encoding of the statement that "T can prove statement S" (the provability predicate) which is used in all these machines. This was further clarified by Alan Turing and Alonzo Church's work on a formal definition of computability.
Although not a traditional turing machine, in 2012 Merlin Carl and Boris Z. Moroz constructed a Diophantine Equation which had solutions if and only if NBG (Von Neumann–Bernays–Gödel set theory) is inconsistent. NBG is a conservative extension of ZFC, so solving this equation is independent of ZFC.[2]
Zermelo–Fraenkel set theory (ZF)
There is no one authoritative source on the history of TMs independent of ZF, this is our best understanding of the history of TMs found. The results before 2026 are taken from Scott Aaronson's blog announcements and Busy Beaver Frontier or self-reported by the individuals who discovered them. The Aaronson-Yedida machine used a compiler called Laconic, which was then updated with NQL or "Not Quite Laconic", while the 432 machines use a compiler built by Andrew J. Wade. Many machines after 2026 have been generated by AI without a formal compiler.
Note that only the results with a linked formal verification are known to have such a verification, with the 7910 machine in particular relying on a result from Harvey Friedman that has no published proof.
| States | Date | Discoverer | Source | Verification |
|---|---|---|---|---|
| 7910 | May 2016 | Adam Yedidia and Scott Aaronson | Yedidia and Aaronson 2016[3] | |
| 1919 | 15 May 2016 | Stefan O'Rear | Github NQL file, Metamath Group Announcement | |
| 748 | May 2016 | Stefan O’Rear | Github NQL, Busy Beaver Frontier[1] | |
| 745 | July 2023 | Johannes Riebel | Riebel 2023 Bachelor Thesis[4] | |
| 643 | July 2024 | Rohan Ridenour | Github NQL, Aaronson Announcement | |
| 636 | 31 August 2024 | Rohan Ridenour | Github NQL (commit) | |
| 588 | 12 July 2025 | Andrew J. Wade | Github NQL (commit) | |
| 549 | 16 July 2025 | Andrew J. Wade | Github NQL (commit) | |
| 432 | 19 Aug 2025 | Andrew J. Wade | git commit | |
| 335 | 11 Oct 2026 | Jeff Ketchersid | discord message | |
| 254 | 13 Oct 2026 | Mira with use of ChatGPT, formalized by Jeff Ketchersid with Claude | Github | Rocq file |
| 230 | 19 Oct 2026 | Elliot Glazer with use of ChatGPT, formalized with GPT and Claude | Github | Rocq file |
| 215 | 21 Oct 2026 | Vladimir Reshetnikov formalized with Claude | Github | Rocq file |
| 209 | 12 Nov 2026 | James Chang formalized with ChatGPT | Github(discord message) | Lean |
| 211 | 17 Nov 2026 | Shivam Patel | Paper | Lean proof and replay |

Wade's 432-state champion also omits the axiom of regularity, as ZF-regularity is also equiconsistent with ZF.
New Foundations (NF)
New Foundations is a formal theory created by W.V.O. Quine in 1937, based around the principle of stratified comprehension of sets. It is known to be stronger than Peano Arithmetic and second-order arithmetic, but weaker than ZF. The Github page contains a proof in Lean that it is equiconsistent with Mac Lane set theory, which is a novel result as of the time of writing (November 2026). Mac Lane set theory is far more mainstream than NF, so the following machine could be seen as an efficient way of determining which Busy Beaver value MAC cannot verify.
| States | Date | Discoverer | Source | Verification |
|---|---|---|---|---|
| 210 | 8 November 2026 | @wlad-svennik | [1] | |
| 198 | 12 November 2026 | @wlad-svennik | [2] | |
| 192 | 16 November 2026 | @wlad-svennik | [3] |
User-friendly theory
The TM searches for an inconsistency in the theory "FunctionNF". It is defined to equal stratified λ-calculus minus pairing, minus case-expressions, plus full functional extensionality, plus an equality checker.
Terms t ::= x | t u | λx.t | (s ≐ t) | ⊤ | ⊥
Depth Each subterm occurrence has a depth relative to the term it sits in:
the term itself 0
in t u at depth n: t at n+1, u at n
in λx.t at depth n: t at n−1
in s ≐ t at depth n: s and t at n
Formation λx.t is a term iff every free occurrence of x in t has depth 0 in t.
Nothing else is constrained: other variables may occur at any depths.
Axioms (β) (λx.t) u = t[u/x]
(ext) (∀x. f x = g x) → f = g
(≐) s = t → (s ≐ t) = ⊤ s ≠ t → (s ≐ t) = ⊥
(nt) ⊤ ≠ ⊥
The logic is ordinary first-order logic with equality, so unstratified formulas are allowed. Only λ is restricted.
It's not obvious, but the above suffices to prove the Axiom of Infinity, i.e. that the set of natural numbers exists and has all of its expected properties. It's then possible to define the set of real numbers in any of the usual ways, and do nearly all of extant mathematics.
NF vs Mac Lane vs other set theories
The Github link contains proofs in Lean that:
- NF interprets FunctionNF (which is very short),
- FunctionNF in turn interprets NFU+Infinity (which is similar to Specker's proof of the "Axiom of Infinity" within NF),
- NFU+Infinity interprets NF, which is a novel and hard result that is not yet found in the literature,
- NFU+Infinity interprets Mac Lane set theory,
- Mac Lane set theory interprets TSTI (Theory of Simple Types plus (Axiom of) Infinity),
- TSTI is equiconsistent with NFU+Infinity.
So overall, the machine halts iff there exists an inconsistency in any of the above theories. Regardless, Mac Lane set theory is actually weaker than NF in terms of intepretability strength, as opposed to just consistency strength.
If we add the Axiom of Counting (AxCount) to NF, which is the rather tautological-looking axiom
For any finite set S, |S| = |{{x} : x ∈ S}| (i.e. the number of elements of S doesn't change when you replace each element x with the singleton {x})
then it's sufficient to prove Con(Z). As of the time of this writing (November 2026) we've used this to obtain a machine that is smaller (201 states) than any machine of Zermelo-strength or above.
ZFC can prove Con(NF + AxCount).
Implementation theory: The combinatory calculus
FunctionalNF is not implemented directly. Instead, a massively leaner form is implemented, in the form of a combinatory logic which consists of just three nonlogical primitives:
- Binary application , associated to the left.
- A constant . This is a fixed-point tester.
- A binary function . This is a merger between the K combinator and a Skolem function for function extensionality.
Define the convenient shorthands
The six axioms, with all free variables universally quantified, are:
| No. | Axiom | Role |
|---|---|---|
| 1 | Constant functions | |
| 2 | Combinatory composition | |
| 3 | Positive equality test | |
| 4 | Negative equality test | |
| 5 | Extensionality witness | |
| 6 | Nondegeneracy |
In particular, follows immediately from axiom 1. It is not a separate axiom.
Fragment of First-Order Logic
Notably, we do not implement the whole of First-Order Logic: The quantifier ∀ can be defined internally to CombNF / FunctionalNF. Moreover, we don't even implement variables thanks to our use of combinatory logic. The only fragment of First-Order Logic we do implement consists of "=", the above function symbols, and propositional logic. This is similar to Primitive Recursive Arithmetic and System T.
Observe that:
∀ := λP.(P ≐ λx.⊤)
¬ := λp.(p ≐ ⊥)
∃ := λP. ¬ (∀ λx. ¬ (P x))
What the symbols do
is an equality tester:
has two jobs. On the diagonal it constructs constant functions:
Off the diagonal it supplies a witness to distinguish two functions whenever they are different:
supplies the composition law
Here and are terms, not primitive constants.
Once again, we do not implement the whole of First-Order Logic.
The formalized proof for this machine's NF-undecidability is formalized as an external Lean metatheorem rather than a completed PA-internal derivation. As of this publication, a fresh independent clean build and community review have not been reported.
Peano Arithmetic (PA)
The ZF bound applies to PA because ZF proves the arithmetical theorems of PA. In turn, a proof of an exact Busy Beaver value in any theory listed below PA would give a PA proof of that same value. For , a proof of would let PA decide whether the 196-state machine halts by padding it to states and checking its first steps.
| States | Date | Discoverer | Source | Verification |
|---|---|---|---|---|
| 372 | 11 February 2026 | @LegionMammal978 (Matthew House) | Github | |
| 196 | 12 Nov 2026 | James Chang formalized with ChatGPT | Github | Lean |
This machine takes Wade's ZF champion and replaces the set theory axioms with one axiom schema of "adjunction + separation", which has been shown to interpret PA.[5]
The 192-state entries use the proposed transfer of the NF result to PA under the assumption that Mac Lane set theory is consistent. The published Lean theorem establishes in the metatheory that the machine halts exactly when NF proves a contradiction.[6] To obtain the 192-state bound for PA, one also needs to show that PA cannot prove this particular machine runs forever. For example, it would suffice to derive in PA that its nonhalting implies the consistency of PA, and then apply Gödel's second incompleteness theorem. The separate 196-state construction directly establishes that PA proves neither halting nor nonhalting for its machine.[7]
Weaker arithmetical theories
Even , a proper subtheory of Tarski–Mostowski–Robinson , proves every true individual halting assertion because it proves all true sentences in the usual language of arithmetic.[8] Between Robinson arithmetic and bounded induction lie , the theory of discretely ordered semirings, and , which adds induction for quantifier-free formulas.[9] Further up, adds total superexponentiation to EFA. It proves the consistency of , which EFA cannot prove.[10]
Theories grouped in one arithmetic row have the same Busy Beaver threshold. For fixed standard and , a counterexample to is a halting computation of an -state machine lasting more than steps. A proposed computation can be checked in polynomial time in the length of its complete history. When is true, a particular halting run witnesses the matching lower bound.
With this explicit history coding, and agree on the universal equations expressing the upper bounds. Full bounded arithmetic and agree on sentences in their common arithmetical language.[11] Buss's conservation theorem similarly gives and the same provable upper bounds.[12] Finally, , and agree with PRA on arithmetic sentences, which suffices for all four to share a threshold.[13]
Large cardinals
These tables are for theories stronger than ZFC.
| States | Date | Discoverer | Source | Verification |
|---|---|---|---|---|
| 493 | 25 February 2026 | @LegionMammal978 | Github |
This machine takes Wade's ZF champion and adds the axiom of Choice and a statement from Harvey Friedman (Proposition 4.3 of "Primitive Independence Results")[14] which Friedman showed to be equivalent to "There exist arbitrarily large subtle cardinals" over ZFC.
For reference, this theory is between the strength of "strongly unfoldable" and " exists" on the large cardinal hierarchy on Wikipedia.
Note: The initial machine produced in 2016 by Yedidia and Aaronson is designed to halt iff a certain statement created by Harvey Friedman is true.[1] According to Friedman (without a published proof), this statement is independent of the theory "Stationary Ramsey Property" or SRP, which is equiconsistent with the theory which is also between the strength of "strongly unfoldable" and " exists" on the large cardinal hierarchy.[15] However, the theory used by the BB(493) machine is also independent of this theory.
| States | Date | Discoverer | Source | Verification |
|---|---|---|---|---|
| 1399 | 8 November 2026 | @Meganeuridae | Github | Rocq file |
Berkeley cardinals are perhaps the strongest family of large cardinals considered, initially proposed by Hugh Woodin at a lecture at UC Berkeley as an axiom that was "obviously inconsistent".[citation needed] However, no inconsistency has been found and many people now believe it may be consistent. Berkeley cardinals are known to be inconsistent with the axiom of choice.
Footnotes
- ↑ The fact that this theorem has been proven in Rocq technically does not imply that the theorem must be provable in ZF, because the consistency strength of Rocq is actually higher than that of ZF. However, the BB(5) proof does not use any techniques that could not be formalized within ZF.
- ↑ Zermelo set theory is a subtheory of ZF. For the version with Choice, the same upper bound follows from inclusion in ZFC and the equality of the ZF and ZFC thresholds.
- ↑ The 196-state PA construction also gives an upper bound for every row below PA. The smaller bound uses the proposed NF-to-PA transfer discussed in the PA section.
References
- ↑ 1.0 1.1 1.2 Scott Aaronson. 2020. The Busy Beaver Frontier. SIGACT News 51, 3 (August 2020), 32–54. https://doi.org/10.1145/3427361.3427369
- ↑ Carl, M., & Moroz, B. Z. (2012). On a Diophantine representation of the predicate of provability. Zapiski Nauchnykh Seminarov POMI, 407, 77-104. (Republished in 2014 in the Journal of Mathematical Sciences) (preprint)
- ↑ A. Yedidia and S. Aaronson. A relatively small Turing machine whose behavior is independent of set theory. Complex Systems, (25):4, 2016. https://arxiv.org/abs/1605.04343
- ↑ Riebel, Johannes (March 2023). The Undecidability of BB(748): Understanding Gödel's Incompleteness Theorems (PDF) (Bachelor's thesis). University of Augsburg.
- ↑ https://mathoverflow.net/questions/508137/interpreting-pa-with-only-adjunction-separation/508161
- ↑ New Foundations: 192-state countdown machine and Lean verification, release notes.
- ↑ James Chang, PA196 proof package.
- ↑ Taishi Kurahashi and Albert Visser, Certified Σ₁-Sentences, §2, Theorem 2.3.
- ↑ Kazuyuki Tanaka, Logic and Computation I, Part 3a. Formal Arithmetic, Corollary 3.43.
- ↑ Samuel R. Buss, First-Order Proof Theory of Arithmetic, §4.3.
- ↑ Jan Krajíček, Bounded Arithmetic, Propositional Logic, and Complexity Theory, Lemma 5.2.15 and Theorem 5.3.4.
- ↑ Samuel R. Buss, Axiomatizations and Conservation Results for Fragments of Bounded Arithmetic.
- ↑ Jeremy Avigad, Notes on Π¹₁-conservativity, ω-submodels, and the collection schema, §2.
- ↑ H. Friedman, "Primitive Independence Results" (2002). Accessed February 2026.
- ↑ tlonuqbar, "What is the consistency strength of SRP (Stationary Ramsey Property)?" (2026). MathOverflow post, accessed February 2026.