Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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$. – Pål GD Jan 17 '13 at 18:54

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).

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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