Computability

Computable

Functions which are computable but whose computation may require the use of “until” loops (as well as “for” loops) are partial computable. They are “partial” in the sense that their domain is the subset of ${\mathbb{N}}^k$ on which the program eventually halts. If a partial computable function is defined for all inputs then it is said to be total computable. A relation $R\subset {\mathbb{N}}^k$ is decidable/computable if its characteristic function is computable. (Note that a characteristic function is everywhere defined.)

primitive recursive $\subset$ (total) computable $\subset$ partial computable

The Ackermann function $A:\mathbb{N}\times \mathbb{N}\to \mathbb{N}$ is computable and is defined for all $m,n\in \mathbb{N}\times \mathbb{N}$, but it is not primitive recursive. It was introduced in 1928 by Ackermann, working on Hilbert’s program, in order to show the existence of a “computable” function which was not captured by the concept of primitive recursive. At that time the precise notion of a computable function was unknown.