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


1 Answer 1


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.

  • 1
    $\begingroup$ So the Goldbach's conjecture is irrelevant here? That's pretty misleading! $\endgroup$
    – Gigili
    Commented Oct 17, 2012 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
    Commented Oct 17, 2012 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
    Commented Nov 17, 2012 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$ Commented Nov 17, 2012 at 19:01

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.