2
$\begingroup$

Let $\varphi(x)=2x$ if $x$ is a perfect square, $\varphi(x) = 2x+1$ otherwise. Show $\varphi$ is primitive recursive.

In proving $\varphi$ to be a p.r. function I think it could come in handy the following theorem:

Let $\mathcal C$ be a PRC class. Let the functions $g$, $h$ and the predicate $P$ belong to $\mathcal C$, let

\begin{equation} f(x_1,\ldots, x_n) = \begin{cases} g(x_1, \ldots, x_n) \;\;\;\;\;\text{ if } P(x_1, \ldots, x_n)\\ h(x_1,\ldots,x_n) \;\;\;\;\;\text{ otherwise} \end{cases} \end{equation} Then $f$ belongs to $\mathcal C$ because $$f(x_1, \ldots, x_n) = g(x_1, \ldots, x_n) \cdot P(x_1, \ldots, x_n) + g(x_1, \ldots, x_n) \cdot \alpha(P(x_1, \ldots, x_n))$$ where

\begin{equation} \alpha(x) = \begin{cases} 1 \;\;\;\;\;\text{ if } x = 0\\ 0 \;\;\;\;\;\text{ if } x \neq 0 \end{cases} \end{equation}

and $\alpha(x)$ is p.r.

So similarly I would say that $\varphi(x)$ is p.r. as

\begin{equation} \varphi(x) = \begin{cases} 2x \;\;\;\;\;\;\;\;\;\;\;\text{ if } x = t \cdot t \\ 2x+1 \;\;\;\;\;\text{ otherwise} \end{cases} \end{equation} hence $$\varphi(x) = 2x \cdot P(x_1, \ldots, x_n) + (2x+1) \cdot \alpha(P(x_1, \ldots, x_n))$$ and $P$ is a primitive recursive predicate as $x \cdot y$ is p.r. and also $x = y$.

Does everything hold? Is there anything wrong? If so, since I am tackling this kind of exercise for the fist time, will you please tell me what's the proper way to solve this?

$\endgroup$
  • 2
    $\begingroup$ You need to show that you can write an "if,then,else"-function, i.e. $f(x,y,z) = y$ if $x$ is true and $z$ otherwise. Then you need to show that you can test whether or not $x$ is a perfect square. This you can do by iterating $i$ from 1 to $x$ testing if $i^2 = x$. $\endgroup$ – Pål GD Jan 17 '13 at 18:54
1
$\begingroup$

To see if $x$ is a perfect square is easy (for example, by adding 1 + 3 + 5 ... you get the succesive squares); once that is settled your problem is solved. Think of such problems primarily as programming asignments (in a rather cruel programming language).

$\endgroup$
  • $\begingroup$ Not so cruel, once you developed the right tools. All you need here is bounded existential quantification: is_square(x) = $\exists n \le x, n^2 =x$. $\endgroup$ – Andrea Asperti Feb 23 '17 at 12:57

Your Answer

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

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