3
$\begingroup$

Let

$$f(x)=\begin{cases} x \quad \text{if Goldbach's conjecture is true }\\ 0 \quad \text{otherwise}\end{cases}$$

Show that f(x) is primitive recursive.

I know a primitive recursive function is obtained by composition or recursion, but I don't know what should I do about this problem.

|cite|improve this question
$\endgroup$
6
$\begingroup$

Goldbach's conjecture is either true or false. Do a case analysis on the two possibilities. In one case, $f(x)=x$, which is primitive recursive. In the other case, $f(x)=0$, which is also primitive recursive. Therefore $f$ is primitive recursive.

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ So the Goldbach's conjecture is irrelevant here? That's pretty misleading! $\endgroup$ – Gigili Oct 17 '12 at 15:12
  • 3
    $\begingroup$ @Gigili Not misleading; it check's whether you have understood the concept of computability (in contrast to algorithm design). $\endgroup$ – Raphael♦ Oct 17 '12 at 20:07
  • $\begingroup$ Sorry, but I figured out that your answer is not correct, it is not that simple. We need to prove that Goldbach's conjecture is PR as well. $\endgroup$ – Gigili Nov 17 '12 at 18:06
  • $\begingroup$ What does it mean to prove that Goldbach's conjecture is PR? The truthhood of it is PR. The problem is that we just don't know whether it is true or not. $\endgroup$ – Dave Clarke Nov 17 '12 at 19:01

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.