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 (and published[1]) in 1927 by Gabriel Sudan, a Romanian mathematician who was a student of David Hilbert.

Definition

${\displaystyle F_{0}(x,y)=x+y,\,}$
${\displaystyle F_{n+1}(x,0)=x,\ n\geq 0\,}$
${\displaystyle F_{n+1}(x,y+1)=F_{n}(F_{n+1}(x,y),F_{n+1}(x,y)+y+1),\ n\geq 0.\,}$

Value Tables

Values of F0(xy)
y\x 0 1 2 3 4 5
0 0 1 2 3 4 5
1 1 2 3 4 5 6
2 2 3 4 5 6 7
3 3 4 5 6 7 8
4 4 5 6 7 8 9
5 5 6 7 8 9 10
6 6 7 8 9 10 11

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

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 ×1010 F1(74, 76) ≈ 5.74 ×1024 F1(185, 187) ≈ 3.67 ×1058 F1(440, 442) ≈ 5.02 ×10135

References

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