0
$\begingroup$

I have to show that given $f:\mathbb{N}\rightarrow\mathbb{N}$ the function that returns the number of times $6$ appears in the input (for example $f(436546)=2$) is primitive recursive. The exercise says to assume that the functions $rem(m,n)$ and $div(m,n)$, which returns the remainder and the quotient, are recursive primitive (rp from now on).

What I tried so far:

  1. Trying to build a recursive primitive schema: $$f(0)=0$$ $$f(n+1)=\phi(n,f(n))$$ where $\phi$ returns how many 6 are there in the input. The problem is that if $n=23599$ then to find the number of $6$ you have to divide and get the remainder $3$ times. In general you will have to do this remainder and division algorithm $l$-times where $l$ is the length of the input. So the recursive primitive schema won't work, I guess, because $f(n)$ does not tell you anything.

  2. Trying to prove that $proj_i:\mathbb{N}\rightarrow\mathbb{N}$ is recursive primitive. Where for example $proj_3(2345)=3$. Now if this is proved to be true $f$ whould be recursive primitive because it's composition of rp functions:$$f(n)=\sum_{i=1}^{n} (10^i<n) \times eq(proj_i(n),6)$$ If this is correct, the only thing left to prove is that $proj$ is a pr function. Maybe like this $proj_i(n)=rem(div(n,10^{(i-1)}),10)$.

  3. I know from other answers in this topic that if we can derive a simple enough algorithm then the function would be pr. In this i guess we can use this strategy, the problem is that we didn't cover it in the lectures, so i guess i can't use it. The algorithm would be very simple though, an iteration, using division and reminder.

$\endgroup$
2
  • $\begingroup$ Write down the algorithm for counting digits and show that it is a composition of primitive recursive functions? $\endgroup$ Jun 6, 2022 at 12:15
  • $\begingroup$ I can write it but i don't know how to prove then that it's composition of pr functions, i mean, there is a loop etc.. I guess i will go with my 2nd point if it is correct $\endgroup$
    – giggiox
    Jun 6, 2022 at 12:35

1 Answer 1

1
$\begingroup$

Here is a recursive function for your problem: \begin{align*} & \mathrm{count6}(n) = \mathrm{cond}(\mathrm{eq}(n, 0), 0,\\ & \quad \mathrm{add}(\\ & \quad \quad \mathrm{cond}(\mathrm{eq}(\mathrm{rem}(n, 10), 6), 1, 0), \mathrm{count6}(\mathrm{div}(n, 10))) \end{align*}

$\mathrm{eq}$ is defined as: $$ \mathrm{eq}(x, y) = \begin{cases}1\,\mathrm{iff}\,x = y\\ 0\,\mathrm{otherwise}\end{cases} $$ and $\mathrm{cond}$ as: $$ \mathrm{cond}(x, y, z) = \begin{cases}y\,\mathrm{iff}\,x=1\\ z\,\mathrm{otherwise}\end{cases} $$ Now you just need to show that $\mathrm{eq}$ and $\mathrm{cond}$ are recursive primitive which is tedious but not difficult.

$\endgroup$
3
  • $\begingroup$ "Now you just need to show ...". Why? That could be the main part of the exercise, since "i guess we can use this strategy, the problem is that we didn't cover it in the lectures, so i guess i can't use it" $\endgroup$
    – John L.
    Jun 7, 2022 at 1:49
  • $\begingroup$ I don't understand. If the lectures introduced the basic operations on primitive recursive functions then giggiox has the tools they need for showing that composite functions are primitive recursive. $\endgroup$ Jun 7, 2022 at 7:43
  • $\begingroup$ It may help the asker if you could describe (and prove) the exact lemma/theorem/tool that enables that "now you just need"? The definition of count6 in this answer involves recursion that is different from the primitive recursion operator in the usual definition of a primitive-recursive function. $\endgroup$
    – John L.
    Jun 7, 2022 at 13:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.