Search: in
Sudan function
Sudan function in Encyclopedia Encyclopedia
  Tutorials     Encyclopedia     Videos     Books     Software     DVDs  
       





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

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.\,

Value Tables

Values of F1(xy)
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(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 F1(74, 76) 5.74 F1(185, 187) 3.67 F1(440, 442) 5.02

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

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






Source: Wikipedia | The above article is available under the GNU FDL. | Edit this article



Search for Sudan function in Tutorials
Search for Sudan function in Encyclopedia
Search for Sudan function in Videos
Search for Sudan function in Books
Search for Sudan function in Software
Search for Sudan function in DVDs
Search for Sudan function in Store




Advertisement




Sudan function in Encyclopedia
Sudan_function top Sudan_function

Home - Add TutorGig to Your Site - Disclaimer

©2011-2013 TutorGig.info All Rights Reserved. Privacy Statement