5
$\begingroup$

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 ?"

$\endgroup$
11
  • 3
    $\begingroup$ Your shock is justified. The "catch" here is that there's no mechanical way to find this upper bound (where mechanical means "computable"). In practice, the only way anyone has any clue to find such an upper bound is create a proof or disproof of the termination of each relevant problem. Which means you're back at square 1: either prove the Goldbach conjecture, or show that it fails, and that failure point is your upper bound! ;) Sad but true. $\endgroup$
    – Alex Meiburg
    Nov 26, 2016 at 8:21
  • 1
    $\begingroup$ I don't understand your question. The "number theoretic proof" is : 1) look at a program $P$ of length $n$ halting iff Goldbach is false, 2) prove that every halting program of length $\le n$ does it in less than $k$ steps, 3) run $P$ for $k+1$ steps. Of course nobody knows $k$. Now if your question is "can you prove that nobody knows $k$" then see why $k$ is in general non-computable $\endgroup$
    – reuns
    Nov 26, 2016 at 8:27
  • $\begingroup$ @AlexMeiburg Do you mean that our current best way to get a lower bound for (say) BB(100) is to encode a math problem in a program 100 "lines" long, find the first counterexample to be $N$ using "conventional" math, and then declare $N$ as the best lower bound for $BB(100)$? $\endgroup$
    – Ovi
    Nov 26, 2016 at 8:29
  • $\begingroup$ @user1952009 Yes sorry I know my question is not too clear, I will try to reformulate it a bit better $\endgroup$
    – Ovi
    Nov 26, 2016 at 8:30
  • $\begingroup$ Exactly. And there cannot, in general, be a more direct way of finding upper bounds, otherwise we could solve the halting problem that way. $\endgroup$
    – Alex Meiburg
    Nov 26, 2016 at 8:31

3 Answers 3

Reset to default
10
$\begingroup$

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...)

$\endgroup$
8
  • $\begingroup$ except your last sentence I don't see the point of your answer $\endgroup$
    – reuns
    Nov 26, 2016 at 8:35
  • 1
    $\begingroup$ @user1952009 Not sure why you say that. This answer seems to perfectly address the original poster's confusion. $\endgroup$
    – Dustan Levenstein
    Nov 26, 2016 at 8:44
  • $\begingroup$ I need to reread your answer a couple more times before I understand everything; maybe you already adressed this and it went over my head, but my shock has more to do with the following implication: Goldbach's is false $\implies$ counterexample $\le BB(100)$ (say). "Normally", in number theoretic problems, an upper bound for counterexamples can be extracted using more "standard" mathematical tools. However, it seems like the problem has an intrinsic upper bound of $BB(100)$ just by virtue of being able to be written in less than $100$ "lines". $\endgroup$
    – Ovi
    Nov 26, 2016 at 8:55
  • $\begingroup$ That's just because $BB(100)$ is defined (roughly) as "the largest number which is the minimal counterexample to a problem that can be written in less than $100$ lines". This is what I mean by saying Goldbach's conjecture is built into the definition of the busy beaver function, since it is one of those problems. $\endgroup$
    – Eric Wofsey
    Nov 26, 2016 at 8:57
  • $\begingroup$ So the "intrinsic" upper bound of $BB(100)$ really tells you nothing more about Goldbach's conjecture than the trivial "upper bound" $n$ I described in the first paragraph of my answer does. $\endgroup$
    – Eric Wofsey
    Nov 26, 2016 at 8:59
8
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ To correctly compute BB(27), one must first answer the question that whether the 27-state TM halts, by definition of busy beaver function. This is exactly the meaning from the answer of Eric: "Goldbach's conjecture is built into the definition of the busy beaver function, such that the upper bound you get is a useless tautology." $\endgroup$
    – Kevin
    Aug 4, 2021 at 5:46
1
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Thanks, you hit the nail right on the head. The upper bound arises solely from how difficult the problem is to code. $\endgroup$
    – Ovi
    May 20, 2017 at 14:24
  • $\begingroup$ If Goldbach's conjecture is not decideable in ZFC, this would imply (if I do not miss something) that ZFC cannot determine $BB(27)$ either because if it could, it could decide Goldbach. But as already mentioned, the number of steps would be far too large anyway. $\endgroup$
    – Peter
    May 23, 2017 at 22:55
  • $\begingroup$ @wythagoras Seems that $BB(18)$ is a new record! Amazing that it beats already Graham's number! Has this actually been proven ? $\endgroup$
    – Peter
    May 23, 2017 at 22:59
  • 2
    $\begingroup$ @Peter Yes, I proved this in 2016. See googology.wikia.com/wiki/User_blog:Wythagoras/… $\endgroup$
    – wythagoras
    Jun 15, 2017 at 16:19

You must log in to answer this question.

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