properties of Ackermann function
In this entry, we derive some basic properties of the Ackermann function , defined by double recursion, as follows:
These properties will be useful in proving that is not primitive recursive.
- 1.
is total ().
- 2.
.
- 3.
.
- 4.
.
- 5.
.
- 6.
.
- 7.
.
- 8.
- 9.
For any , for some not depending on .
Most of the proofs are done by induction.
Proof.
- 1.
Induct on . First, is well-defined, so for all . Next, suppose that for a given , for all . We want to show that for all . To do this, induct on . First, , since is well-defined. Next, assume that . Then is well-defined. so as well.
- 2.
Induct on . First, . Next, assume . Then .
- 3.
Induct on . First, . Next, assume . Then .
- 4.
Induct on . First, . Next, assume , where . Then .
- 5.
Induct on . First, . Next, assume that . Then .
- 6.
Induct on . First, . Next, assume that . Then .
- 7.
Induct on . First, . Next, assume that . There are two cases: . Then . Otherwise, , so that .
- 8.
.
- 9.
Let . Then . The proof is completed by setting .
∎
With respect to the recursive property of , we see that is recursive, since, by Church’s Thesis, can be effectively computed (in fact, a program can be easily written to compute ). We also have the following:
Proposition 1.
Define by . Then is primitive recursive for each .
Proof.
, so is primitive recursive. Now, assume is primitive recursive, then , and , so that is defined by primitive recursion via the constant function , and , which is primitive recursive by the induction hypothesis. Therefore is primitive recursive also.∎
The most important fact about concerning recursiveness is that is not primitive recursive. Due to the length of its proof, it is demonstrated in this entry (http://planetmath.org/AckermannFunctionIsNotPrimitiveRecursive).