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.

${\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

${\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}}}$.

These equations can be used as rules of a term rewriting system (TRS).

The generalized function ${\displaystyle F(x,y,n){\stackrel {\mathrm {def} }{=}}F_{n}(x,y)}$leads to the rewrite rules

${\displaystyle {\begin{array}{lll}{\text{(r1)}}&F(x,y,0)&\rightarrow x+y\\{\text{(r2)}}&F(x,0,n+1)&\rightarrow x\\{\text{(r3)}}&F(x,y+1,n+1)&\rightarrow F(F(x,y,n+1),F(F(x,y,n+1),y+1,0),n)\\\end{array}}}$

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: compute ${\displaystyle F(2,2,1)\rightarrow _{*}12}$.

The reduction sequence is

${\displaystyle {\underline {F(2,2,1)}}}$

${\displaystyle \rightarrow _{r3}F(F(2,1,1),F({\underline {F(2,1,1)}},2,0),0)}$

${\displaystyle \rightarrow _{r3}F(F(2,1,1),F(F(F(2,0,1),F({\underline {F(2,0,1)}},1,0),0),2,0),0)}$

${\displaystyle \rightarrow _{r2}F(F(2,1,1),F(F(F(2,0,1),{\underline {F(2,1,0)}},0),2,0),0)}$

${\displaystyle \rightarrow _{r1}F(F(2,1,1),F(F({\underline {F(2,0,1)}},3,0),2,0),0)}$

${\displaystyle \rightarrow _{r2}F(F(2,1,1),F({\underline {F(2,3,0)}},2,0),0)}$

${\displaystyle \rightarrow _{r1}F(F(2,1,1),{\underline {F(5,2,0)}},0)}$

${\displaystyle \rightarrow _{r1}F({\underline {F(2,1,1)}},7,0)}$

${\displaystyle \rightarrow _{r3}F(F(F(2,0,1),F({\underline {F(2,0,1)}},1,0),0),7,0)}$

${\displaystyle \rightarrow _{r2}F(F(F(2,0,1),{\underline {F(2,1,0)}},0),7,0)}$

${\displaystyle \rightarrow _{r1}F(F({\underline {F(2,0,1)}},3,0),7,0)}$

${\displaystyle \rightarrow _{r2}F({\underline {F(2,3,0)}},7,0)}$

${\displaystyle \rightarrow _{r1}{\underline {F(5,7,0)}}}$

${\displaystyle \rightarrow _{r1}12}$

F₀(x, y) = x + y

F₁(x, y) = 2^y · (x + 2) − y − 2

• Rosetta Code (23 July 2024). "Sudan function".

• OEIS: A260003, A260004