Computability theory

Computability theory studies which problems algorithms can solve and which functions formal models of computation can calculate. It distinguishes computable tasks from tasks no algorithm can perform.

Turing machine: An abstract machine that computes by manipulating symbols on a tape according to finite instructions. It provides a standard formal model for defining algorithmic computation.
Diagonalization: A proof technique that constructs an object differing from every item in a proposed enumeration at a selected position. It underlies proofs that some computable functions and decision procedures cannot exist.
Entscheidungsproblem: Hilbert's decision problem asks whether an algorithm can determine the truth or falsity of every first-order logical statement. Its negative solution helped establish the subject's central limits on algorithms.
Computational complexity theory: The study of the resources, such as time and memory, required to solve computational problems. Computability asks whether any algorithm exists; complexity asks how costly one is.
Program verification: The use of formal methods to establish that software satisfies specified properties. Undecidability results limit which program properties can be checked automatically in full generality.
Partial recursive function: A function generated from basic functions by composition, primitive recursion, and minimization; it may be undefined for some inputs. This function class gives a formal account of computations that may fail to halt.
Universal Turing machine: A Turing machine that simulates any encoded Turing machine on an encoded input. Universal simulation lets programs be treated as data in undecidability proofs.
Alonzo Church: An American mathematician and logician who developed lambda calculus and proved the Entscheidungsproblem undecidable. His 1936 work gave one formal proof that no general decision procedure exists.
Proof theory: The study of formal proofs as mathematical objects and of the structure of formal derivations. It concerns what formal systems can prove, a question related to but distinct from algorithmic solvability.
Static analysis: The automated examination of program code without executing it, often to infer possible behaviors. Its sound approximations address properties that exact general analysis cannot decide.

Linked from 28 pages