In the theory of computation, the Sudan function is an example of a function that is recursive, but not primitive recursive. This is also true of the better-known Ackermann function. In 1926, David Hilbert conjectured that every computable function was primitive recursive. This was refuted by Gabriel Sudan and Wilhelm Ackermann — both his students — using different functions that were published in quick succession: Sudan in 1927, Ackermann in 1928. The Sudan function is the earliest published example of a recursive function that is not primitive recursive.

Definition

The last equation can be equivalently written as

Computation

These equations can be used as rules of a term rewriting system (TRS). The generalized function leads to the rewrite rules At each reduction step the rightmost innermost occurrence of F is rewritten, by application of one of the rules (r1) - (r3). Calude (1988) gives an example: compute. The reduction sequence is

Value tables

Values of F0

F0(x, y) = x + y

Values of F1

F1(x, y) = 2y · (x + 2) − y − 2

Values of F2

Values of F3

Notes and references