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
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