Computable function

A partial function is computable when a program returns its value on every input in its domain and runs forever on inputs outside its domain.

A universal partial computable function simulates the program with index $e$ on input $\mathbf{x}$, reproducing both its output and its divergence. Decode the finite program and repeatedly apply its transition rule. This gives a partial computable function of the code and inputs. There can be no total computable evaluator whose rows are precisely all total computable functions, because $n\mapsto U(n,n)+1$ would be a missing diagonal row.

For every partial computable function $f(\mathbf{x})$, there are total primitive recursive functions $C,U$ such thatHere $C$ is zero exactly on codes of valid halting computation histories for the chosen program and input, and $U$ extracts the final output. Coding finite configurations and finite histories makes checking every local step a bounded primitive recursive operation. If a computation halts, some history code passes and every passing code has the same output; if it does not halt, none passes. This is the usual normal-form version with the program index fixed; a universal predicate can also retain that index as an input.

For a partial function $g(\mathbf{x},y)$, unbounded minimization definesas the least $y$ at which $g$ is zero, provided the preceding required computations are defined. If no such $y$ is found, $f(\mathbf{x})$ is undefined. Closing the primitive recursive functions under this operation gives the partial recursive functions.

A total computable function is a computable function whose domain is the entire input space.

A total computable function is a computable function whose domain contains every allowed input.

For a theory of arithmetic $T$ and a program index $e$, the function ${\phi }_e$ is provably total in $T$ when $T$ proves its canonical totality sentenceIf $T$ is recursively axiomatized, the indices of its provably total functions form a computably enumerable set.

For a program code $e$, input $x$, and time bound $t$, the truncated computation simulates program $e$ on $x$ for at most $t$ steps and reports either its output or that no halt occurred within the bound. This is a total computable function of $(e,x,t)$.

One convention for the Ackermann function on nonnegative integers isIts two-argument recursion defines a computable function; fixing the convention matters when defining an inverse Ackermann function.

For the displayed Ackermann function convention, one possible inverse-growth scale is $\alpha (n)=\min \{m\ge 1:A(m,m)\ge n\}$ for positive integers $n$. It gives $\alpha (n)=1$ through $3$, $2$ from $4$ through $7$, and $3$ from $8$ through $61$. Several inverse Ackermann function conventions occur in algorithm analysis; changing convention can shift these small values without changing the very slow growth relevant to the disjoint-set data structure. This inverse-growth definition does not invert a two-variable function as an ordinary one-variable inverse function.