Goldbach Conjecture and the Busy Beaver function?

Question

Background: Math undergrad, but complete layman in computer science

I recently asked this question on CS stackexchange. I hope I am interpreting the answers correctly:

Suppose we make a program to check that every even number greater than $2$ is the sum of two primes and run. All we have to do is run it for a certain, finite ammount of time; if a counterexample is found in that time, the conjecture is false. If no counterexample is found in that time, then the program will never halt so therefore the conjecture is true. Therefore there is an upper bound for the first possible counterexample.

My question is, how is this upper bound encoded mathematically in the Goldbach conjecture? Does this mean that any math problem can be answered by brute force in a finite ammount of time? I am still in shock; all my life I've been told that if you have a statement about infinitely many numbers, you will never be able to conclude that it is true by just plugging in more and more numbers; but apparently this is possible.

To me it's unbelivable that the upper bound for the smallest counterexample depends on our ability to encode the problem in a program.

EDIT: Reformulation suggested by user1952009 in the comments:

"What happens if someone had (for every nn) an upper bound for B(n)B(n). He can solve the halting problem and every number theory conjecture, so what ?"

Answer 1

This is much less deep than you seem to think it is. In fact, it is trivial that there exists a number $n$ with the property that there exists a counterexample to Goldbach's conjecture $\leq n$ iff Goldbach's conjecture is false. Namely, if Goldbach conjecture's is true, let $n=0$, and if Goldbach conjecture's is false, let $n$ be the smallest counterexample. Since Goldbach conjecture's is either true or false, either way there exists such an $n$. We just can't explicitly say what this $n$ is (because we don't know whether the conjecture is true, and we don't know what the least counterexample is if it's false).

The exact same thing is going on with the $n$ obtained from the busy beaver function. The definition of the busy beaver function involves testing which Turing machines halt, asking how long the ones that do halt take to halt. So part of the definition of the busy beaver value that you use to obtain your upper bound involves asking whether the computation you described ever halts, and taking the number of steps it takes if it does. That is, the definition of the busy beaver value you are using as an upper bound is basically the same as the definition of $n$ I gave in the previous paragraph, except that instead of just testing Goldbach's conjecture you are testing every conjecture that can be tested by running a Turing machine with a certain number of states.

So, it's not so much that the busy beaver function is built into Goldbach's conjecture. Rather, Goldbach's conjecture is built into the definition of the busy beaver function, such that the upper bound you get is a useless tautology.

---

Here's an even sillier variant on what's going on here. I claim there exists a very simple computation which correctly answers whether Goldbach's conjecture is true. Namely, if Goldbach's conjecture is true, take the computation that just immediately outputs "true". And if Goldbach's conjecture is false, take the computation that just immediately outputs "false". Goldbach's conjecture is either true or false, so either way one of these computations works! (We just don't know which one...)

Answer 2

It has been proved that there is a 27-state TM that halts if Goldbach's conjecture is false, and doesn't halt if Goldbach's conjecture is true.

Therefore, if we know $\mathrm{BB}(27)$, we can prove that Goldbach's conjecture is false if the machine halts, or that Goldbach's conjecture is true by simulating the machine for $\mathrm{BB}(27)$.

However, we will probably never know $\mathrm{BB}(7)$,

which is already known to be larger than $10^{10^{10^{10^{18705352}}}}$.

Let alone $\mathrm{BB}(27)$. $\mathrm{BB}(27)$ (in fact $\mathrm{BB}(18)$) is at least larger than Graham's number, but such a lower bound is probably so far from the actual value that the comparison is laughable.

Such a simulation is almost certainly physically impossible.

Answer 3

OP, I share your amazement. I understand in part Eric Wofseys lack of amazement but believe he left out the detail that you found amazing, or at least the one I do - the upper bound to the disproof arises solely from the complexity of the least complex possible tester. The simpler a conjecture is to test exhaustively/enumeratively, the lower the upper bound of a disproof has to be. The other mind bending thing, to me, is that while I know there isn't enough time or power to actually do so, one could hypothetically prove or disprove the Goldbach conjecture or any other machine testable one in finite time without knowing anything about it except how to test it. Proving the Goldbach conjecture this way seems even obscure than a non constructive existential proof - "this kind of thing exists but I couldnt point to one or make it for you."

To answer your second question, I believe this means that any mathematical conjecture which could certainly be disproven in a finite amount of time if a counterexample exists can be disproven in a bounded amount of time where the bound is determined by BB(number of states necessary to carry out exhaustive search for counterexample.)

To touch back on your first question: While granting that numbers like Graham's number and BB (27) are "very big," there are an infinite number of still larger numbers. It appears that the easier it is to search for a countered ample to a conjecture, the smaller it's countered ample must be (as per this line of reasoning. Other math might be able to much more limit it's upper bound.) So it seems that, and this is very interesting, it is impossible to have a "simple" conjecture (simple to test for counterexample) which has an arbitrarily large counterexample. I don't know what's intrinsic about that.

I could be wrong, but I'm going to guess that Loader's number is greater than BB (27). I don't have a clue what, intrinsically, about the Goldbach conjecture makes it impossible for the least counterexample of it (or any other possible conjecture with the same or less complexity to test) to be larger than Loader's number.

Wythagoras, thanks for the details. Didn't know BB(18) was greater than G64. That just means BB (27) is "extra" hopelessly big.