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