Concept
Introduction
n2
3
4
5
6
...
Σ(n)
4
6
13
4098≥ 2↑↑↑5?Does not appear The Busy Beaver function Σ(n) grows faster than any computable function.
Hence, it is not computable; only a few values are known.
Computability theory originated in the 1930s, with the work of Kurt Gödel, Alonzo Church, Rózsa Péter, Alan Turing, Stephen Kleene, and Emil Post.
The fundamental results the researchers obtained established Turing computability as the correct formalization of the informal idea of effective calculation. In 1952, these results led Kleene to coin the two names "Church's thesis" and "Turing's thesis". Nowadays these are often considered as a single hypothesis, the Church–Turing thesis, which states that any function that is computable by an algorithm is a computable function. Although initially skeptical, by 1946 Gödel argued in favor of this thesis:
"Tarski has stressed in his lecture (and I think justly) the great importance of the concept of general recursiveness (or Turing's computability). It seems to me that this importance is largely due to the fact that with this concept one has for the first time succeeded in giving an absolute notion to an interesting epistemological notion, i.e., one not depending on the formalism chosen."
With a definition of effective calculation came the first proofs that there are problems in mathematics that cannot be effectively decided. In 1936, Church and Turing (inspired by techniques used by Gödel to prove his incompleteness theorems) independently demonstrated that the Entscheidungsproblem is not effectively decidable. This result showed that there is no algorithmic procedure that can correctly decide whether arbitrary mathematical propositions are true or false.
Many problems in mathematics have been shown to be undecidable after these initial examples were established. In 1947, Markov and Post published independent papers showing that the word problem for semigroups cannot be effectively decided. Extending this result, Pyotr Novikov and William Boone showed independently in the 1950s that the word problem for groups is not effectively solvable: there is no effective procedure that, given a word in a finitely presented group, will decide whether the element represented by the word is the identity element of the group. In 1970, Yuri Matiyasevich proved (using results of Julia Robinson) Matiyasevich's theorem, which implies that Hilbert's tenth problem has no effective solution; this problem asked whether there is an effective procedure to decide whether a Diophantine equation over the integers has a solution in the integers.
- ^Aaronson, Scott (2025-06-28). "BusyBeaver(6) is really quite large". Shtetl-Optimized. Retrieved 2025-08-05.
- ^Cite error: The named reference Rado_1962 was invoked but never defined (see the help page).
- ^Cite error: The named reference Soare_2011 was invoked but never defined (see the help page).
- ^ ^{a}^{b}Cite error: The named reference Kleene_1952 was invoked but never defined (see the help page).
- ^ ^{a}^{b}Cite error: The named reference Davis_1965 was invoked but never defined (see the help page).
- ^Cite error: The named reference Feferman_1990 was invoked but never defined (see the help page).
- ^Cite error: The named reference Church_1936a was invoked but never defined (see the help page).
- ^Cite error: The named reference Church_1936b was invoked but never defined (see the help page).
- ^Cite error: The named reference Turing_1936 was invoked but never defined (see the help page).
Cite error: There are tags or {{efn}} templates on this page, but the references will not show without a {{reflist|group=lower-alpha}} template or {{notelist}} template (see the help page).