primitive recursive vector-valued function

Recall that a primitive recursive function is an operation on $\mathbb{N}$, the set of all natural numbers ($0$ included here). In other words, it is a mapping into the set $\mathbb{N}$, 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 equivalent to a mapping $\mathbb{N}^{m}\to\mathbb{N}^{n}$ (provided with $m$ inputs).

For this entry, $\mathcal{S}:=\{f:\mathbb{N}^{m}\to\mathbb{N}\mid\mbox{ any }m\geq 1\}$, $\mathcal{V}:=\{f:\mathbb{N}^{m}\to\mathbb{N}^{n}\mid\mbox{ any }m,n\geq 1\}$, and for specific $m,n\geq 1$, we set $\mathcal{V}(m,n):=\{f:\mathbb{N}^{m}\to\mathbb{N}^{n}\}$.

Definition. A function $f\in\mathcal{V}$ is primitive recursive iff each of its components is. In other words, if $f=(f_{1},\ldots,f_{n})$, where each $f_{i}:\mathbb{N}^{m}\to\mathbb{N}$, then $f$ is primitive recursive if each $f_{i}$ is (in the traditional sense).

It is evident that primitive recursiveness in this generalized version is closed under composition: if $f\in\mathcal{V}(m,n)$ and $g\in\mathcal{V}(n,p)$ are primitive recursive, then so is $g\circ f$.

In addition, it is also closed under iterated composition:

Proposition 1.

If $f\in\mathcal{V}(n,n)$ is primitive recursive, then so is the function $g\in\mathcal{V}(n+1,n)$ such that

 $g(\boldsymbol{x},0)=\boldsymbol{x}\qquad\mbox{and}\qquad g(\boldsymbol{x},n)=f% ^{n}(\boldsymbol{x}).$

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

Proof.

Suppose $f=(f_{1},\ldots,f_{n})$ with each $f_{i}\in\mathcal{V}(n,1)$, and $g=(g_{1},\ldots,g_{n})$ with each $g_{i}\in\mathcal{V}(n+1,1)$. Then

 $f^{n}(\boldsymbol{x})=(g_{1}(\boldsymbol{x},n),\ldots,g_{n}(\boldsymbol{x},n)).$

From this we compute

 $\displaystyle(g_{1}(\boldsymbol{x},n+1),\ldots,g_{n}(\boldsymbol{x},n+1))$ $\displaystyle=$ $\displaystyle f^{n+1}(\boldsymbol{x})=f(f^{n}(\boldsymbol{x}))$ $\displaystyle=$ $\displaystyle(f_{1}(g_{1}(\boldsymbol{x},n),\ldots,g_{n}(\boldsymbol{x},n)),% \ldots,f_{n}(g_{1}(\boldsymbol{x},n),\ldots,g_{n}(\boldsymbol{x},n))).$

So $g_{i}(\boldsymbol{x},n+1)=f_{i}(g_{1}(\boldsymbol{x},n),\ldots,g_{n}(% \boldsymbol{x},n))$. This shows that the functions $g_{i}$ are defined by mutual recursion via the functions $f_{i}$ and the identity function $p_{1}^{1}$. Since each of the $f_{i}$ is primitive recursive, so is each of the $g_{i}$, and hence so is $g$. ∎

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

Let

 $f(x,y)=\begin{bmatrix}x&y\end{bmatrix}\begin{bmatrix}0&1\\ 1&1\end{bmatrix}=(x,x+y).$

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

 $\begin{bmatrix}0&1\\ 1&1\end{bmatrix}^{n}=\begin{bmatrix}F(n-1)&F(n)\\ F(n)&F(n+1)\end{bmatrix}$

for any $n>1$, we see that

 $g(x,y,n)=\begin{bmatrix}x&y\end{bmatrix}\begin{bmatrix}F(n-1)&F(n)\\ F(n)&F(n+1)\end{bmatrix}=(xF(n-1)+yF(n),xF(n)+yF(n+1)).$

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 multiplication is primitive recursive. To see what this means, we define:

Definition. Let $M(\boldsymbol{x})$ be an $m\times n$ matrix whose cells $M_{ij}(\boldsymbol{x})\in\mathcal{V}(k,1)$. We say that $M(\boldsymbol{x})$ is primitive recursive if each of its cells is primitive recursive.

If $M(\boldsymbol{x})$ and $N(\boldsymbol{x})$ are $m\times n$ and $n\times p$ primitive recursive matrices, then clearly so is their product $M(\boldsymbol{x})N(\boldsymbol{x})$, 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(\boldsymbol{x})$ is an $m\times m$ primitive recursive matrix, so is its $n$-fold power $M(\boldsymbol{x})^{n}$, where each cell is a function of $\boldsymbol{x}$ and $n$.

Proof.

We employ the same trick given in the example. Define, for any $\boldsymbol{y}\in\mathbb{N}^{m}$, the function $f(\boldsymbol{x},\boldsymbol{y}):=\boldsymbol{y}M(\boldsymbol{x})$, where the right hand side is product of the matrices $\boldsymbol{y}$ (considered as a $1\times m$ matrix) and $M(\boldsymbol{x})$. So $f$ is primitive recursive because $M$ is. Next, define $g(\boldsymbol{x},\boldsymbol{y},n)$ such that $g(\boldsymbol{x},\boldsymbol{y},0)=(\boldsymbol{x},\boldsymbol{y})$, and $g(\boldsymbol{x},\boldsymbol{y},n)=f^{n}(\boldsymbol{x},\boldsymbol{y})$. Then $g$ is primitive recursive by proposition 1 above. But then $g(\boldsymbol{x},\boldsymbol{y},n)$ is just $\boldsymbol{y}M(\boldsymbol{x})^{n}$. Applying $\boldsymbol{y}=(1,0,\ldots,0)$ to $g$, we get $g(\boldsymbol{x},1,\ldots,0,n)$, which is just the first row of $M(\boldsymbol{x})^{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 PrimitiveRecursiveVectorvaluedFunction 2013-03-22 19:06:38 2013-03-22 19:06:38 CWoo (3771) CWoo (3771) 9 CWoo (3771) Definition msc 03D20