Partial Computable Function

A partial computable function (also called a partial recursive function) is a function from natural numbers to natural numbers that can be computed by an effective procedure — a Turing machine, a lambda calculus term, or a register machine program — with the critical feature that the procedure may not halt on all inputs. Where a total computable function is defined for every input in its domain, a partial computable function is defined only on a subset of its domain, and the procedure computing it diverges (runs forever) on inputs outside that subset.

This partiality is not a defect. It is the defining feature of general computation. The set of partial computable functions is strictly larger than the set of total computable functions, and the difference between them is precisely the set of functions whose totality cannot be effectively determined — a fact closely related to the halting problem. The partial computable functions form the standard model of computability in computability theory, and the Church-Turing thesis is most naturally stated in terms of them: a function is effectively computable if and only if it is partial computable.

The partial computable functions are enumerable: there exists an effective enumeration \( \varphi_0, \varphi_1, \varphi_2, \ldots \) such that every partial computable function appears at some index, and the universal function \( U(e, x) = \varphi_e(x) \) is itself partial computable. This enumeration is the foundation of Kleene's recursion theorem, the s-m-n theorem, and all diagonalization arguments in computability theory.