Girish Mahajan (Editor)

Sudan function

Updated on
Edit
Like
Comment
Share on FacebookTweet on TwitterShare on LinkedInShare on Reddit

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

Definition

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

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

References

Sudan function Wikipedia
(Text) CC BY-SA