# How to show that f(x) is primitive recursive?

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.

• Commented Oct 17, 2012 at 20:07

## 1 Answer

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.

• So the Goldbach's conjecture is irrelevant here? That's pretty misleading! Commented Oct 17, 2012 at 15:12
• @Gigili Not misleading; it check's whether you have understood the concept of computability (in contrast to algorithm design). Commented Oct 17, 2012 at 20:07
• 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. Commented Nov 17, 2012 at 18:06
• 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. Commented Nov 17, 2012 at 19:01