ART

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(x, y)
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(x, y)
y\x 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
0 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
1 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29
2 4 8 12 16 20 24 28 32 36 40 44 48 52 56 60
3 11 19 27 35 43 51 59 67 75 83 91 99 107 115 123
4 26 42 58 74 90 106 122 138 154 170 186 202 218 234 250
5 57 89 121 153 185 217 249 281 313 345 377 409 441 473 505
6 120 184 248 312 376 440 504 568 632 696 760 824 888 952 1016
7 247 375 503 631 759 887 1015 1143 1271 1399 1527 1655 1783 1911 2039
8 502 758 1014 1270 1526 1782 2038 2294 2550 2806 3062 3318 3574 3830 4086
9 1013 1525 2037 2549 3061 3573 4085 4597 5109 5621 6133 6645 7157 7669 8181
10 2036 3060 4084 5108 6132 7156 8180 9204 10228 11252 12276 13300 14324 15348 16372
11 4083 6131 8179 10227 12275 14323 16371 18419 20467 22515 24563 26611 28659 30707 32755
12 8178 12274 16370 20466 24562 28658 32754 36850 40946 45042 49138 53234 57330 61426 65522
13 16369 24561 32753 40945 49137 57329 65521 73713 81905 90097 98289 106481 114673 122865 131057
14 32752 49136 65520 81904 98288 114672 131056 147440 163824 180208 196592 212976 229360 245744 262128

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

Values of F2(x, y)
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

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 doi:10.1016/0315-0860(79)90024-7

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

External links

OEIS: A260003, A260004

Undergraduate Texts in Mathematics

Graduate Texts in Mathematics

Graduate Studies in Mathematics

Mathematics Encyclopedia

World

Index

Hellenica World - Scientific Library

Retrieved from "http://en.wikipedia.org/"
All text is available under the terms of the GNU Free Documentation License