alternative characterization of primitive recursiveness
One useful feature regarding the extended notion of primitive recursiveness described in the parent entry is that it can be used to characterize the original notion of primitive recursiveness. As in the parent entry, we use the notation
In addition, let
Let be the smallest subset of such that
contains the zero function , the successor function , and the projection functions (see the definition of primitive recursive functions for more detail),
is closed under extension of coordinates: that is, if are in , so is , given by ,
is closed under iterated composition: if is in , and so is , given by (where is the identity function).
We now state the characterization.
First, observe that condition 1 is satisfied by both and . To see that , note that condition 3 is just the definition in the parent entry, and conditions 2 and 4 are discussed and proved, also in the parent entry. So we have one inclusion. To see the other inclusion , we need to verify the two closure properties:
functional composition (in ): suppose and are in , we want to show that is in too. First, form . Then by extension of coordinates. Then by functional composition (in ).
primitive recursion: suppose and are both in , we want to show that given by and is in too. First, define a function by
Then is formed by extension of coordinates via the projection functions (with ) producing the first coordinates (the coordinates of ), the function producing the st coordinate , and producing the last coordinate. Since each of the coordinate functions is in , so is .
Next, the function given by is in by iterated composition. We now verify by induction on that
, and its third coordinate is , as desired.
Suppose now that . Then
As a result, is in also.
Therefore, , and the proof is complete. ∎
Remark. According to the characterization above, one sees that primitive recursion is in a sense a special form of iterated composition. The above characterization is helpful in proving, among other things, that every URM-computable function is recursive, and that the Ackermann function is not primitive recursive.
|Title||alternative characterization of primitive recursiveness|
|Date of creation||2013-03-22 19:06:44|
|Last modified on||2013-03-22 19:06:44|
|Last modified by||CWoo (3771)|