primitive recursive vector-valued function

Recall that a primitive recursive functionMathworldPlanetmath is an operationMathworldPlanetmath on , the set of all natural numbersMathworldPlanetmath (0 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 n tape cells). This is equivalentMathworldPlanetmathPlanetmathPlanetmathPlanetmath to a mapping mn (provided with m inputs).

For this entry, 𝒮:={f:m any m1}, 𝒱:={f:mn any m,n1}, and for specific m,n1, we set 𝒱(m,n):={f:mn}.

Definition. A functionMathworldPlanetmath f𝒱 is primitive recursive iff each of its componentsPlanetmathPlanetmathPlanetmath is. In other words, if f=(f1,,fn), where each fi:m, then f is primitive recursive if each fi is (in the traditional sense).

It is evident that primitive recursiveness in this generalized version is closed under compositionMathworldPlanetmath: if f𝒱(m,n) and g𝒱(n,p) are primitive recursive, then so is gf.

In additionPlanetmathPlanetmath, it is also closed under iterated composition:

Proposition 1.

If fV(n,n) is primitive recursive, then so is the function gV(n+1,n) such that

g(𝒙,0)=𝒙  𝑎𝑛𝑑  g(𝒙,n)=fn(𝒙).

The technique of mutual recursion is used to prove this fact.


Suppose f=(f1,,fn) with each fi𝒱(n,1), and g=(g1,,gn) with each gi𝒱(n+1,1). Then


From this we compute

= fn+1(𝒙)=f(fn(𝒙))
= (f1(g1(𝒙,n),,gn(𝒙,n)),,fn(g1(𝒙,n),,gn(𝒙,n))).

So gi(𝒙,n+1)=fi(g1(𝒙,n),,gn(𝒙,n)). This shows that the functions gi are defined by mutual recursion via the functions fi and the identity functionMathworldPlanetmath p11. Since each of the fi is primitive recursive, so is each of the gi, and hence so is g. ∎

Example. We give an alternative proof that the function F(n) denoting the n-th Fibonacci numberDlmfMathworldPlanetmath is primitive recursive.



Clearly, f is primitive recursive. Now define g(x,y,n) such that g(x,y,0)=(x,y) and g(x,y,n)=fn(x,y). By what we have just shown, g is primitive recursive too. Since


for any n>1, we see that


Therefore, the function h(x,y,n)=xF(n)+yF(n+1) is primitive recursive, and hence F(n)=h(1,0,n) is primitive recursive also.

The example above is but a more general phenomenon: the operation of matrix multiplicationMathworldPlanetmath is primitive recursive. To see what this means, we define:

Definition. Let M(𝒙) be an m×n matrix whose cells Mij(𝒙)𝒱(k,1). We say that M(𝒙) is primitive recursive if each of its cells is primitive recursive.

If M(𝒙) and N(𝒙) are m×n and n×p primitive recursive matrices, then clearly so is their product M(𝒙)N(𝒙), for each of its cell is just a finite sum of products of primitive recursive functions. More over, we have the follow:

Proposition 2.

If M(𝐱) is an m×m primitive recursive matrix, so is its n-fold power M(𝐱)n, where each cell is a function of 𝐱 and n.


We employ the same trick given in the example. Define, for any 𝒚m, the function f(𝒙,𝒚):=𝒚M(𝒙), where the right hand side is product of the matrices 𝒚 (considered as a 1×m matrix) and M(𝒙). So f is primitive recursive because M is. Next, define g(𝒙,𝒚,n) such that g(𝒙,𝒚,0)=(𝒙,𝒚), and g(𝒙,𝒚,n)=fn(𝒙,𝒚). Then g is primitive recursive by propositionPlanetmathPlanetmath 1 above. But then g(𝒙,𝒚,n) is just 𝒚M(𝒙)n. Applying 𝒚=(1,0,,0) to g, we get g(𝒙,1,,0,n), which is just the first row of M(𝒙)n, 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
Canonical name PrimitiveRecursiveVectorvaluedFunction
Date of creation 2013-03-22 19:06:38
Last modified on 2013-03-22 19:06:38
Owner CWoo (3771)
Last modified by CWoo (3771)
Numerical id 9
Author CWoo (3771)
Entry type Definition
Classification msc 03D20