Table of Values
Computing the Ackermann function can be restated in terms of an infinite table. We place the natural numbers along the top row. To determine a number in the table, take the number immediately to the left, then look up the required number in the previous row, at the position given by the number just taken. 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:
| m\n | 0 | 1 | 2 | 3 | 4 | n |
|---|---|---|---|---|---|---|
| 0 | 1 | 2 | 3 | 4 | 5 | |
| 1 | 2 | 3 | 4 | 5 | 6 | |
| 2 | 3 | 5 | 7 | 9 | 11 | |
| 3 | 5 | 13 | 29 | 61 | 125 | |
| 4 | 13 = |
65533 = |
265536 − 3 = |
= |
= |
The numbers listed here in a recursive reference are very large and cannot be easily notated in some other form.
Despite the large values occurring in this early section of the table, some even larger numbers have been defined, such as Graham's number, which cannot be written with any small number of Knuth arrows. This number is constructed with a technique similar to applying the Ackermann function to itself recursively.
This is a repeat of the above table, but with the values replaced by the relevant expression from the function definition to show the pattern clearly:
| m\n | 0 | 1 | 2 | 3 | 4 | n |
|---|---|---|---|---|---|---|
| 0 | 0+1 | 1+1 | 2+1 | 3+1 | 4+1 | |
| 1 | A(0,1) | A(0,A(1,0)) | A(0,A(1,1)) | A(0,A(1,2)) | A(0,A(1,3)) | |
| 2 | A(1,1) | A(1,A(2,0)) | A(1,A(2,1)) | A(1,A(2,2)) | A(1,A(2,3)) | |
| 3 | A(2,1) | A(2,A(3,0)) | A(2,A(3,1)) | A(2,A(3,2)) | A(2,A(3,3)) | |
| 4 | A(3,1) | A(3,A(4,0)) | A(3,A(4,1)) | A(3,A(4,2)) | A(3,A(4,3)) | |
| 5 | A(4,1) | A(4,A(5,0)) | A(4,A(5,1)) | A(4,A(5,2)) | A(4,A(5,3)) |
A(4, A(5, n-1)) |
| 6 | A(5,1) | A(5,A(6,0)) | A(5,A(6,1)) | A(5,A(6,2)) | A(5,A(6,3)) |
A(5, A(6, n-1)) |
Read more about this topic: Ackermann Function
Famous quotes containing the words table of, table and/or values:
“Remember thee?
Ay, thou poor ghost, whiles memory holds a seat
In this distracted globe. Remember thee?
Yea, from the table of my memory
I’ll wipe away all trivial fond records,
All saws of books, all forms, all pressures past
That youth and observation copied there,
And thy commandment all alone shall live
Within the book and volume of my brain,”
—William Shakespeare (1564–1616)
“Will you greet your doom
As final; set him loaves and wine; knowing
The game is finished when he plays his ace,
And overturn the table and go into the next room?”
—Philip Larkin (1922–1986)
“Writing ought either to be the manufacture of stories for which there is a market demand—a business as safe and commendable as making soap or breakfast foods—or it should be an art, which is always a search for something for which there is no market demand, something new and untried, where the values are intrinsic and have nothing to do with standardized values.”
—Willa Cather (1876–1947)