Ackermann function

The Ackermann function is a 1926 found by Wilhelm Ackermann, extremely fast growing mathematical function that will help in theoretical computer science boundaries of computer and computational models can be identified. Today there are a number of functions, which are called Ackermann function. These all have a similar education law as the original Ackermann function and also have a similar growth behavior.

  • 4.1 proof
  • 5.1 Benchmark for recursive calls
  • 5.2 Running time estimates with the inverse function

Genesis

1926 David Hilbert conjectured that every computable function is primitive recursive. Simplified, this means that can be composed of a few very simple rules every computable by a computer function and that the length of the calculation can be estimated in advance. This is true for nearly all occurring in practice functions.

Also in 1926 Ackermann constructed a function that refutes this assumption, and published it 1928. Him, this function is now called the Ackermann function in honor. It can be evaluated by a computer in a finite time, but is not primitive recursive.

Rózsa Péter 1955 constructed a simplified version that has the same properties. This feature, sometimes called Ackermann- Péter function, is used primarily today.

Idea

We consider the sequence. Here, for each follower, the operation of the previous sequence is used to link times, ie is straight, the variable occurs twice and so on. The idea behind the Ackermann function is to be interpreted this result as a function.

Ackermann function, recorded as is therefore a function that satisfies the following equations:

From the fourth row of function values ​​can no longer be formulated with conventional operators; you need advanced notations, such as the Hyper- operator.

Definition and variants

The Ackermann function is usually defined recursively, ie it makes for some initial values ​​explicit information and provides guidance ( the recursion ), how to get more function values ​​from the already computed.

Definition of Ackermann

Ackermann himself defined function in a rather roundabout way, but was shortly thereafter the following equivalent definition.

This is another function that is not further described Ackermann. It provides the starting values ​​:

  • If you want to calculate, we can use the first line of the definition and receives directly.
  • If you want to calculate, we can apply the second line and get:.
  • When neither the second nor the third argument is 0, using the third line of the definition. For example,. Substituting from the previous example, we obtain. Now again one can apply the third row, and then twice a second. Put it all together:

When one speaks of the growth of the Ackermann function, we think often the function.

Definition of Péter

Rózsa Péter 1955 defined a simpler version of the Ackermann function, which has only two parameters and also does not require the auxiliary function:

Again, we think in the context of growth studies often the function when one speaks of the Ackermann function.

From this definition is not immediately apparent that the operation for all non- negative integer and is defined, as is in part also increased. But you can see recursively that, firstly for is well-defined. The other is provided that is well-defined and well-defined by using the last two Rekursionsvorschriften iteratively.

Note, however, that there is with a reduction of no upper bound for the growth of the following function calls.

Modified Ackermann function

In the complexity analysis slightly modified versions of the Ackermann function are frequently used but have the same asymptotic runtime behavior. One of these variants, which allows an interpretation as " generalized exponential function " can be specified as follows:

As the defined sequence of functions can be used to define the function now modified Ackermann by

Sets.

The functions can now be interpreted as a natural continuation of addition, multiplication and exponentiation. As represented, for example, times the sum of the number -fold multiplication of the number, etc. It is

Importance in theoretical computer science

As already mentioned, Ackermann invented this function as an example of a function that is not primitive recursive, but predictable.

In search of the limits of computers you come very quickly to the notion of computable functions. These are all the functions for their evaluation can specify an algorithm, so all the functions that can calculate a computer ( a Turing machine in particular ). This definition provides a very fast before a problem if you want to decide on a specific function, whether it is predictable. One can find an algorithm that computes the function, so it is obviously predictable. Otherwise, it is uncertain whether the function is not really predictable or whether indeed there is an algorithm, but it has not found him.

For this reason, searching for alternative definitions, with which one can produce such evidence easier. A first approach for this was the primitive recursive functions. These are functions that can be composed by a few rules from very simple functions.

Some conjectured that all computable functions are primitive recursive, with the primitive recursive functions, ie a tool to solve the above described problem was found. However, this hope destroyed the Ackermann function, from which one can prove that it is predictable, but not primitive recursive. (See subsequent proof. )

If one introduces to the class of primitive recursive functions, a further construction rule, the so-called μ - recursion, one, one obtains a larger class also computable functions that contains the Ackermann function. It is believed that this class of μ - recursive functions of the class of intuitively computable functions corresponding to ( Church'sche thesis ).

Evidence

The proof that the Ackermann function is computable but not primitive recursive, uses, essentially, that the Ackermann function grows faster than any primitive recursive function.

Sketch of proof to the assertion that the Ackermann function is not primitive recursive:

  • First you defined for each primitive recursive function, a function This function specifies the maximum that can be reached when the sum of the arguments does not exceed.
  • Then you show by structural induction on the inductive structure of the primitive recursive functions, that there is a natural number to each primitive recursive function so that applies to all. Clearly, this shows that the Ackermann function grows faster than any primitive recursive function.
  • This can be proved then, as follows, that the Ackermann function is not primitive recursive: Suppose that is primitive recursive, then. After the preface there is a but, so that applies to all. If, here we obtain the contradiction:

Applications

For the Ackermann function, there are very few applications. The two most important are the benchmarks for recursive calls in programming languages ​​and run- time estimates of the weighted union and path compression in the union-find structure.

Benchmark for recursive calls

With the introduction of new programming languages, compilers and computers you want to investigate their performance. For this purpose, inter alia, by benchmarking determined by special programs properties are checked.

In this context, the Ackermann function is often used as a benchmark for verification of recursive procedure calls, since a program to calculate the Ackermann function essentially consists only of such procedure calls. In the definition of Péter yes is only calculated directly. The difficulty in the calculation of the function values ​​are therefore not only their size, but the deep nesting of function calls that are easy to a stack overflow (English StackOverflow ) results, ie to the fact that the system runs out of memory. Therefore, the Ackermann function is a simple and safe method to provoke a stack overflow, for example, to test whether this error case is handled and if so, how this is done. The Ackermann function has the advantage that it is immune to compiler optimizations and static source code analysis the (possible) stack overflow practically can not detect.

This idea goes back to Yngve Sundblad, the 1971, the function used to compare various programming languages. To calculate calls are made.

Sundblad tested, inter alia, the size can be selected so that the computer is still able to calculate this number. At the time he reached. For comparison: With Java 1.4.2, with the default memory settings, you can reach nowadays.

Over the calculation many identical calls are repeatedly calculated. An intelligent compiler can exploit this by caching the results in order to perform such calls only need to. This was already 1971 Views feasible to. A significant time advantage is also obtained if one calculates directly, instead it recursively to expand. The direct calculation of requires linear time. The calculation of requires quadratic time, because it leads to (ie, for a constant; see Landau symbols) of nested calls for different. The calculation of eventually requires a time proportional to ().

Runtime estimates with the inverse function

Since the function grows very fast, its inverse function grows very slowly. It is less practical for every conceivable input size than 5, because the feature value is greater than the number of atoms in the universe as the calculating further downwards. In the practical analysis algorithms it may thus be considered to be constant.

This inverse function appears in the runtime analysis of certain algorithms, for example, when union-find problem and in Chazelles algorithm for minimum spanning trees. In this and other contexts, the original Ackermann function is often easily redefined by omitting additive constants or other modifications to a function with a similar asymptotic behavior. These modified functions are not equal to the Ackermann function, but by the standards of runtime analysis they can be considered as equivalent.

Implementation

The recursive implementation of the Ackermann function (here in pseudo-code ) directly corresponds to the definition:

Function ACK ( n, m)       if n = 0           return m 1       else if m = 0           return ack ( n - 1, 1)       else           return ack ( n - 1, ACK ( n, m - 1)) Something more efficient is the following, partially iterative implementation:

Function ACK ( n, m)       while n ≠ 0           if m = 0               m: = 1           else               m: = ACK ( n, m - 1 )           n: = n - 1       return m 1 Even more efficient implementations use arrays for caching already calculated values ​​, see also Dynamic Programming.

In Haskell, a functional programming language, the implementation reflects directly contradicts the definition:

Ack 0 m = m 1 ack s ack 0 = ( n-1) 1 ack s ack = m ( n-1) (ack n (m -1)) In Prolog, the implementation looks like this:

Ackermann (0, X, Y ): - X > = 0, Y is X 1!   ackermann (X, 0, Z): - X > 0, X1 is X - 1, ackermann (X1, 1, Z).   ackermann (X, Y, Z): - X > 0, Y > 0, X1 is X-1, Y1 is Y - 1, ackermann (X, Y1, W), ackermann (X1, W, Z). table of values

The following table shows some of the function values ​​for small values ​​of and. The not fully calculated values ​​are too large to represent them in decimal.

¹ a number with decimal places 19729

Despite the unimaginably large numbers, which appear already in this table, recursive procedures have been defined, which provide even faster growing values ​​, such as Graham's number.

Closer Look

Based on the table of values ​​can be a scheme of calculating the function values ​​derived, which is easier to understand than the formal recursive definition. It is easy to see that the values ​​of the first row are simply a list of all natural numbers. The respective entries can be calculated with the formula. All following lines contain simple instructions to look into this line a value. In the case of the line, this statement simplifies to seek the value in the row, but this simplification is somewhat more difficult to derive - for example:

A ( 1, 2 ) = a (0, a (1,1) )          = A (0, a (0, a (1,0 )))          = A (0, a ( 0, 2) )          = A ( 0, 3 )          = 4 We now consider a more complex case, namely, the first function value which is so large that it can not practically be written in decimal.

A ( 4, 3 ) = a (3, a ( 4, 2 ) )          = A (3, a ( 3, A (4, 1 )))          = A (3, a ( 3, a ( 3, A (4, 0 ))))          = A (3, a ( 3, a ( 3, a ( 3, 1 ))))          = A (3, a ( 3, a ( 3, A (2, a (3, 0) ))))          = A (3, a ( 3, a ( 3, A (2, a (2, 1) ))))          = A (3, a ( 3, a ( 3, A (2, a (1, a (2, 0)) ))))          = A (3, a ( 3, a ( 3, A (2, a (1, a (1, 1 ))) )))          = A (3, a ( 3, a ( 3, A (2, a (1, a (0, a (1, 0 ))) ))))          = A (3, a ( 3, a ( 3, A (2, a (1, a (0, a (0, 1 )))) )))          = A (3, a ( 3, a ( 3, A (2, a (1, a (0, 2 ))) )))          = A (3, a ( 3, a ( 3, A (2, a ( 1, 3) ))))          = A (3, a ( 3, a ( 3, A (2, a (0, a (1, 2 ))) )))          = A (3, a ( 3, a ( 3, A (2, a (0, a (0, a (1, 1 )))) )))          = A (3, a ( 3, a ( 3, A (2, a (0, a (0, a (0, a (1, 0 )))) ))))          = A (3, a ( 3, a ( 3, A (2, a (0, a (0, a (0, a (0, 1 )))) ))))          = A (3, a ( 3, a ( 3, A (2, a (0, a (0, a (0, 2 ))) )))          = A (3, a ( 3, a ( 3, A (2, a (0, a (0, 3) ))))          = A (3, a ( 3, a ( 3, A (2, a (0, 4) ))))          = A (3, a ( 3, a ( 3, a ( 2, 5 ))))          = ... This is for some time the simplest case of such an expansion, and it is apparent from the table, why function values ​​are calculated as this rarely directly. It is also interesting to note how many steps are necessary in order to simplify very simple looking Ackermann expressions. Each line in the previous example is a single application of one of the three parts of the definition of the Ackermann function.

... = A (3, a ( 3, a ( 3, 13 )))          = ...          = A (3, a ( 3, 65533 ) ) If we skip at this point several logical steps, we could evaluate to 13 and then try to evaluate - which is 65533 But already the next function call returns with a number that far exceeds the estimated number of atoms in the universe. . This number is finally used in the calculation, which would eventually written out to an expression of the form, but can not be written by our means.

Another interesting aspect of the Ackermann function is that the only calculation that actually shows up next to the recursive calls, the calculation of is that simply increased by 1.

27720
de