Misplaced Pages

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

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

Computation

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}$

Value tables

Values of F₀

F₀(x, y) = x + y

Values of F₁

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

Values of F₂

Values of F₃

Notes and references

1. Sudan 1927.
2. Ackermann 1928.
3. Calude, Marcus & Tevy 1979.
4. Calude 1988, p. 92.
5. Calude 1988, pp. 92–95.
6. The rightmost innermost occurrences of F are underlined.

Bibliography

• Ackermann, Wilhelm (1928). "Zum Hilbertschen Aufbau der reellen Zahlen". Mathematische Annalen. 99: 118–133. doi:10.1007/BF01459088. JFM 54.0056.06. S2CID 123431274.

• Calude, Cristian; Marcus, Solomon; Tevy, Ionel (1979). "The first example of a recursive function which is not primitive recursive". Historia Mathematica. 6 (4): 380–384. doi:10.1016/0315-0860(79)90024-7.

• Calude, Cristian (1988). Theories of Computational Complexity. Amsterdam: North-Holland. ISBN 978-0-444-70356-9.

• Sudan, Gabriel (1927). "Sur le nombre transfini ω". Bulletin mathématique de la Société Roumaine des Sciences. 30: 11–30. JFM 53.0171.01. JSTOR 43769875. Jbuch 53, 171

External links

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

• OEIS: A260003, A260004

• Arithmetic
• Large integers
• Special functions
• Theory of computation