Partial 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.

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 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)$.