Search: in Tutorials Encyclopedia Videos Books Software DVDs Sudan function Encyclopedia
 Tutorials Encyclopedia Videos Books Software DVDs

## 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. It was published in[1].

## 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), \ n\ge 0.\,

## Value Tables

Values of F1(xy)
y\x 0 1 2 3 4 5
0 0 1 2 3 4 5
1 1 3 5 7 9 11
2 4 8 12 16 20 24
3 11 19 27 35 43 51
4 26 42 58 74 90 106
5 57 89 121 153 185 217
6 120 184 248 312 376 440

In general, F1(xy) is equal to F1(0, y) + 2y x.

Values of F2(xy)
y\x 0 1 2 3 4 5
0 0 1 2 3 4 5
1 1 8 27 74 185 440
2 19 F1(8, 10) = 10228 F1(27, 29) 1.55 F1(74, 76) 5.74 F1(185, 187) 3.67 F1(440, 442) 5.02

## 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

1. Bull. Math. Soc. Roumaine Sci. 30 (1927), 11 - 30; Jbuch 53, 171

Source: Wikipedia | The above article is available under the GNU FDL. | Edit this article

 Search for Sudan function in Tutorials Search for Sudan function in Encyclopedia Search for Sudan function in Videos Search for Sudan function in Books Search for Sudan function in Software Search for Sudan function in DVDs Search for Sudan function in Store