Computability theory
Study of computable functions and degrees of noncomputability.
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. The field has since expanded to include the study of generalized computability and definability, overlapping with proof theory and effective descriptive set theory. Basic questions include what it means for a function on the natural numbers to be computable and how noncomputable functions can be classified into a hierarchy based on their level of noncomputability.
- field
- Mathematical logic, computer science, theory of computation
- known_for
- Formalizing effective calculation, Church–Turing thesis, undecidable problems
- key_concepts
- Turing computability, computable sets, computably enumerable sets, Turing degrees, many-one reducibility
- origins
- 1930s
- founders
- Kurt Gödel, Alonzo Church, Rózsa Péter, Alan Turing, Stephen Kleene, Emil Post
Lore & Background
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. Their fundamental results established Turing computability as the correct formalization of the informal idea of effective calculation. With a definition of effective calculation came the first proofs that there are problems in mathematics that cannot be effectively decided. A set of natural numbers is computable if there is a Turing machine that, given a number n, halts with output 1 if n is in the set and halts with output 0 if not. A function is Turing computable if there is a Turing machine that, on input n, halts and returns output f(n). Other models of computation, such as μ-recursive functions, have the same computing power. Not every set is computable; the halting problem is a well-known noncomputable set. The existence of many noncomputable sets follows from the fact that there are only countably many Turing machines but uncountably many sets of natural numbers. The halting problem is an example of a computably enumerable (c.e.) set, which can be enumerated by a Turing machine.
Reader's Guide
Computability theory's significance lies in providing a rigorous mathematical foundation for the concept of effective calculation, which underpins modern computer science and mathematical logic. The Church–Turing thesis, though not a formal theorem, serves as a fundamental assumption that algorithmic computability is captured by Turing machines. This framework enabled the first proofs of undecidable problems, such as the Entscheidungsproblem, the word problem for groups, and Hilbert's tenth problem, demonstrating inherent limits of algorithmic methods. The field's development of relative computability and Turing degrees allows precise classification of noncomputable sets by their level of unsolvability. The study of computably enumerable sets and reducibility notions (such as many-one and Turing reducibility) provides tools for comparing the difficulty of mathematical problems. Computability theory also overlaps with proof theory and effective descriptive set theory, and its concepts are applied in computer science through subrecursive hierarchies, formal methods, and formal languages. The legacy of computability theory includes a deeper understanding of what can and cannot be computed, influencing both theoretical and practical aspects of computation.
Did You Know?
- The halting problem is a well-known example of a noncomputable set, but it is computably enumerable.
- The Church–Turing thesis states that any function computable by an algorithm is a computable function.
- There are only countably many Turing machines, and thus only countably many computable sets, but uncountably many sets of natural numbers.
Frequently Asked Questions
Who is Computability theory?
Computability theory, also called recursion theory, is a branch of mathematical logic and computer science that emerged in the 1930s. It was founded by figures like Gödel, Church, Turing, Kleene, and Post, who set out to pin down exactly what it means for a calculation to be effectively performable.
What are Computability theory's powers/role?
Its core task is to formalize effective calculation and classify functions on the natural numbers as either computable or noncomputable. It also builds hierarchies of noncomputability using tools like Turing degrees and many-one reducibility to rank how 'hard' an unsolvable problem truly is.
How does Computability theory's story end?
It has no single ending; the field keeps expanding into generalized computability, definability, and effective descriptive set theory. Its foundational questions—what is computable, and how do we measure what is not—remain open threads that intersect with proof theory and modern theoretical computer science.
Why is Computability theory important?
It gave mathematics a rigorous answer to what can and cannot be decided by any mechanical procedure, crystallized in the Church–Turing thesis and the discovery of undecidable problems. Without it, we would lack the formal vocabulary to discuss algorithmic limits, computable sets, and the boundaries of computation.
Who are Computability theory's founding members?
The field was shaped in the 1930s by Kurt Gödel, Alonzo Church, Rózsa Péter, Alan Turing, Stephen Kleene, and Emil Post. Each contributed a different formal model or theorem that together established the modern framework of Turing computability and the degrees of unsolvability.
More in Mathematical Logic And Computation 1-21
Spotted an error? Know more?
This is a living reference — every entry is fact-audited, and reader corrections feed straight into our audit queue. Suggest an edit · See this site's audit record