Suppose I told you that the Goldbach conjecture is one of those. (The Goldbach conjecture supposes that every even integer number can be expressed as the sum of two odd primes.)

Is that logically possible? (And, no, I haven't proved it!)

This puzzle is stated wrong. It is possible for Goldbach's Conjecture GC to be true and unprovable. We'll never find a counter-example but will never know if one exists.  It cannot be that GC is FALSE and we cannot prove that fact.  This is the miswording of this puzzle.  If FALSE there is a counter-example and we can find it.<o:p></o:p>

Just like Godel's 2nd Incompleteness Theorem says we may be consistent but then will be unable to prove it. Consistent means no proof of a contradictory sentence P&~P can be found but we'll never prove that - Goldbach is saying no proof of a counter-example number can be found but likewise perhaps we'll never prove it.<o:p></o:p>

The solution says if GC is true then the program doesn't stop so it's true and we just proved it. No! We only said that if we are given that GC is true, then "GC is true!!" is true so GC is true. We didn't prove it - we just repeated our given assumption.  We didn’t show that we can actually prove it.<o:p></o:p>

GC can't be FALSE and not provably false. If false, there is a counter-example and we can find it and showing it gives a proof that GC is FALSE. It is not possible for ~GC but ~ |- ~GC. GC can't be FALSE and undecidable, not resolvable, not provably so. If FALSE we can prove it is FALSE!<o:p></o:p>

Formally we say that GC being FALSE is recursively enumerable. (exists x)P(x) where P() is recursive means if P(N) then |- P(N) we can prove it and ~|-~P(N) we cannot refute P(N). (exists x) is "a counter-example x exists" and P(N) is "N if even is the sum of 2 primes". That is easy to check so it is recursive, so when it is FALSE it is provably false.<o:p></o:p>

The basic conclusion comes from Marvin Minsky's Computation: Finite and Infinite Machines.<o:p></o:p>