computing the Ackermann function
Recall that the Ackermann function (the modern version) is given by the following double recursive relation:
From the equations above, we see that computing the Ackermann function involves first deciding whether the pair is such that
which dictates which one of the three equations above to use. Let us illustrate this by a simple example: and :
If , then quite a few more steps are involved:
When , computations of becomes unwieldy, mainly due to the number of steps involved, and partially due to the number of ’s and the parentheses that need to be written down.
Nevertheless, based on the computations of and above, we see an algorithm emerging for computing in general. First, notice that in each of the expression , the right parentheses all occur at the right end of the expression. Therefore, there is no ambiguity involved if the ’s and the parentheses were removed. Formalizing this notion, we have
In particular, the sequence of length is an Ackermann sequence for .
Therefore, computing is just a process of transforming the Ackermann sequence to the Ackermann sequence , for . Transforming one sequence to another sequence can be formalized as follows:
Definition. Suppose is a finite non-empty sequence of non-negative integers. A sequence is said to be immediately derivable from , written , if exactly one of the following conditions holds:
consists of one number, and ;
, and ;
, with , and ; or
, with , , and ,
where may be the empty sequence.
It is clear that conditions 2-4 correspond to the three equations defining the Ackermann function.
We also write to mean a finite chain of sequences
such that either , or , and for .
From the definition above, we can also describe the entire computational process rigorously:
start with a sequence , call the sequence derived at step ;
If is derived at step , and , then is derived at step .
For example, the computation of can be written simply as
A number of easy consequences of can now be listed:
if , then unless consists of only one number.
if , then is an Ackermann sequence for iff is.
if , where , then is an Ackermann sequence for .
if , then there is such that .
any pair is an Ackermann sequence for some .
|Title||computing the Ackermann function|
|Date of creation||2013-03-22 19:07:46|
|Last modified on||2013-03-22 19:07:46|
|Last modified by||CWoo (3771)|