Sudan Function

 

Definition

 

A function of two positive integers x and y, defined by the recurrence relation

 

F0(x,y) = x + y,

 

Fn+1(x,0) = x, for n ≥ 0,

 

Fn+1(x,y+1) = Fn( Fn+1(x,y), Fn+1(x,y)+y+1), for n ≥ 0.

 

Sudan function F0(x,y)

Tables of Values of F0(x,y)

    y

 

 x

0 1 2 3 4 5 6 7 8
0 0 1 2 3 4 5 6 7 8
1 1 2 3 4 5 6 7 8 9
2 2 3 4 5 6 7 8 9 10
3 3 4 5 6 7 8 9 10 11
4 4 5 6 7 8 9 10 11 12
5 5 6 7 8 9 10 11 12 13
6 6 7 8 9 10 11 12 13 14
 

Properties of F0(x,y)

 

F0(x,0) = x

 

 

F0(0,y) = y

 

 

F0(x,x) = 2x,

 

e.g F0(4,4) = 2.4 = 8 ü

 

First-order Sudan function F1(x,y)

Tables of Values of F1(x,y)

 

    y

 x

0 1 2 3 4 5 6 7 8 9 10
0 0 1 4 11 26 57 120 247 502 1013 2036
1 1 3 8 19 42 89 184 375 758 1525 3060
2 2 5 12 27 58 121 248 503 1014 2037 4084
3 3 7 16 35 74 153 312 631 1270 2549 5108
4 4 9 20 43 90 185 376 759 1526 3061 6132
5 5 11 24 51 106 217 440 887 1782 3573 7156
6 6 13 28 59 122 249 504 1015 2038 4085 8180
7 7 15 32 67 138 281 568 1143 2294 4597 9204
8 8 17 36 75 154 313 632 1271 2550 5109 10228
9 9 19 40 83 170 345 696 1399 2806 5621 11252
10 10 21 44 91 186 377 760 1527 3062 6133 12276
 

Properties of F1(x,y)

F1(x,0) = x,

 

F1(0,y) = (x + 2)(2x - 1),

 

F1(x,y) = F1(0,y) + x.2y,

 

e.g. F1(3,4) = F1(0,4) + 3.24 = 26 + 48 = 74 ü

 

 

F1(x,y) = (x + 2).2y - (y + 2), (explicit solution)

 

e.g. F1(8,8) = (x+2).2y - (y+2) = 10.2 - 10 = 2560 - 10 = 2550 ü

 

 

Graphical Representation of F1(x,y)

Second-order Sudan function F2(x,y)

Tables of Values of F2(x,y)

 
      y

  x

0 1 2
0 0 F1(0,1) = 1 F1(1,3) = 19 ≈ 101
1 1 F1(1,2) = 8 F1(8,10) = 10228 ≈ 104
2 2 F1(2,3) = 27 F1(27,29) ≈ 1010
3 3 F1(3,4) = 74 F1(74,76) ≈ 1025
4 4 F1(4,5) = 185 F1(185,187) ≈ 1058
5 5 F1(5,6) = 440 F1(440,442) ≈ 10136
 

 

 

Properties of F2(x,y)

 

F2(x,0) = x,

 

F2(x,y+1) = F1( F2(x,y), F2(x,y)+y+1).

 

 

History of Fn(x,y)

 

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 but 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.

Applications of Fn(x,y)

Higher order Sudan functions with n ≥ 2 can be used to test the ability of computers to handle recursion efficiently.

A A A