Editing Computability theory (section)

==Introduction==
{{use list-defined references|date=August 2022}}
{| class="wikitable floatright"
|-
! ''n''
! width="30px" | 2
! width="30px" | 3
! width="30px" | 4
! width="50px" | 5
! width="120px" | 6
! width="120px" | 7
! width="30px" | ...
|-
! Σ(''n'')
| align="center" | 4
| align="center" | 6
| align="center" | 13
| align="center" | {{val|4098}}
| align="center" | {{color|#800000|>}} {{val|3.5|e=18267}}
| align="center" | {{color|#800000|>}} 10<sup>10<sup>10<sup>10<sup>{{val|18705353}}</sup></sup></sup></sup>
| align="center" | {{color|#800000|?}}
|-
| colspan="8" {{COther}} The [[Busy Beaver#The busy beaver function Σ|Busy Beaver]] function Σ(''n'') grows faster than any computable function.<br />Hence, it is not computable;<ref name="Rado_1962"/> 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]].<ref name="Soare_2011"/>{{efn|Many of these foundational papers are collected in {{citeref|Davis|1965|''The Undecidable'' (1965)|style=plain}} edited by [[Martin Davis (mathematician)|Martin Davis]]}}

The fundamental results the researchers obtained established [[computable function|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"<ref name="Kleene_1952"/>{{rp|page=300}} and "Turing's thesis".<ref name="Kleene_1952"/>{{rp|page=376}} 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:<!-- <ref name="Gödel_1946"/> --><ref name="Davis_1965"/>{{rp|page=84}}

{{blockquote|"[[Alfred Tarski|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."<!-- <ref name="Gödel_1946"/> --><ref name="Davis_1965"/>{{rp|page=84}}<ref name="Feferman_1990"/>}}

With a definition of effective calculation came the first proofs that there are problems in mathematics that cannot be [[recursive set|effectively decided]]. In 1936, Church<ref name="Church_1936a"/><ref name="Church_1936b"/> and Turing<ref name="Turing_1936"/> were inspired by techniques used by Gödel to prove his incompleteness theorems - in 1931, Gödel<!-- <ref name="Gödel_1931"/> --> independently demonstrated that the {{lang|de|[[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.{{efn|The [[list of undecidable problems]] gives additional examples.}} In 1947, [[Andrey Markov Jr.|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 (mathematician)|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 (mathematics)|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.