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. The Sudan function was the first function having this property to be published.

It was discovered in 1927 by Gabriel Sudan, a Romanian mathematician who was a student of David Hilbert.

Definition

:$$F _0 (x, y) = x+y,,

:$$F _{n+1} (x, 0) = x, n ge 0,

:$$F _{n+1} (x, y+1) = F _n (F_{n+1} (x, y), F_{n+1} (x, y) + y + 1), nge 0.,

Value Tables

References

*Cristian Calude, Solomon Marcus, Ionel Tevy, "The first example of a recursive function which is not primitive recursive", Historia Mathematica 6 (1979), no. 4, 380–384 doi|10.1016/0315-0860(79)90024-7