The ModulaTor logo 7KB

The ModulaTor

Oberon-2 and Modula-2 Technical Publication

Erlangen's First Independent Modula-2 Journal! Nr. 2/Mar-1991, 2nd ed. Dec-1999


A guided trip into the theory of computability

by Günter Dotzel, ModulaWare

The so-called Ackermann function was developed by Wilhelm Ackermann (1896 to 1962) in the year 1928. Ackermann worked as a high-scool teacher from 1927 to 1961. He was a student of the well-known mathematician David Hilbert in Göttingen/Germany. From 1953 Ackermann also was a honorary professor. He worked as a multi-talent in the fields of mathematical logic, decidability and set theory. Together with Hilbert he published the first modern textbook on mathematical logic [Hilb 28]. Since the topic covered by this book was logic and not computability it did not contain the definition of the function which bears his name. (That he discovered the function in the same year was by mere coincidence. I was not able to retrieve any reference to a paper where the function was first defined.) The Ackermann function is the simplest example of a well-defined and total function, which ist computable but not primitive recursive (PR). Using a twofold induction, its termination it is provable for all input arguments. At the turn of the century, one believed, that everything which is computable is also PR.

What is Primitive Recursive (PR)?

It can be shown, that all recursive algorithms can be replaced by suitable program loop constructs. Essentially there exist two different loops, the so-called For- and the While-Loop.

The For-Loop iterates x-times, whereas the bound x is to be fixed at the loop's entry. It isn't possible to replace the recursion in the Ackermann function by For-Loops. This is only possible by using While-Loops, since its bound is more flexible. (It can be shown, that everything what is computable can be programmed using While-Loops.) Hence, one actually has to compute the Ackermann function, to be able to determine its nesting level. But its important feature is that the function value grows very fast, faster than those of any function which is PR. Given any function f(x) or f(x,y) which is PR, there exists a value for the Ackermann function's first argument for which its function value is always greater than the value of f. Also its nesting level (i.e.: not the number of calls of the Ackermann function) is at least as deep as its function value.

The definition of the Ackermann function b(x,y) makes use of three cases:

1. if x=0 then the function value is b = y+1

2. if y=0 then the function value is computed recursively by b = b(x-1, 1)

3. otherwise a twofold recursion determines the function value by b = b(x-1, b(x, y-1))

The first argument x determines the complexity or kind of the function, the Ackermann function represents, whereas the second argument y is the iteration count for the function determined by the first argument.

Here is the Ackermann function programmed in Modula-2 [Wirt 88]:


    MODULE Ackermann;
    FROM Terminal IMPORT WriteInt, WriteLn;
      PROCEDURE b(x, y: INTEGER):INTEGER;
      BEGIN
        IF x=0 THEN RETURN y+1
        ELSIF y=0 THEN RETURN b(x-1, 1)
        ELSE RETURN b(x-1, b(x, y-1))
        END
      END b;
    BEGIN WriteInt(b(4,2)); WriteLn;
    END Ackermann.
The example is supposed to calculate b(4,2). This takes a long time and is rather resource consuming. I think that no computer ever constructed in the future will be able to run the program above and get the result within human's life-time. Using the program above, it is only possible to calculate b(4,2) or b(3,y) for low values of y -- on a single computer, using the recursive algorithm above.

But there exists a second possibility to calculate b. One can determine the function that b represents dependend on the first argument x. I like to show these functions for the first five values:


b(0,y) = successor (y); e.g.: b(0,0)=1, b(0,1)=2, b(0,2)=3, b(0,3)=4, ...
 
b(1,y) = y+2; e.g.: b(1,0)=2, b(1,1)=3, b(1,2)=4, b(1,3)=5, ...
 
b(2,y) = 2y+3; e.g.: b(2,0)=3, b(2,1)=5, b(2,2)=7, b(2,3)=9, ...
 
          y+3
b(3,y) = 2    -3; e.g.: b(3,0)=5, b(3,1)=13, b(3,2)=29, b(3,3)=61, ... b(3,9)=4093, 

b(3,10)=8189, b(3,11)=16381, b(3,12)=32765, b(3,13)=65533, ... 

              2
             .
            .
           .
          2
b(4,y) = 2       -3
(whereas the tower of the 2's has a height of y+3. Note that the exponent is evaluated in top-down fashion), e.g. b(4,0)=13, b(4,1)=65533,

                  19728
b(4,2) is about 10     
that's is a number which has 19728 decimal characters. Even this number b(4,1) is too large for the human imagination and can't be calculated using the recursive definition of b. Using the appropriate software tools with unlimited precision arithmetic and the replacement function for b(4,y) as shown above, one can determine b(4,2) on todays workstations in about 20 seconds and print out the result with 19728 digits.

Acknowledgements

I like to thank Dr. Helmut Sperber, who provided me with the theoretical background of the Ackermann function and the personal data of Ackermann. He also calculated b(4,2).

In a contest, Konrad Scheller was able to get the result of b(4,1) in less than two hours. He programmed his home computer in Forth, but got stack overflow for b(3,y) for (say) y>8. So he calculated the result by hand (manually) applying the original definition and simplifying from b(4,1) which is identical to b(3, b(4,0)), which is identical to b(3, 13), to b(2,b(3,12)), b(2,b(2,b(3,11))), ... b(2, ..., b(3,0)...), b(2, ..., 5)...) and got the correct value of 65533.

A follow up for this article with letters to the editor is contained in The ModulaTor, vol. 1, nr. 11 (#17).

References

[Hilb 28] David Hilbert, Wilhelm Ackermann: Grundzuege der theoretischen Logik, 1928 (in German).

[Wirt 88] Niklaus Wirth: Programming in Modula-2 (fourth edition). Springer Verlag (Berlin, Heidelberg, New York, Tokyo) 1988. Also available in German and French.


IMPRESSUM: The ModulaTor is an unrefereed journal. Technical papers are to be taken as working papers and personal rather than organizational statements. Items are printed at the discretion of the Editor based upon his judgement on the interest and relevancy to the readership. Letters, announcements, and other items of professional interest are selected on the same basis. Office of publication: The Editor of The ModulaTor is Guenter Dotzel


Home Site_index Contact Legal Buy_products OpenVMS_compiler Alpha_Oberon_System ModulaTor Bibliography Oberon[-2]_links Modula-2_links
Amazon.com [3KB] [Any browser]


Webdesign by www.otolo.com/webworx, last revised in 27-Oct-2004 (thanks Bill for pointing out that the number result for b(3,10) was wrong.)