Sudan function

From Wikipedia, the free encyclopedia

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.

[edit] 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.\,

[edit] Value Tables

Values of F1(m, n)
m\n 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


Values of F2(m, n)
m\n 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 ×1010 F1(74, 76) ≈ 5.74 ×1024 F1(185, 187) F1(440, 442)

[edit] References

 This mathematical logic-related article is a stub. You can help Wikipedia by expanding it.