Computability Theory

Computability theory studies which problems can in principle be solved by an algorithm and classifies the unsolvable ones by their degree of difficulty.

Definition

Computability theory, also called recursion theory, is the branch of mathematical logic that makes precise the notion of an effectively calculable function, studies the sets and functions that algorithms can and cannot compute, and measures the relative difficulty of unsolvable problems.

Scope

This area covers formal models of computation and the Church-Turing thesis, computable and computably enumerable sets, undecidable problems such as the halting problem, the reducibilities and Turing degrees that measure relative unsolvability, and the arithmetical hierarchy that stratifies definability by quantifier complexity.

Sub-topics

• computable functions and the church turing thesis
• recursively enumerable sets and turing degrees
• the arithmetical hierarchy
• the halting problem and undecidability

Core questions

• What does it mean for a function or set to be computable?
• Which natural problems are algorithmically undecidable?
• How can the difficulty of unsolvable problems be compared and ranked?
• How does logical complexity correspond to levels of computability?

Key theories

Church-Turing thesis

The intuitive notion of effective calculability coincides with Turing machine computability, equivalently with the recursive functions and the lambda-definable functions, fixing a robust mathematical definition of algorithm.

Unsolvability of the halting problem

No algorithm can decide for every program and input whether the program halts, giving the first and prototypical example of an undecidable problem.

Turing degrees

Turing reducibility ranks sets by relative computability, and the induced degrees form a rich partial order whose structure, including the existence of intermediate degrees, is a central object of study.

Clinical relevance

Computability theory delimits the absolute boundary of algorithmic solvability, underpinning theoretical computer science and providing the undecidability results, such as the unsolvability of the halting and word problems, that recur across mathematics and inform the theory of computational complexity.

History

Computability theory arose in the 1930s when Church, Turing, Kleene, and Post independently formalized the notion of an effective procedure through the lambda calculus, Turing machines, recursive functions, and combinatory systems, all proved equivalent. Post and Kleene developed the theory of degrees and the arithmetical hierarchy, and the priority method introduced in the 1950s drove the deep structural study of the computably enumerable degrees.

Key figures

• Alan Turing
• Alonzo Church
• Stephen Cole Kleene
• Emil Post

Seminal works

• soare1987
• rogers1987
• cutland1980

Frequently asked questions

Is computability theory the same as complexity theory?

No. Computability theory asks whether a problem can be solved by any algorithm at all, ignoring resources, whereas complexity theory asks how much time or memory a solvable problem requires. Computability draws the line between solvable and unsolvable; complexity grades the solvable side.

Why is the Church-Turing thesis not a theorem?

It equates an informal notion, effective calculability, with a precise mathematical one, so it cannot be proved formally. Its acceptance rests on the convergence of many independent formalizations to the same class of functions, which is strong evidence rather than a proof.