Proof that this is a Primitive Recursive function

Question

Consider the following function:
$$varphi(m) = begin{cases} 1 & m = 1 vee bigg( m= 2^n3^k wedge varphi(k)= 1 bigg)\ 0 & o.w.end{cases}$$
So $varphi$ evaluates whether an integer is of the form $2^{n_1}3^{2^{n_2}3^{(...)}}$
Now, I know how to get primitive recursion with just arity one, using composition, how to get to definition by cases, using the characteristic function and how to check whether a number is of the form $2^n3^k$ or not (see this, for example). My problem is with the other condition, of $varphi(k) = 1$.
I'm using the following definition for primitive recurion, from the book Logic and Complexity, by Richard Lassaigne:
$$ begin{cases} f(x_1,...,x_n,0) = g(x_1,...,x_n) \ f(x_1,...,x_n,S(y)) = h(x_1,...,x_n,y,f(x_1,...,x_n,y))end{cases}$$
So the value of $varphi(m)$ depends, not on the previous value of $m$, but on one of its prime factors.
I would think it's still a Primitve Recursive function, but haven't been able to prove it formaly.
Is it still a Primitive Recursive function?
If so, how can I prove it?

Hanul Jeon · Answer

The key issue is that we refer the value of $varphi(k)$ for some $k<n$, to define $varphi(n)$. It is apparently like that our primitive recursion does not allow to refer $varphi(k)$ when defining $varphi(n)$, save for when $k$ is the predecessor of $n$.
We may dodge the problem by defining $langle varphi(0),cdots,varphi(n)rangle$ simultaneously.
Let $ell:mathbb{N}^{<omega}tomathbb{N}$ be the canonical primitive recursive function that codes the finite sequence of natural numbers into a single natural number. In addition, assume that $p:mathbb{Ntimes N}to mathbb{N}$ be the projection, such that $p(k,ell(a_0,cdots,a_m))=a_k$. (If $k>m$, set $p(k,ell(a_0,cdots,a_m))=0$.)
Furthermore, let $mathsf{app}(l,a)$ be the function which appends $a$ into the list of natural numbers $l$; that is, $mathsf{app}(ell(a_0,cdots,a_m),a)=ell(a_0,cdots,a_m,a)$. We also define the length function $mathsf{len}$, which gives the length of $ell(a_0,cdots,a_m)$.
Now consider the following functions: define $h$ as follows:
$$h(l,m)=begin{cases}
mathsf{app}(l,1) & text{if there is $k<mathsf{len}(l)$ s.t. }p(k,l)=1 text{ and } exists n<m: m=2^n 3^k,\
mathsf{app}(l,0) & text{otherwise.}
end{cases}$$
Now define $psi$ by the following primitive recursion: $psi(0)=ell(1)$ and $psi(m+1)=h(psi(m),m)$. Then $varphi(m)=p(m,psi(m))$ is the desired function.

FiMePr · Answer

Hint : If $m = 2^n 3^k$, then $k < m$.

Proof that this is a Primitive Recursive function

2 Answers

Add your own answers!

Ask a Question