In computability theory, the Ackermann function, named after Wilhelm Ackermann, is one of the simplest[1] and earliest-discovered examples of a total computable function that is not primitive recursive.
One common version is the two-argument Ackermann–Péter function developed by Rózsa Péter and Raphael Robinson.
[3] In the late 1920s, the mathematicians Gabriel Sudan and Wilhelm Ackermann, students of David Hilbert, were studying the foundations of computation.
, it reproduces the basic operations of addition, multiplication, and exponentiation as
[2][6] Rózsa Péter[7] and Raphael Robinson[8] later developed a two-variable version of the Ackermann function that became preferred by almost all authors.
Compared to most other versions, Buck's function has no unessential offsets:
Of the various two-argument versions, the one developed by Péter and Robinson (called "the" Ackermann function by most authors) is defined for nonnegative integers
or, written in Knuth's up-arrow notation (extended to integer indices
Iteration is the process of composing a function with itself a certain number of times.
The recursive definition of the Ackermann function can naturally be transposed to a term rewriting system (TRS).
The definition of the 2-ary Ackermann function leads to the obvious reduction rules [16][17]
space.The definition of the iterated 1-ary Ackermann functions leads to different reduction rules
Remarks As Sundblad (1971) — or Porto & Matos (1980) — showed explicitly, the Ackermann function can be expressed in terms of the hyperoperation sequence:
or, after removal of the constant 2 from the parameter list, in terms of Buck's function
,[10] a variant of Ackermann function by itself, can be computed with the following reduction rules:
To compute the Ackermann function it suffices to add three reduction rules
These rules take care of the base case A(0,n), the alignment (n+3) and the fudge (-3).
Computing the Ackermann function can be restated in terms of an infinite table.
If there is no number to its left, simply look at the column headed "1" in the previous row.
Here is a small upper-left portion of the table: The numbers here which are only expressed with recursive exponentiation or Knuth arrows are very large and would take up too much space to notate in plain decimal digits.
This number is constructed with a technique similar to applying the Ackermann function to itself recursively.
Sometimes Ackermann's original function or other variations are used in these settings, but they all grow at similarly high rates.
In particular, some modified functions simplify the expression by eliminating the −3 and similar terms.
A two-parameter variation of the inverse Ackermann function can be defined as follows, where
This function arises in more precise analyses of the algorithms mentioned above, and gives a more refined time bound.
[20] The Ackermann function appears in the time complexity of some algorithms,[21] such as vector addition systems[22] and Petri net reachability, thus showing they are computationally infeasible for large instances.
[23] The inverse of the Ackermann function appears in some time complexity results.
For instance, the disjoint-set data structure takes amortized time per operation proportional to the inverse Ackermann function,[24] and cannot be made faster within the cell-probe model of computational complexity.
[25] Certain problems in discrete geometry related to Davenport–Schinzel sequences have complexity bounds in which the inverse Ackermann function
The first published use of Ackermann's function in this way was in 1970 by Dragoș Vaida[27] and, almost simultaneously, in 1971, by Yngve Sundblad.