Computable function

A function whose values can be produced by a finite effective procedure. Its computability is independent of the particular computational model, provided the model captures effective calculation.

Turing machine: An abstract machine that computes by reading and writing symbols on an unbounded tape according to finite rules. A function is computable when a Turing machine halts with its value for every valid input.
Algorithm: A finite, precisely specified procedure for solving a class of problems. A computable function is one whose outputs an algorithm can produce on every input.
Uncomputable function: A function for which no finite effective procedure produces the correct value on every input. It marks the boundary beyond which no algorithm computes the function.
Computability theory: The mathematical study of which problems and functions can be computed by effective procedures. It classifies computable functions and studies the limits of algorithms.
Recursive function: A function defined through initial functions and operations such as composition, primitive recursion, and minimization. The recursive-function formalism characterizes the same effectively calculable functions.
Total function: A function defined for every element of its stated domain. Computable functions are usually taken to be total unless partiality is stated explicitly.
Primitive recursive function: A function generated from basic functions using composition and primitive recursion alone. These functions are computable, but form a strict subclass of total computable functions.
Gödel's incompleteness theorems: Two theorems showing that sufficiently expressive, consistent formal systems cannot prove every arithmetic truth. Their proofs use effective formalization and connect computation with limits of proof.
Lambda calculus: A formal system for expressing computation through function abstraction and application. Its evaluation rules provide another formal account of computable functions.
Natural number: A nonnegative integer used for counting and formal arithmetic. Computability theory often encodes inputs and outputs as natural numbers.

Linked from 15 pages