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. This description is adapted from Wikipedia contributors under CC BY-SA 4.0; changes were made. https://creativecommons.org/licenses/by-sa/4.0/
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 Gödel'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 Classification
Pure or Applied Connections
Associated With
Includes
Source Ackermann Function (Wikipedia)
Source Wikipedia: Busy beaver
Source Emil Leon Post (Wikipedia)
Source Greibach's theorem, Wikipedia
Source Wikipedia: Joseph R. Shoenfield
Source Kleene's Recursion Theorem (Wikipedia)
Source Myhill isomorphism theorem, Wikipedia
Source Post's theorem, Wikipedia
Source Primitive Recursive Function (Wikipedia)
Source Rice-Shapiro theorem, Wikipedia
Source Wikipedia: Smn theorem
Source Stephen Cole Kleene (Wikipedia)
Source Trakhtenbrot's theorem (Wikipedia)
Source Wikipedia: Turing machine
Source Turing's proof - Wikipedia
Sources
1. Wikipedia: Computability Theory
Wikimedia FoundationIntroduction 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
Relative computability and the Turing degrees section
The Turing degree of a set gives a precise measure of how uncomputable the set is.
Introduction
In 1952, these results led Kleene to coin the two names "Church's thesis" and "Turing's thesis".
Lead section
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.
Turing computability
The main form of computability studied in the field was introduced by Turing in 1936.
Relationships between definability, proof and computability
Gödel's proofs show that the set of logical consequences of an effective first-order theory is a computably enumerable set, and that if the theory is strong enough this set will be uncomputable.
View the Source Turing's proof - Wikipedia
Includes: Turing's Proof, LeadQuote, Includes: Turing's Proof, Lead
Turing's proof is a proof by Alan Turing submitted on 12 November 1936
Post's theorem, Wikipedia
Includes: Post's Theorem, Lead sentenceQuote, Includes: Post's Theorem, Lead sentence
In computability theory, Post's theorem, named after Emil Post, describes the connection between the arithmetical hierarchy and th
Ackermann Function (Wikipedia)
Includes: Ackermann Function, Lead sentenceQuote, Includes: Ackermann Function, Lead sentence
In computability theory, the Ackermann function, named after Wilhelm Ackermann, is one of the simplest and earliest-discovered exa
Primitive Recursive Function (Wikipedia)
Includes: Primitive Recursive Function, Lead sentenceQuote, Includes: Primitive Recursive Function, Lead sentence
In computability theory, a primitive recursive function is, roughly speaking, a function that can be computed by a computer progra
Rice-Shapiro theorem, Wikipedia
Kleene's Recursion Theorem (Wikipedia)
Wikimedia FoundationIncludes: Kleene's Recursion Theorem, Lead sentenceQuote, Includes: Kleene's Recursion Theorem, Lead sentence
In computability theory, Kleene's recursion theorems are a pair of fundamental results about the application of computable functio
Wikipedia: Smn theorem
WikipediaIncludes: S-m-n Theorem, Lead sentenceQuote, Includes: S-m-n Theorem, Lead sentence
In computability theory the S mn theorem, written also as "smn-theorem" or "s-m-n theorem" (also called the translation lemma, par
Myhill isomorphism theorem, Wikipedia
Includes: Myhill Isomorphism Theorem, Lead sentenceQuote, Includes: Myhill Isomorphism Theorem, Lead sentence
In computability theory the Myhill isomorphism theorem, named after John Myhill, provides a characterization for two numberings to
Stephen Cole Kleene (Wikipedia)
Includes: Stephen Cole Kleene, Lead paragraph [in-branch]Quote, Includes: Stephen Cole Kleene, Lead paragraph [in-branch]
recursion theory
Emil Leon Post (Wikipedia)
Includes: Emil Post, Lead paragraph [in-branch]Quote, Includes: Emil Post, Lead paragraph [in-branch]
computability theory
Wikipedia: Joseph R. Shoenfield
Includes: Joseph R. Shoenfield, LeadQuote, Includes: Joseph R. Shoenfield, Lead
Shoenfield worked on recursion theory, model theory and axiomatic set theory.
Trakhtenbrot's theorem (Wikipedia)
Includes: Trakhtenbrot's Theorem, Lead paragraphQuote, Includes: Trakhtenbrot's Theorem, Lead paragraph
In logic, finite model theory, and computability theory, Trakhtenbrot's theorem (due to Boris Trakhtenbrot) states that the problem of validity in first-order logic on the class of all finite models is undecidable.
Wikipedia: Turing machine
Includes: Turing Machine, Lead sectionQuote, Includes: Turing Machine, Lead section
A Turing machine is a mathematical model of computation describing an abstract machine that manipulates
Wikipedia: Busy beaver
Includes: Busy Beaver, Lead sectionQuote, Includes: Busy Beaver, Lead section
In theoretical computer science, the busy beaver game aims to find a terminating program of a given
Greibach's theorem, Wikipedia
Includes: Greibach's Theorem, Lead sectionQuote, Includes: Greibach's Theorem, Lead section
In theoretical computer science, in particular in formal language theory, Greibach's theorem states that certain properties
Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.