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].
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(x, y) is equal to F1(0, y) + 2y x.
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 ×1010 | F1(74, 76) ≈ 5.74 ×1024 | F1(185, 187) ≈ 3.67 ×1058 | F1(440, 442) ≈ 5.02 ×10135 |