Ackermann function is not primitive recursive
In this entry, we show that the Ackermann function , given by
The key to showing that is not primitive recursive, is to find a properties shared by all primitive recursive functions, but not by . One such property is in showing that in some way “grows” faster than any primitive recursive function. This is formalized by the notion of “majorization”, which is explained here (http://planetmath.org/SuperexponentiationIsNotElementary).
Let be the set of all functions majorized by . Then .
We break this up into three parts: show all initial functions are in , show is closed under functional composition, and show is closed under primitive recursion. The proof is completed by realizing that is the smallest set satisfying the three conditions.
In the proofs below, denotes some tuple of non-negative integers for some , and . Likewise for and .
We show that the zero function, the successor function, and the projection functions are in .
, so .
, so .
, so .
Next, suppose are -ary, and is -ary, and that each , and are in . This means that , and . Let
Then , showing that .
Finally, suppose is -ary and is -ary, and that . This means that and . We want to show that , defined by primitive recursion via functions and , is in .
We first prove the following claim:
Pick , and induct on . First, . Next, suppose . Then , where . By the induction hypothesis, together with the fact that , we see that . Thus, , proving the claim.
To finish the proof, let . Then, by the claim, , showing that .
Since is by definition the smallest set containing the initial functions, and closed under composition and primitive recursion, . ∎
As a corollary, we have
The Ackermann function is not primitive recursive.
Otherwise, , which is impossible. ∎
|Title||Ackermann function is not primitive recursive|
|Date of creation||2013-03-22 19:07:29|
|Last modified on||2013-03-22 19:07:29|
|Last modified by||CWoo (3771)|