Busy Beaver Outruns All Arithmetically Definable Functions — E8 Intelligence Research
- 1Independent Researcher, United Kingdom
Abstract
FINDING: Busy Beaver function defines a non-computable hierarchy that outruns every arithmetically definable function, revealing a strict lattice-like stratification of uncomputability. | MATH: BB(n) = max steps before halting among n-state Turing machines; BB grows faster than any computable function f(n) (∀f computable, ∃N: BB(n) > f(n) ∀n>N). Arithmetical hierarchy: Σ₀=Π₀=Δ₀ (decidable), Σ₁ (computably enumerable), Π₁ (co-c.e.), … Σ_k, Π_k, Δ_k = Σ_k ∩ Π_k. Key theorem: BB is Σ₁-complete (equivalent to halting problem); iterated BB (BB₂, BB₃, …) climbs the hierarchy — BB^(k) is Σ_k-complete. Known values: BB(1)=1, BB(2)=6, BB(3)=21, BB(4)=107, BB(5)=47,176,870 (proven 2024 via Coq). | CONNECTION: The correspondence between BB-hierarchy and arithmetical hierarchy mirrors a **lattice duality**: each level k corresponds to quantifier alternation depth (∃∀∃…), analogous to crystallographic root system rank — the number of alternations acts like dimension. The growth ratios between succe
Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com
Related
- The Halting Boundary: Where Arithmetic Truth Outruns Formal Proof — E8 Intelligence Research
- K-holomorphic functions with definable real part
- Murmurations in L-Functions: Statistical Correlations in Elliptic Curves of Conductor 24 — E8 Intelligence Research
- The Busy Beaver Challenge: BB(5) Solved, Higher-Order Functions and Oracle Decidability — E8 Intelligence Research
- Scattered Sources, No Direct Discovery on Weyl Group Exponents or L-Functions — E8 Intelligence Research
BibTeX
@misc{caldin2026busy,
title = {{Busy Beaver Outruns All Arithmetically Definable Functions — E8 Intelligence Research}},
author = {Andrew Stewart Caldin},
howpublished = {Zenodo},
year = {2026},
month = oct,
doi = {10.5281/zenodo.23587264},
url = {https://zenodo.org/records/23587264},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Busy Beaver Outruns All Arithmetically Definable Functions — E8 Intelligence Research
AU - Andrew Stewart Caldin
PY - 2026
DA - 2026/10/23
PB - Zenodo
DO - 10.5281/zenodo.23587264
UR - https://zenodo.org/records/23587264
AB - FINDING: Busy Beaver function defines a non-computable hierarchy that outruns every arithmetically definable function, revealing a strict lattice-like stratification of uncomputability. | MATH: BB(n) = max steps before halting among n-state Turing machines; BB grows faster than any computable function f(n) (∀f computable, ∃N: BB(n) > f(n) ∀n>N). Arithmetical hierarchy: Σ₀=Π₀=Δ₀ (decidable), Σ₁ (computably enumerable), Π₁ (co-c.e.), … Σ_k, Π_k, Δ_k = Σ_k ∩ Π_k. Key theorem: BB is Σ₁-complete (equivalent to halting problem); iterated BB (BB₂, BB₃, …) climbs the hierarchy — BB^(k) is Σ_k-complete. Known values: BB(1)=1, BB(2)=6, BB(3)=21, BB(4)=107, BB(5)=47,176,870 (proven 2024 via Coq). | CONNECTION: The correspondence between BB-hierarchy and arithmetical hierarchy mirrors a **lattice duality**: each level k corresponds to quantifier alternation depth (∃∀∃…), analogous to crystallographic root system rank — the number of alternations acts like dimension. The growth ratios between succe Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com
ER -