Relationships Between the Busy Beaver Function and Mathematics I: What is the Smallest n such that BB(n) > ... ?
ACM SIGACT News · 11.06.2026 · 57 (2) · 22-35
DOI: 10.1145/3819804.3819808 ↗Kurz gefasst
Fachartikel in der Zeitschrift ACM SIGACT News, online erschienen am 11.06.2026. Verfasst von William Gasarch. Die Arbeit nennt 7 Literaturangaben.
Abstract (Originalsprache)
1 This is the first of (hopefully only) two papers In this paper we ask the following question: for a variety of computable functions f, what is the smallest n such that BB(n) > f(n). In the sequel, we will ask questions such as: What is the smallest Turing machine M such that Goldbach's conjecture is true iff M never halts? In both papers all concepts and definitions are due to others unless otherwise noted. For example, if I wrote We define a hierarchy similar to the Wainer hierarchy the definition we give is already known.
Zitieren
APA
Gasarch, W. (2026). Relationships Between the Busy Beaver Function and Mathematics I: What is the Smallest n such that BB(n) > ... ?. ACM SIGACT News, 57(2), 22-35. https://doi.org/10.1145/3819804.3819808
Vancouver
Gasarch W. Relationships Between the Busy Beaver Function and Mathematics I: What is the Smallest n such that BB(n) > ... ?. ACM SIGACT News. 2026;57(2):22-35. doi:10.1145/3819804.3819808
BibTeX
@article{Gasarch2026,
author = {Gasarch, William},
title = {Relationships Between the Busy Beaver Function and Mathematics I: What is the Smallest n such that BB(n) > ... ?},
journal = {ACM SIGACT News},
year = {2026},
volume = {57},
number = {2},
pages = {22--35},
doi = {10.1145/3819804.3819808}
}
EUVIMED