In my discrete mathematics class this week I challenged my students with an extra credit task. Write a program to compute A (4,4) and print the decimal digits of the answer. The original version of the function was developed by the German logician Wilhelm Ackermann in the 1920s. The Ackermann function is a deceptively simple recursive function with a not-so-obvious, very-high rate of growth. It is defined as follows:
|A(0,n) = n + 1||If m=0 and n is a non-negative integer|
|A(m,0) = A(m – 1, 1)||If m is a positive integer and n=0|
|A(m,n) = A(m – 1, A(m, n-1))||If m, n are positive integers
As an example, a call of A(1,1) would result in the following calculations.
|A(0, A(1, 0))||m, n are positive integers so the third line is evaluated.|
|A(0, A(0,1))||A(1,0) evaluates to A(0,1) on the second line.|
|A(0, 2)||A(0,1) evaluates to n + 1 = 2 on the first line.|
|3||A(0,2) evaluates to n + 1 = 3 on the first line.|
Not bad. All students in discrete mathematics are required as a prerequisite to have passed a Java or C++ programming course, so assigning a simple program is a reasonable request. In fact, programming this function is a ‘walk in the park.’ The program is essentially an evaluation to an integer when m = 0 and two recursive function calls when m is not 0. All that needs to be added is scenery: the syntax for a function declaration, data definitions, conditionals that implement the decisions on the function calls, and a print statement to display the answer.
I was vague about how much extra credit the assignment was worth, but I did tell them that points earned would be added to their graded homework tally—a nice way to win back some lost homework points.
Five students rose to the challenge; some standing taller than others.
Two students wrote a simple program; tried to run it for A(4,4); and gave up when nothing printed (various run-time errors occurred).
Two students realized that the answer would be a large integer, larger than a normal 64-bit integer representation would allow (which explains the various run-time errors). The students decided to use a Java BigInteger class that allows for very large integers. Doing so allowed one student to print the answer for A(4,2), a number with 19,729 digits. But the A(4,4) failed with cryptic errors. The other student divided the computation into parts that could run on multiple processors but had no answer displayed, even after the program ran all night.
One student did not write a program but analyzed the mathematics behind the recursive calls to compute A(4,4) in the form of an approximate exponential , 2^(2^(2^65536)).
A small challenge; but one that was never going to be met. No one was going to print all the digits of the answer to A(4,4). Abuse of trust? I hope not. I gave credit for the programs and more credit for the realization of the need to address the size of the answer; and even points for analyzing the mathematics instead of writing a program. Students like to be challenged (at least some students) and since there was no big prize attached to the challenge, and I gave consolation prizes, I do not think the students felt cheated (none said so anyway). I do not often use extra credit as a tool in teaching. This week told me it might be worthwhile to use it more often, at least once in a while. What do you think?