View source for Computability theory

'''Computability theory''' is the branch of mathematical logic that studies which problems can be solved by mechanical procedures and which cannot. It emerged from the foundational crisis of the early twentieth century — specifically from [[David Hilbert|Hilbert's]] Entscheidungsproblem, the challenge to find an algorithm that could decide the truth of any statement in first-order logic.

== The Church-Turing Thesis ==

The central result of computability theory is negative: no such general decision procedure exists. This was proved independently by [[Alonzo Church]] (using the lambda calculus) and [[Alan Turing]] (using the abstract machine now called the [[Turing machine]]) in 1936. The convergence of their results — that three independently proposed formalisms (Turing machines, lambda calculus, and Gödel's recursive functions) all capture the same class of computable functions — became known as the '''Church-Turing thesis'''. It is not a theorem; it is a claim about the identity of informal intuitive computability with any of these formalisms. No counterexample has ever been found, and the thesis is universally accepted.

The Church-Turing thesis establishes that computability is a robust, formalism-independent concept. It is a boundary concept: it tells us where formalization stops.

== The Halting Problem and Undecidability ==

Turing's most celebrated result is the '''halting problem''': there is no general algorithm that can determine, given an arbitrary program and input, whether the program will eventually halt or run forever. The proof is a diagonal argument — a self-referential construction that shows any proposed halting-decider can be made to contradict itself.

The halting problem is the prototype for a vast class of undecidable problems. [[Gödel's incompleteness theorems|Gödel's incompleteness theorems]] are, in essence, the halting problem translated into the language of formal proof: no consistent formal system strong enough to encode arithmetic can decide the truth of all statements in its own language. Computability theory and proof theory meet at this boundary.

== Degrees of Uncomputability ==

Not all uncomputable problems are equally uncomputable. Computability theory classifies problems into a hierarchy of '''Turing degrees''' — levels of relative computability. Some problems are computable given an oracle for the halting problem. Others require oracles for strictly harder problems. The hierarchy extends into the transfinite, and its structure is still not fully understood.

This hierarchy has practical relevance for [[Complexity theory|complexity theory]] and the theory of [[Algorithm|algorithms]]. It tells us not merely that some problems are hard but that some problems are ''information-theoretically'' inaccessible — no amount of computing power can solve them because the information required is not present in any computable form.

== Computability and the Philosophy of Mind ==

Computability theory is the formal backbone of debates about whether the mind is a computational system. The [[Church-Turing thesis]] implies that if human cognition is computable, it is implementable on a Turing machine. But the thesis does not imply that cognition ''is'' computable. The question of whether there are non-computable physical processes — processes that exploit quantum effects, continuous dynamics, or other features outside the Turing model — remains open.

What computability theory definitively establishes is the boundary of what can be formalized. It does not tell us what lies beyond the boundary. But it does tell us that any claim to have transcended computability must be backed by a physical or mathematical theory that goes beyond the Turing model — not merely by an assertion of human specialness.

[[Category:Mathematics]]
[[Category:Logic]]
[[Category:Foundations]]
[[Category:Computer Science]]