In the theory of computation

Theory of computation

In theoretical computer science, the theory of computation is the branch that deals with whether and how efficiently problems can be solved on a model of computation, using an algorithm...

, the Sudan function is an example of a function

Function (mathematics)

In mathematics, a function associates one quantity, the argument of the function, also known as the input, with another quantity, the value of the function, also known as the output. A function assigns exactly one output to each input. The argument and the value may be real numbers, but they can...

 that is recursive

Recursive function

Recursive function may refer to:*Recursion , a procedure or subroutine, implemented in a programming language, whose implementation references itself*A total computable function, a function which is defined for all possible inputs...

, but not primitive recursive

Primitive recursive function

The primitive recursive functions are defined using primitive recursion and composition as central operations and are a strict subset of the total µ-recursive functions...

. This is also true of the better-known Ackermann function

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

. The Sudan function was the first function having this property to be published.

It was discovered in 1927 by Gabriel Sudan

Gabriel Sudan

Gabriel Sudan was a Romanian mathematician, known for the Sudan function , an important example in the theory of computation, similar to the Ackermann function .Gabriel Sudan received his Ph.D...

, a Romania

Romania

Romania is a country located at the crossroads of Central and Southeastern Europe, on the Lower Danube, within and outside the Carpathian arch, bordering on the Black Sea...

n mathematician

Mathematician

A mathematician is a person whose primary area of study is the field of mathematics. Mathematicians are concerned with quantity, structure, space, and change....

 who was a student of David Hilbert

David Hilbert

David Hilbert was a German mathematician. He is recognized as one of the most influential and universal mathematicians of the 19th and early 20th centuries. Hilbert discovered and developed a broad range of fundamental ideas in many areas, including invariant theory and the axiomatization of...

. It was published in.

Definition

Value Tables

Values of F₁(x, y)

y\x	0	1	2	3	4	5
0	0	1	2	3	4	5
1	1	3	5	7	9	11
2	4	8	12	16	20	24
3	11	19	27	35	43	51
4	26	42	58	74	90	106
5	57	89	121	153	185	217
6	120	184	248	312	376	440

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

Values of F₂(x, y)

y\x	0	1	2	3	4	5
0	0	1	2	3	4	5
1	1	8	27	74	185	440
2	19	F1(8, 10) = 10228	F1(27, 29) ≈ 1.55	F1(74, 76) ≈ 5.74	F1(185, 187) ≈ 3.67	F1(440, 442) ≈ 5.02