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 invented in 1927 by Gabriel Sudan, a Romanian mathematician who was a student of David Hilbert.
Definition
- <math>F _0 (x, y) = x+y,\,</math>
- <math>F _{n+1} (x, 0) = x, \ n \ge 0\,</math>
- <math>F _{n+1} (x, y+1) = F _n (F_{n+1} (x, y), F_{n+1} (x, y) + y + 1), \ n\ge 0.\,</math>
