# For which Millennium Problems does undecidable -> true?

Gregory Chaitin has quoted Marcus du Sautoy to the effect that:

If the Riemann Hypothesis (RH) is undecidable this implies that it's true, because if the RH were false it would be easy to confirm that a particular zero of the zeta function is in the wrong place.

Question(s)  Which of the other five (at present) unsolved Clay Institute Millenium Prize Problems similarly have the attribute $\text{undecidable}\to\text{true}$? And do any of the five have the attribute $\text{undecidable}\to\text{false}$?

Context  This question first arose in the discussion of "a whole lot of basic questions" that were asked by Tim Gowers on Dick Lipton and Ken Regan's weblog Gödel's Lost Letter and P-NP.

Edit Dick and Ken subsequently posted an essay Why We Lose Sleep Some Nights in which (in a comment) the question is associated to the immanence of the eschaton (or perhaps not) in computational complexity theory. ☺

-
The point is that if there's a counterexample then one can prove it by a contour integral: no need to actually locate the zero, only to prove there's one in a circle disjoint from the critical line. –  Noam D. Elkies Sep 30 '12 at 3:03
So if I understand correctly, this is essentially asking which of these statements are equivalent to a $\Pi_1^0$ statement, right? –  Harry Altman Sep 30 '12 at 4:01
If an elliptic curve has rank at least $n$ we can always write down $n$ rational solutions. If the $L$-function has a zero of order less than $n$ at $s=1$ then we can determine this by accurately approximating a contour integral in sufficiently small loop around $s=1$, which I think is always possible. If this works then undecidability of BSD implies that the analytic rank is greater than the algebraic rank. The other inequality appears more elusive. –  Will Sawin Sep 30 '12 at 5:59
Will - yes, but the undecidable bit is to prove that a CW-complex is not simply connected. There is a partial algorithm that terminates if and only if an input CW-complex is simply connected or, equivalently, an group presentation presents the trivial group, and this is enough for these purposes. The partial algorithm simply tries to write each generator as a product of conjugates of relators. –  HJRW Sep 30 '12 at 6:54
It is undecidable whether a 2-complex is simply connected, but it is decidable whether a 3-manifold is simply connected. (This should not be shocking to someone who know how to make a 4-manifold with arbitrary fundamental group.) –  Ben Wieland Sep 30 '12 at 19:03