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
F 0 ( x , y ) = x + y F n + 1 ( x , 0 ) = x if n ≥ 0 F n + 1 ( x , y + 1 ) = F n ( F n + 1 ( x , y ) , F n + 1 ( x , y ) + y + 1 ) if n ≥ 0 {\displaystyle {\begin{array}{lll}F_{0}(x,y)&=x+y\\F_{n+1}(x,0)&=x&{\text{if }}n\geq 0\\F_{n+1}(x,y+1)&=F_{n}(F_{n+1}(x,y),F_{n+1}(x,y)+y+1)&{\text{if }}n\geq 0\\\end{array}}}
The last equation can be equivalently written as
F n + 1 ( x , y + 1 ) = F n ( F n + 1 ( x , y ) , F 0 ( F n + 1 ( x , y ) , y + 1 ) ) {\displaystyle {\begin{array}{lll}F_{n+1}(x,y+1)&=F_{n}(F_{n+1}(x,y),F_{0}(F_{n+1}(x,y),y+1))\\\end{array}}} .
Computation These equations can be used as rules of a term rewriting system (TRS). The generalized function F ( x , y , n ) = d e f F n ( x , y ) {\displaystyle F(x,y,n){\stackrel {\mathrm {def} }{=}}F_{n}(x,y)} leads to the rewrite rules
… excerpt ends here. Continue reading the full article.
