In the

theory of computation In theoretical computer science and mathematics, the theory of computation is the branch that deals with what problems can be solved on a model of computation, using an algorithm, how efficiently they can be solved or to what degree (e.g., app ...

, the Sudan function is an example of a

function Function or functionality may refer to: Computing * Function key, a type of key on computer keyboards * Function model, a structured representation of processes in a system * Function object or functor or functionoid, a concept of object-orie ...

that is

recursive Recursion occurs when the definition of a concept or process depends on a simpler or previous version of itself. Recursion is used in a variety of disciplines ranging from linguistics to logic. The most common application of recursion is in m ...

, but not

primitive recursive In computability theory, a primitive recursive function is, roughly speaking, a function that can be computed by a computer program whose loops are all "for" loops (that is, an upper bound of the number of iterations of every loop is fixed befor ...

. This is also true of the better-known

Ackermann function In computability theory, the Ackermann function, named after Wilhelm Ackermann, is one of the simplest and earliest-discovered examples of a total function, total computable function that is not Primitive recursive function, primitive recursive. ...

. In 1926,

David Hilbert David Hilbert (; ; 23 January 1862 – 14 February 1943) was a German mathematician and philosopher of mathematics and one of the most influential mathematicians of his time. Hilbert discovered and developed a broad range of fundamental idea ...

conjectured that every computable function was primitive recursive. This was refuted by Gabriel Sudan and

Wilhelm Ackermann Wilhelm Friedrich Ackermann (; ; 29 March 1896 – 24 December 1962) was a German mathematician and logician best known for his work in mathematical logic and the Ackermann function, an important example in the theory of computation. Biograph ...

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

\begin
F_0 (x, y) & = x+y \\
F_ (x, 0) & = x & \text n \ge 0 \\
F_ (x, y+1) & = F_n (F_ (x, y), F_ (x, y) + y + 1) & \text n\ge 0 \\
\end

The last equation can be equivalently written as :

\begin
F_ (x, y+1) & = F_n(F_ (x, y), F_0(F_(x, y), y + 1)) \\
\end

Computation

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

F(x,y,n) \stackrel F_n(x,y)

leads to the rewrite rules :

\begin
\text & F(x, y, 0) & \rightarrow x+y \\
\text & F(x, 0, n+1) & \rightarrow x \\
\text & F(x, y+1, n+1) & \rightarrow F(F(x, y, n+1), F(F(x, y, n+1), y + 1,0), n) \\
\end

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

F(2,2,1) \rightarrow_ 12

. The reduction sequence isThe rightmost innermost occurrences of F are underlined. :

Value tables

Values of F₀

''F''₀(''x'', ''y'') = x + y

Values of F₁

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

Values of F₂

Values of F₃

Notes and references

Bibliography

* * * *

External links

* * OEIS: A260003, A260004 {{DEFAULTSORT:Sudan Function Arithmetic Large integers Special functions Theory of computation