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., ...

, 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 (adjective: ''recursive'') occurs when a thing is defined in terms of itself or of its type. Recursion is used in a variety of disciplines ranging from linguistics to logic. The most common application of recursion is in mathemati ...

, 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 can be determined ...

. 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 computable function that is not primitive recursive. All primitive recursive functions are total ...

. The Sudan function was the first function having this property to be published. It was discovered (and published ) in 1927 by Gabriel Sudan, a

Romania Romania ( ; ro, România ) is a country located at the crossroads of Central, Eastern, and Southeastern Europe. It borders Bulgaria to the south, Ukraine to the north, Hungary to the west, Serbia to the southwest, Moldova to the east, a ...

mathematician A mathematician is someone who uses an extensive knowledge of mathematics in their work, typically to solve mathematical problems. Mathematicians are concerned with numbers, data, quantity, mathematical structure, structure, space, Mathematica ...

who was a student of David Hilbert.

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

Value tables

In general, ''F''₁(''x'', ''y'') is equal to ''F''₁(0, ''y'') + 2^''y'' ''x''.

Notes and references

Bibliography

* * *

External links

* OEIS: A260003, A260004 Arithmetic Large integers Special functions Theory of computation {{mathlogic-stub