Branches of Mathematics
Computability Theory
Citation Formats
General Reference
APA Style
BibTeX
Computability theory, also called recursion theory, is the branch of mathematical logic that studies which functions can be computed by an effective, mechanical procedure and which cannot, and how computable problems can be ranked by their relative difficulty.
Facts
Central QuestionWhich functions and sets are computable by some effective procedure at all, and among those that are not, how their difficulty can be measured and compared. 1 Key DebateWhat counts as an effective procedure in the first place. Alan Turing's 1936 formalization of computability gave the field its main working definition, one that converged with Kurt Godel's independent work on effectively generated theories to suggest that the notion, however it was formalized, was capturing something genuinely fixed rather than an artifact of any one formalism. 1 Cross-Tradition Connections
Sources
1. Wikipedia: Computability Theory
Wikimedia FoundationIntroduction sectionQuote, Introduction section
a branch of mathematical logic, computer science, and the theory of computation that originated in the 1930s with the study of computable functions and Turing degrees
1. Wikipedia: Computability Theory
Wikimedia FoundationRelative computability and the Turing degrees sectionQuote, Relative computability and the Turing degrees section
The Turing degree of a set gives a precise measure of how uncomputable the set is.
1. Wikipedia: Computability Theory
Wikimedia FoundationIntroduction section, Church-Turing thesis namingQuote, Introduction section, Church-Turing thesis naming
In 1952, these results led Kleene to coin the two names 'Church's thesis' and 'Turing's thesis'.
Stone-Weierstrass Theorem (Wikipedia)
Wikipedialead paragraphQuote, lead paragraph
Computability theory, also known as recursion theory, is a branch of mathematical logic, computer science, and the theory of computation that originated in the 1930s with the study of computable functions and Turing degrees.
Stone-Weierstrass Theorem (Wikipedia)
WikipediaTuring computability sectionQuote, Turing computability section
The main form of computability studied in the field was introduced by Turing in 1936.
Stone-Weierstrass Theorem (Wikipedia)
Wikipedialead sectionQuote, lead section
Godel's proofs show that the set of logical consequences of an effective first-order theory is a computably enumerable set.
Reader Challenges (0 open reader challenges)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.
View At A Past Year
The atlas records no dated fact of its own for this entry, so there is no other year to choose.