You are here
Home ›properties of Ackermann function
Primary tabs
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.
Mathematics Subject Classification
03D75 Abstract and axiomatic computability and recursion theory- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)
- Other useful stuff
Recent Activity
new question: pure subgroups by lvoyster
new correction: Typo in M\"obius function? by Aleph Zero
new collection: analytic number theory by Aleph Zero
May 20
new question: Taylor's Series Query! by unlord
new question: Laplace transform by J
new question: Residue Calculus by J
May 19
new Education: Project: PlanetMath Outlines Series by unlord
May 17
new image: sinx_approx.png by jeremyboden
new image: approximation_to_sinx by jeremyboden
new image: approximation_to_sinx by jeremyboden


