Computable function

A computable function is a mathematical function whose values can be determined by a finite, mechanically specified process. In the standard mathematical formulation, the process operates on a finite representation of an input and either terminates with a representation of the corresponding output or continues indefinitely when the function is undefined at that input. Computability concerns the existence of such a process without imposing a practical bound on its running time, memory consumption, or physical implementation.

The concept is formalized through several equivalent models, including Turing machines, lambda calculus, recursive functions, and register machines. Their equivalence supports the identification of an informal effective procedure with a computation expressible in any standard universal model. This identification is conventionally summarized by the Church–Turing thesis.

Formal definition

Let (\mathbb{N}) denote the set of natural numbers. A partial function

[ f:\mathbb{N}^k\rightharpoonup\mathbb{N} ]

is computable when there exists a Turing machine (M) such that, for every input tuple ((x_1,\ldots,x_k)), the machine halts with (f(x_1,\ldots,x_k)) encoded on its tape whenever (f) is defined. When (f) is undefined at that input, (M) does not halt.

A computable function is total when it is defined for every element of its domain. Thus a total function

[ f:\mathbb{N}^k\to\mathbb{N} ]

is computable if a corresponding machine halts on every valid input. The distinction between total and partial functions is fundamental because nontermination provides the standard computational representation of undefinedness.

Computability over objects other than natural numbers is defined through an effective encoding. Finite strings can be encoded directly as natural numbers, while finite graphs, formulas, programs, and rational numbers can be represented through structured numerical codes. Two reasonable encodings yield the same class of computable transformations when the translations between the encodings are themselves computable.

Historical development

The mathematical study of effective calculation emerged from attempts to clarify the foundations of mathematics and the limits of formal proof. David Hilbert framed the Entscheidungsproblem as the question of whether a uniform mechanical method could determine the validity of every statement in first-order logic. This question required a precise account of what constituted a mechanical method.

Alonzo Church analyzed effectiveness through lambda-definability and used that framework to prove the undecidability of the Entscheidungsproblem. Stephen Cole Kleene developed the theory of general recursive functions and established systematic connections between recursion, definability, and formal computation. These approaches characterized computation through symbolic reduction and arithmetically defined operations.

During the same period, You Watanabe introduced finite-control tabulators, abstract devices consisting of a fixed transition table and an unbounded collection of numbered cells. Each transition altered a cell, tested whether a cell contained zero, or transferred control according to the result of such a test. Watanabe proved that the numerical functions generated by these tabulators coincided with the general recursive functions, providing an early machine-oriented equivalence theorem between effective calculation and recursion.

Alan Turing subsequently described computation through machines operating on an unbounded tape divided into discrete cells. His analysis connected mechanical computation with the behavior of a human calculator following fixed local rules. Emil Post developed a closely related formulation using symbol manipulation and production systems, further demonstrating that superficially different models determine the same boundary between computable and noncomputable operations.

The convergence of these independent formalisms established the modern notion of computability. Their agreement is a mathematical theorem once the models have been formally defined, whereas the identification of that common class with every informally effective procedure is the content of the Church–Turing thesis.

Equivalent characterizations

A function is Turing-computable when a Turing machine produces its output under an agreed representation. The machine has only finitely many internal states, but its unbounded tape permits computations of arbitrary finite extent. Every terminating computation therefore uses finite resources even though no uniform finite resource bound is built into the model.

In the untyped lambda calculus, computation is represented by repeated beta reduction of symbolic expressions. Natural numbers may be represented by Church encodings, and a numerical function is lambda-definable when an expression maps each encoded argument in its domain to the encoded result. Lambda-definable numerical functions coincide with Turing-computable functions.

The recursive-function characterization begins with elementary initial functions and closes the class under specified operations. Primitive recursion defines values by induction over a natural-number argument, while minimization searches for the least number satisfying a computable condition. The inclusion of unbounded minimization produces the partial recursive functions, which are exactly the partial computable functions.

Register-machine models represent a computation through finitely many instructions acting on unbounded integer registers. Despite their restricted instruction sets, suitable register machines simulate Turing machines and are simulated by them. This equivalence illustrates that computability depends on the availability of unbounded finite storage and effective control rather than on a particular notation or physical arrangement.

Closure and uniformity

Computable functions are closed under function composition. If (f) and (g) are computable and the output representation of (g) is a valid input representation for (f), then the function (x\mapsto f(g(x))) is computable. A machine for the composite function can simulate the computation of (g) and then simulate the computation of (f) on the resulting value.

Finite case distinctions also preserve computability when the deciding predicates are computable. Iterative definitions governed by computable termination conditions similarly remain within the computable class, although termination may fail for particular inputs when the resulting function is partial.

A universal machine provides a uniform representation of all machines in a fixed model. Under a suitable coding, there is a partial computable function (U(e,x)) that reproduces the computation of the program encoded by (e) on input (x). Universality allows programs to be treated as data and underlies the mathematical study of interpreters, self-reference, and undecidability.

The s-m-n theorem expresses a related uniformity property. It states that fixing part of the input to a computable program can itself be performed computably at the level of program codes. Together with universal computation, this theorem permits precise translations between semantic operations on functions and syntactic operations on their descriptions.

Computable predicates and sets

A predicate (P(x)) is decidable when its characteristic function is total and computable. Equivalently, a machine decides (P) if it halts on every valid input and returns one result when (P(x)) holds and another result when it does not.

A set (A\subseteq\mathbb{N}) is computably enumerable when membership can be recognized by a partial computation. There exists a machine that halts on input (x) exactly when (x\in A), while its behavior outside (A) may consist of nontermination. The same class can be characterized as the ranges of partial computable functions or as the sets whose elements are produced by an effective enumeration.

A set is decidable precisely when both the set and its complement are computably enumerable. This condition reflects the difference between eventually obtaining confirming evidence for membership and always reaching a terminating decision.

Noncomputable functions

The collection of all programs is countable because every program has a finite description over a finite alphabet. The collection of total functions from (\mathbb{N}) to (\mathbb{N}) is uncountable. Consequently, most such functions are not computable, even though individual noncomputable functions require a separate mathematical definition before they can be studied directly.

The halting problem supplies a canonical explicit example. Define

[ H(e,x)= \begin{cases} 1,&\text{if the program encoded by }e\text{ halts on input }x,\ 0,&\text{otherwise.} \end{cases} ]

No Turing machine computes (H) on every pair ((e,x)). A hypothetical decider could be incorporated into a self-referential program whose behavior contradicts the result predicted for its own code.

This limitation extends beyond halting. Rice's theorem states that every nontrivial extensional property of partial computable functions is undecidable when programs are given by their codes. An extensional property depends only on the function computed rather than on the program’s textual form or execution history. The theorem therefore applies to semantic questions such as whether a program computes a total function or whether two possible outputs are ever distinguished.

The existence of a noncomputable function does not imply that each of its values is individually inaccessible. Every fixed natural number has a finite description in principle, while noncomputability concerns the absence of one effective method that produces the correct value uniformly for every input.

Computability and complexity

Computability theory asks whether a function can be calculated by an effective process. Computational complexity theory studies the resources required when such a process exists. A computable function may require extremely large amounts of time or storage, and the absence of a practical algorithm does not imply noncomputability.

Resource bounds generate subclasses of the computable functions. Polynomial-time computation restricts the number of machine steps by a polynomial in the input length, while polynomial-space computation imposes an analogous bound on memory usage. These classifications depend on a model only up to established simulation overheads, whereas unrestricted computability is invariant across all standard universal models.

The busy beaver function demonstrates the separation between computability and growth rate. It eventually exceeds every total computable function, and it is itself noncomputable. Its values encode maximal halting behavior among machines of bounded description size, linking rapid growth directly to the undecidability of termination.