GeezerVison is showing planetmath.org — primitive recursive vector-valued function

primitive recursive vector-valued function

Recall that a primitive recursive function is an operation on $ℕ$ , the set of all natural numbers ( $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 equivalent to a mapping $ℕ^{m} \to ℕ^{n}$ (provided with $m$ inputs).

For this entry, $𝒮 := {f : ℕ^{m} \to ℕ ∣ any m \geq 1}$ , $𝒱 := {f : ℕ^{m} \to ℕ^{n} ∣ any m, n \geq 1}$ , and for specific $m, n \geq 1$ , we set $𝒱 (m, n) := {f : ℕ^{m} \to ℕ^{n}}$ .

Definition. A function $f \in 𝒱$ is primitive recursive iff each of its components is. In other words, if $f = (f_{1}, \dots, f_{n})$ , where each $f_{i} : ℕ^{m} \to ℕ$ , 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 𝒱 (m, n)$ and $g \in 𝒱 (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 V (n, n)$ is primitive recursive, then so is the function $g \in V (n + 1, n)$ such that

g (𝒙, 0) = 𝒙 𝑎𝑛𝑑 g (𝒙, n) = f^{n} (𝒙) .

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

Proof.

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

f^{n} (𝒙) = (g_{1} (𝒙, n), \dots, g_{n} (𝒙, n)) .

From this we compute

			$(g_{1} (𝒙, n + 1), \dots, g_{n} (𝒙, n + 1))$
		$=$	$f^{n + 1} (𝒙) = f (f^{n} (𝒙))$
		$=$	$(f_{1} (g_{1} (𝒙, n), \dots, g_{n} (𝒙, n)), \dots, f_{n} (g_{1} (𝒙, n), \dots, g_{n} (𝒙, n))) .$

So $g_{i} (𝒙, n + 1) = f_{i} (g_{1} (𝒙, n), \dots, g_{n} (𝒙, 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{matrix} x & y \end{matrix}] [\begin{matrix} 0 & 1 \\ 1 & 1 \end{matrix}] = (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{matrix} 0 & 1 \\ 1 & 1 \end{matrix}]}^{n} = [\begin{matrix} F (n - 1) & F (n) \\ F (n) & F (n + 1) \end{matrix}]

for any $n > 1$ , we see that

g (x, y, n) = [\begin{matrix} x & y \end{matrix}] [\begin{matrix} F (n - 1) & F (n) \\ F (n) & F (n + 1) \end{matrix}] = (x F (n - 1) + y F (n), x F (n) + y F (n + 1)) .

Therefore, the function $h (x, y, n) = x F (n) + y F (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 (𝒙)$ be an $m \times n$ matrix whose cells $M_{i j} (𝒙) \in 𝒱 (k, 1)$ . We say that $M (𝒙)$ is primitive recursive if each of its cells is primitive recursive.

If $M (𝒙)$ and $N (𝒙)$ are $m \times n$ and $n \times 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 \times m$ primitive recursive matrix, so is its $n$ -fold power $M {(𝐱)}^{n}$ , where each cell is a function of $𝐱$ and $n$ .

Proof.

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