For all $(n_1, \cdots, n_k) \in \mathbb{N}^k$ let's define $<n_1, \dots, n_k>:=p_1^{n_1+1} \dotsc p_k^{n_k+1}$, whereby $(p_1, p_2, p_3, \cdots)=(2,3,5,7,\cdots)$ are the prime numbers.
For every function $f: \mathbb{N}^k \times \mathbb{N} \rightarrow \mathbb{N}$ we define $\hat{f}: \mathbb{N}^k \times \mathbb{N} \rightarrow \mathbb{N}$ as follows:
$\hat{f}(\vec{x}, y)=<f(\vec{x}, 0), \cdots, f(\vec{x}, y-1)>$,
i.e. $f(\vec{x}, 0) = <>=1$ and $f(\vec{x},1) = <f(\vec{x}, 0)> = 2^{f(\vec{x}, 0) + 1}$.
Now we want to proof that f is primitive recursive if and only if $\hat{f}$ is primitive recursive. (Moreover: If f is total, then f is computable if and only if $\hat{f}$ is computable.)

In order to clarify the definition of primitve recursive functions:
We define a set $\mathcal{P}$ of operations on $\mathbb{N}$, the so-called "primitive recursive functions": For every $k \geq 0$ the constant function from $\mathbb{N}^k$ to $\mathbb{N}$ with value 0 is primitive recursive.
The function $n \mapsto n+1$ is primitive recursive.
For every $n \geq 1$ and every k so that $1 \leq k \leq n$ the projection function $\Pi_k^n: \mathbb{N}^n \rightarrow \mathbb{N}, \pi_k^n(x_1, ..., x_n) = x_k$ is primitive recursive.
If g: $\mathbb{N}^k \rightarrow \mathbb{N}$ and $f_1, \cdots, f_k: \mathbb{N}^n \rightarrow \mathbb{N}$ all are primitive recursive, then also the function $g(f_1, \cdots, f_k): \mathbb{N}^n \rightarrow \mathbb{N}$, defined by:
$\forall \vec{x}=(x_1, \cdots, x_n): g(f_1, \cdots f_k)(\vec{x})):=g(f_1(\vec{x}), \cdots, f_k(\vec{x}))$.
For all $k \geq 0$, all primitive recursive funtions h: $\mathbb{N}^k \rightarrow \mathbb{N}$ and all primitive recursive functions g, the function defined by
$\forall \vec{x} \in \mathbb{N}: f(\vec{x}, 0) = h(\vec{x}), \quad \forall y \in \mathbb{N} \forall \vec{x} \in \mathbb{N}^k: f(\vec{x}, y+1) = g(f(\vec{x}, y), \vec{x}, y)$ is primitive recursive. This f is called $PR(g,h)$.
This are all primitive recursive funtions.

I'd appreciate any idea on how to proof the statements mentioned above.

  • 3
    $\begingroup$ The way to learn about primitive recursive functions to start with simple ones and work your way up. Rather complex ones, like what you're asking, will become easy for you before long. Here is a decent introduction to work through, which I found on google search. Seems to have a few typos. www.andrew.cmu.edu/user/kk3n/complearn/chapter2.pdf $\endgroup$ – realdonaldtrump Dec 30 '18 at 19:20
  • $\begingroup$ Thanks for the link. I've skimmed it (and am going to read it properly, of course), but from what I've seen, most of it I already know, but still can't solve the problem. $\endgroup$ – Studentu Dec 31 '18 at 7:08
  • 1
    $\begingroup$ Simplify the problem and work up. 1.Can you design a primitive recursive function $f$ in one variable such that $f(y) = p_y$? 2. If so, can you design $g$ such that $g(y) = \langle \underbrace{0,0,\ldots,0}_{y~\rm times}\rangle$, or in other words $g(y) = p_1 \cdots p_y$? 3. If so, can you do variations such as $h(y)= \langle 1,2,\ldots,y\rangle$ and so on? If you can, you are very close to solving your original problem. $\endgroup$ – realdonaldtrump Dec 31 '18 at 14:35
  • $\begingroup$ @realdonaldtrump Well, I can manage 1.), because this is given in the chapter you posted the link to. (Though I'm not 100% sure why the function given there is primitive recursive, because I don't know why the function h(x) given there is primitive recursive, although I know that factorial and subtraction are primitive recursive.) For 2.) and 3.) I'd need help, please. $\endgroup$ – Studentu Jan 2 at 14:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.