# 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 \text{any}m\ge 1\}$, $\mathcal{V}:=\{f:{\mathbb{N}}^{m}\to {\mathbb{N}}^{n}\mid \text{any}m,n\ge 1\}$, and for specific $m,n\ge 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},\mathrm{\dots},{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\mathrm{\in}\mathrm{V}\mathit{}\mathrm{(}n\mathrm{,}n\mathrm{)}$ is primitive recursive, then so is the function $g\mathrm{\in}\mathrm{V}\mathit{}\mathrm{(}n\mathrm{+}\mathrm{1}\mathrm{,}n\mathrm{)}$ such that

$$g(\bm{x},0)=\bm{x}\mathit{\hspace{1em}\hspace{1em}}\text{\mathit{a}\mathit{n}\mathit{d}}\mathit{\hspace{1em}\hspace{1em}}g(\bm{x},n)={f}^{n}(\bm{x}).$$ |

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

###### Proof.

Suppose $f=({f}_{1},\mathrm{\dots},{f}_{n})$ with each ${f}_{i}\in \mathcal{V}(n,1)$, and $g=({g}_{1},\mathrm{\dots},{g}_{n})$ with each ${g}_{i}\in \mathcal{V}(n+1,1)$. Then

$${f}^{n}(\bm{x})=({g}_{1}(\bm{x},n),\mathrm{\dots},{g}_{n}(\bm{x},n)).$$ |

From this we compute

$({g}_{1}(\bm{x},n+1),\mathrm{\dots},{g}_{n}(\bm{x},n+1))$ | ||||

$=$ | ${f}^{n+1}(\bm{x})=f({f}^{n}(\bm{x}))$ | |||

$=$ | $({f}_{1}({g}_{1}(\bm{x},n),\mathrm{\dots},{g}_{n}(\bm{x},n)),\mathrm{\dots},{f}_{n}({g}_{1}(\bm{x},n),\mathrm{\dots},{g}_{n}(\bm{x},n))).$ |

So ${g}_{i}(\bm{x},n+1)={f}_{i}({g}_{1}(\bm{x},n),\mathrm{\dots},{g}_{n}(\bm{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)=\left[\begin{array}{cc}\hfill x\hfill & \hfill y\hfill \end{array}\right]\left[\begin{array}{cc}\hfill 0\hfill & \hfill 1\hfill \\ \hfill 1\hfill & \hfill 1\hfill \end{array}\right]=(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

$${\left[\begin{array}{cc}\hfill 0\hfill & \hfill 1\hfill \\ \hfill 1\hfill & \hfill 1\hfill \end{array}\right]}^{n}=\left[\begin{array}{cc}\hfill F(n-1)\hfill & \hfill F(n)\hfill \\ \hfill F(n)\hfill & \hfill F(n+1)\hfill \end{array}\right]$$ |

for any $n>1$, we see that

$$g(x,y,n)=\left[\begin{array}{cc}\hfill x\hfill & \hfill y\hfill \end{array}\right]\left[\begin{array}{cc}\hfill F(n-1)\hfill & \hfill F(n)\hfill \\ \hfill F(n)\hfill & \hfill F(n+1)\hfill \end{array}\right]=(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(\bm{x})$ be an $m\times n$ matrix whose cells ${M}_{ij}(\bm{x})\in \mathcal{V}(k,1)$. We say that $M(\bm{x})$ is *primitive recursive* if each of its cells is primitive recursive.

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

###### Proof.

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