primitive recursive vector-valued function
Recall that a primitive recursive function is an operation on , the set of all natural numbers ( included here). In other words, it is a mapping into the set , mimicking a computation whose outcome has only one value. However, it is possible to extend this notion, so that a computation yields an outcome with several values simultaneously (imagine a URM where the contents of the output are found in first tape cells). This is equivalent to a mapping (provided with inputs).
For this entry, , , and for specific , we set .
It is evident that primitive recursiveness in this generalized version is closed under composition: if and are primitive recursive, then so is .
In addition, it is also closed under iterated composition:
If is primitive recursive, then so is the function such that
The technique of mutual recursion is used to prove this fact.
Suppose with each , and with each . Then
From this we compute
So . This shows that the functions are defined by mutual recursion via the functions and the identity function . Since each of the is primitive recursive, so is each of the , and hence so is . ∎
Example. We give an alternative proof that the function denoting the -th Fibonacci number is primitive recursive.
Clearly, is primitive recursive. Now define such that and . By what we have just shown, is primitive recursive too. Since
for any , we see that
Therefore, the function is primitive recursive, and hence is primitive recursive also.
The example above is but a more general phenomenon: the operation of matrix multiplication is primitive recursive. To see what this means, we define:
Definition. Let be an matrix whose cells . We say that is primitive recursive if each of its cells is primitive recursive.
If and are and primitive recursive matrices, then clearly so is their product , for each of its cell is just a finite sum of products of primitive recursive functions. More over, we have the follow:
If is an primitive recursive matrix, so is its -fold power , where each cell is a function of and .
We employ the same trick given in the example. Define, for any , the function , where the right hand side is product of the matrices (considered as a matrix) and . So is primitive recursive because is. Next, define such that , and . Then is primitive recursive by proposition 1 above. But then is just . Applying to , we get , which is just the first row of , and is clearly primitive recursive. By the same token, the other rows are primitive recursive too, completing the proof. ∎
|Title||primitive recursive vector-valued function|
|Date of creation||2013-03-22 19:06:38|
|Last modified on||2013-03-22 19:06:38|
|Last modified by||CWoo (3771)|