# Relation between Halting problem and Godel's incompleteness Theorem

I've heard that these are closely related to each other. However, while the former looks totally trivial to me, the latter still puzzles me even after I read the proof of it. So I made up a scenario to check my understanding.

Let's suppose that I believe Goldbach's conjecture to be false for some reason. And I'm running a simple python program to find the counterexample of it on my desktop. The program checks each case in increasing order. When it finds a counterexample, it returns the number and stops.

Then one day, someone proved that Goldbach's conjecture is unprovable. From my understanding, it doesn't mean that I should stop the program right then. What is proven is that there is no proof stating that my program will run forever, even if Goldbach's conjecture is true and my program actually run forever. So it's reasonable to keep the program running and expect the program to find the counterexample even tomorrow. Also, I can say that there is still a chance to disprove Goldbach's conjecture.

Is that correct?

• What you say is true, if I understand you correctly, but I think you've missed the point. The incompleteness theorem says that there are true statements that are unprovable. If math is consistent, all false statements are unprovable. Commented Feb 17, 2021 at 14:04
• What you possibly mean : If we can prove in ZFC that Goldbach is undecidable in PA, then we have proven Goldbach's conjecture. PA can never detect this undecidability because then it could prove Goldbach which it cannot. Commented Feb 17, 2021 at 14:11
• If Goldbach is false, this can be proven within PA (which is also intuitively clear). If it is true then a turing machine (or a computer program) searching for counterexamples will never halt. In this case it can be provable or unprovable. Commented Feb 17, 2021 at 14:12

## 1 Answer

I'm not sure what your example has to do with the Incompleteness Theorem. If the Goldbach Conjecture is false, then yes, your program will eventually find a counterexample and thus prove it to be false. But if it is true, we might still be able to prove it true as well.

For example, suppose I have a computer program that tests the hypothesis that every even number greater than $$2$$ is the sum of two odd numbers by going through all such even numbers one by one, just like your program. Now, we know this hypothesis to be true, and so your computer program will run forever. But, does this mean that we can't prove the hypothesis? Of course not .. and the proof is elementary.