Logical independence

From BusyBeaverWiki
Revision as of 21:41, 18 November 2026 by Svennik (talk | contribs) (→New Foundations (NF): 16th November not 18th)
Jump to navigation Jump to search
Theory BB(n) is independent
ZF+Berkeley cardinal 1399
ZF+subtle cardinal 493
Zermelo-Fraenkel set theory 209
New Foundations / Mac Lane 192
Peano arithmetic 196
PRA —
EFA —
IΔ₀ —


For any recursively enumerable and arithmetically sound axiomatic theory T, there exists an integer NT such that T cannot prove the values of BB(n) for any n≥NT. For Zermelo–Fraenkel set theory (ZF), this value is known to be in the range:

6≤NZF≤211

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 NZF≤20 and NPA≤10, where PA 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 PA + “BB(n) = b” can prove the consistency of T, where b is the true value of BB(n).[1]

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

NZFC=NZF

Therefore we refer to ZF and NZF 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.

History of ZF independent TMs
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
The transition table of the ZF machine with 254 states. The initial state is 1.

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.

History of New Foundations (NF) independent TMs
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.

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.

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 xy, associated to the left.
  • A constant q. This is a fixed-point tester.
  • A binary function H(x,y). This is a merger between the K combinator and a Skolem function for function extensionality.

Define the convenient shorthands

K(x):=H(x,x),r:=(qq)q,b:=(q(qq))r.

The six axioms, with all free variables universally quantified, are:

No. Axiom Role
1 H(x,x)y=x Constant functions
2 bxyz=(xH(z,z))(yz) Combinatory composition
3 xy=y⟹(qx)y=b Positive equality test
4 xy≠y⟹(qx)y=r Negative equality test
5 xH(x,y)=yH(x,y)⟹x=y Extensionality witness
6 q(qq)≠qq Nondegeneracy

In particular, K(x)y=x 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.

What the symbols do

q is an equality tester:

(qx)y={b,xy=y,r,xy≠y.

H has two jobs. On the diagonal it constructs constant functions:

H(x,x)y=x.

Off the diagonal it supplies a witness to distinguish two functions whenever they are different:

x≠y⟹xH(x,y)≠yH(x,y).

b supplies the composition law

bxyz=x(K(z))(yz).

Here b and r 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)

For Peano Arithmetic, the ZF and NF independent machines are upper bounds. In general, a machine that is independent of a theory will also be independent of any theory with strictly lower consistency strength. For the theories in this article, Con(ZFC+Subtle)->Con(ZFC)->Con(NF)->Con(PA).

History of Peano Arithmetic (PA) independent TMs
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]

Large cardinals

These tables are for theories stronger than ZFC.

History of ZFC + "There exist arbitrarily large subtle cardinals" independent TMs
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")[6] 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 "0♯ 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 ZFC+{``There is a k-subtle cardinal``∣k∈ℕ} which is also between the strength of "strongly unfoldable" and "0♯ exists" on the large cardinal hierarchy.[7] However, the theory used by the BB(493) machine is also independent of this theory.

History of ZF + "There exists a Berkeley cardinal" independent TMs
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

  1. ↑ 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.

References

  1. ↑ 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
  2. ↑ 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)
  3. ↑ 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
  4. ↑ Riebel, Johannes (March 2023). The Undecidability of BB(748): Understanding Gödel's Incompleteness Theorems (PDF) (Bachelor's thesis). University of Augsburg.
  5. ↑ https://mathoverflow.net/questions/508137/interpreting-pa-with-only-adjunction-separation/508161
  6. ↑ H. Friedman, "Primitive Independence Results" (2002). Accessed February 2026.
  7. ↑ tlonuqbar, "What is the consistency strength of SRP (Stationary Ramsey Property)?" (2026). MathOverflow post, accessed February 2026.