Wikipedia / Sudan function
Wikipedia / 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.
In 1926, David Hilbert conjectured that every computable function was primitive recursive. This was refuted by Gabriel Sudan and Wilhelm Ackermann both his students using different functions that were published in quick succession: Sudan in 1927, Ackermann in 1928.
The Sudan function is the earliest published example of a recursive function that is not primitive recursive.
Definition
The last equation can be equivalently written as
.
Computation
These equations can be used as rules of a term rewriting system (TRS).
leads to the rewrite rules
At each reduction step the rightmost innermost occurrence of F is rewritten, by application of one of the rules (r1) - (r3).
Calude (1988) gives an example.
The reduction sequence is
{|
|- | |- | |- | |- | |- | |- | |- | |- | |- | |- | |- | |- | |- | |}
Value tables
Values of F0
F0(x,y) = x+y
Values of F1
F1(x,y) = 2y·(x+2) − y − 2
Values of F2
Values of F3
Notes and references
Bibliography
External links