3
$\begingroup$

A consequence of the Halting-Problem is that there isn't a Turingmachine for the Entscheidungsproblem of Hilbert.

An exersice I have to work on has the question: Does there exist a TM that prints 1 if the Goldbach Conjecture holds and prints 0 otherwise?

I guess there isn't a TM for this problem. But I can't argue with the Entscheidungsproblem because it deals with a "general" machine that takes mathematical conjectures as an input and not a specific one.

What could be an argument that there isn't a TM for the decision whether the Goldbach conjecture holds or not?

Thank you for hints!

$\endgroup$
2
  • $\begingroup$ @SooS: I don't see a requirement that the Turing machine has to compute a proof for whether Goldbach holds or not; it just needs to compute the answer. By the way, it might well be the case that Goldbach is neither provable nor disprovable (from $\mathsf{ZFC}$, say). But in your question you talk about whether it "holds", which suggests to me that you are asking about whether it is true or not. Mathematicians almost universally believe that first-order statements about $\mathbb N$ have objective truth values, regardless of whether they are provable from a given axiom system or not. $\endgroup$
    – Joe
    Apr 12 at 20:39
  • $\begingroup$ There is a less trivial answer to a question which is weaker than yours: "Is there a Turing machine which halts if and only if the Goldbach conjecture is false?". The answer is yes, and we can construct such a TM very explicitly (basically, just look for a counterexample). There is interesting logic behind this, and it leads into some of the discussion here. Particularly, this is not true in the same way of the twin prime conjecture, for example. $\endgroup$ Apr 12 at 21:14

2 Answers 2

8
$\begingroup$

Yes, there is one: either the Goldbach conjecture is true or it is not. If the Goldbach conjecture is true, then a Turing machine computing the function $f(n)=1$ will do the job; otherwise, a Turing machine computing the function $g(n)=0$ works. Without knowing the answer to the Goldbach conjecture, we of course don't know which of these Turing machines does the job; but this doesn't stop us from concluding that there exists a Turing machine which computes the answer to this problem.

$\endgroup$
1
  • $\begingroup$ @SooS In classical logic, "there is a TM computing P" is equivalent to "it is not the case that all TMs fail to compute P". This is by DeMorgan laws: $\exists t.\ P(t)$ is equivalent to $\lnot\forall t.\ \lnot P(t)$. Hence, to prove an $\exists t$ statement you don't actually have to construct a working $t$, it's enough to prove that it's impossible that all the $t$ fail. This reasoning would not be acceptable in constructive logic, but we commonly reason in classical logic, even when studying computability. $\endgroup$
    – chi
    Apr 13 at 8:04
3
$\begingroup$

Yes. There does exist such a Turing machine, even if you don't know what it is. See https://cs.stackexchange.com/q/367/755.

$\endgroup$
1
  • $\begingroup$ I see the point in this thread. One of these TMs gives the correct answer. But to call a Problem decidable or computable, we exactly need 1 TM, or where is my fault? It's strange $\endgroup$
    – SooS
    Apr 12 at 23:44

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .