Sudan function

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,^[1] Ackermann in 1928.^[2]

The Sudan function is the earliest published example of a recursive function that is not primitive recursive.^[3]