13
$\begingroup$

Background: I am a complete layman in computer science.

I was reading about Busy Beaver numbers here, and I found the following passage:

Humanity may never know the value of BB(6) for certain, let alone that of BB(7) or any higher number in the sequence.

Indeed, already the top five and six-rule contenders elude us: we can’t explain how they ‘work’ in human terms. If creativity imbues their design, it’s not because humans put it there. One way to understand this is that even small Turing machines can encode profound mathematical problems. Take Goldbach’s conjecture, that every even number 4 or higher is a sum of two prime numbers: 10=7+3, 18=13+5. The conjecture has resisted proof since 1742. Yet we could design a Turing machine with, oh, let’s say 100 rules, that tests each even number to see whether it’s a sum of two primes, and halts when and if it finds a counterexample to the conjecture. Then knowing BB(100), we could in principle run this machine for BB(100) steps, decide whether it halts, and thereby resolve Goldbach’s conjecture.

Aaronson, Scott. "Who Can Name the Bigger Number?" Who Can Name the Bigger Number? N.p., n.d. Web. 25 Nov. 2016.

It seems to me like the author is suggesting that we can prove or disprove the Goldbach Conjecture, a statement about infinitely many numbers, in a finite number of calculations. Am I missing somehing?

Improve this question
$\endgroup$
3
  • $\begingroup$ @Evil I would think it's possible that some mathematical conjectures are still unresolved because their proposed proofs rely on a finite (yet unfathomably large) number of calculations. I just wanted to check that this wasn't the case with the Goldbach conjecture. $\endgroup$
    – Ovi
    Commented Nov 26, 2016 at 5:11
  • $\begingroup$ Keep in mind that all formal proofs consist of a finite number of steps, whether they concern "a statement about infinitely many numbers" or not. In this hypothetical situation the claim depends on "knowing" an upper bound on how many even numbers have to be checked to verify (or contradict) Goldbach's conjecture. $\endgroup$
    – hardmath
    Commented Nov 26, 2016 at 14:53
  • 1
    $\begingroup$ your question gets to the heart of mathematical proofs which generally manage to convert infinite properties into finite logical statements. "how this happens" is still under study. hes also pointing out the correspondence of undecidable problems to open mathematical problems, there is nearly a 1-1 correspondence for all open mathematical conjectures. (might cook this into answer with refs sometime if there is interest eg expr via upvotes). also more discussion in Computer Science Chat & my blog etc $\endgroup$
    – vzn
    Commented Nov 29, 2016 at 22:31

5 Answers 5

Reset to default
11
$\begingroup$

The statement is about infinitely many numbers, but its demonstration (or refutation) would have to be a finite exercise. If possible.

The surprise may come from the (false) assumption that finding BB(100) would be a "theoretically easier" problem, only made impossible for practical reasons - since there are so many machines, and they can run for such a long time before stopping, if at all - after all, they're just machines...

The truth is that discovering BB(n), for n large enough, has to be an unsurmountable task, for both theoretical and practical reasons.

Improve this answer
$\endgroup$
3
  • 2
    $\begingroup$ Hm so let me make sure I understand it. BB(n) measures the number of "steps" that can be taken in 100 "lines" of code (for programs that do not halt). If we can make a program 100 lines or less that checks each even number, and it does not halt in BB(100) steps, then it wil never halt, thereby proving the conjecture true? $\endgroup$
    – Ovi
    Commented Nov 26, 2016 at 7:08
  • 3
    $\begingroup$ @Ovi Not quite. $BB(n)$ is the greatest possible number of steps that a program with "$n$ lines" of code can run for, if it does halt. But the rest of your comment is exactly correct. $\endgroup$
    – David Richerby
    Commented Nov 26, 2016 at 13:17
  • 3
    $\begingroup$ @Ovi The point is that if Goldbach conjecture is false, than any TM that checks that conjecture will halt in a finite number of steps (because it will find a counterexample). If such a machine has $n$ states and assuming that Goldbach conjecture is false, i.e. that said machine halts after a finite number of steps, then this number of steps is, by definition, smaller than $BB(n)$. In the other direction: if we run this machine for $BB(n)$ steps and it did not find a counterexample then we know that that machine does not halt, hence Goldbach conjecture is true. $\endgroup$
    – Bakuriu
    Commented Nov 26, 2016 at 14:30
9
$\begingroup$

The idea from the author was that you can write a program in 100 lines (any fixed finite number here) which does the following: takes number x, tests conjecture. If not true then stop else continue on the next number.

Knowing busy beaver number you can simulate this machine for that number of steps and then decide if it halts or not. From above, if it halts - conjecture not true, if it doesn't halt - conjecture is true.

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ "if it doesn't halt - conjecture is true", because after the machine has run more than BB(100) steps, it will never halt. $\endgroup$
    – Albert Hendriks
    Commented Dec 1, 2016 at 9:54
9
$\begingroup$

Aaronson has recently expanded in detail on this musing/ idea here working with Yedidia.[1] they find an explicit 4888 state machine for the Goldbachs conjecture. you can read the paper to see how it was constructed. TMs are rarely constructed but those that have been tend to be compiler-like based on high level languages and the compilers add many states. a "hand built" TM could easily use an order-of-magnitude less amount of states, eg in the 100s or less than 100. in other words there was not really an attempt in this paper to try to really minimize the # of states. the general idea is sound and computer scientists are generally not so worried about exact constants wrt applied work.

this general theory is outlined by the Caludes (also cited by [1]) in two excellent papers which lay out some of the long-folklore theorems in this area and which has been noted by other authors (eg Michel).[2][3] basically any open mathematical problem can be converted to undecidable problems. this is because most mathematical problems involve searching an infinite number of cases for counterexamples and counterexamples are algorithmically checkable (but maybe inefficiently or requiring large TMs etc).

also, "very small" TMs (counted in # of states) can check/ be equivalent very complex math problems. eg a rough estimate for a TM to resolve the collatz conjecture would be a few dozen states.

so there is an interesting connection/ analogy between undecidability and NP completeness. NP is the class of efficiently checkable problems, ie instances can be checked in P time. undecidable problems are the class of all problems that allow algorithmic checking for counterexamples with no limit on efficiency.

here is a basic way to understand the connection with the busy beaver problem. all undecidable problems are equivalent due to Turing computability/ equivalence. much like all NP complete problems can be converted to each other in P time (reductions), all undecidable problems are equivalent due to Turing completeness and computable reductions (which can take arbitrary time). hence busy beaver problem is in this sense equivalent to the halting problem, and if one could solve busy beaver, then one could solve all open mathematical questions.

[1] A relatively small TM whose behavior is independent of set theory / Yedidia, Aaronson

[2] Evaluating the Complexity of Mathematical Problems: Part 1 / Calude

[3] Evaluating the Complexity of Mathematical Problems: Part 2 / Calude

Improve this answer
$\endgroup$
2
1
$\begingroup$

  1. The Goldbach conjecture can be falsified (if actually false) by such a TM program; it can not be proven correct in this way (an insightful mathematician, however, might do this).

  2. Knowing BB(27) would allow to stop the Goldbach search at some point; nevertheless BB(27) (or Chaitin's Omega(27)) previously will require to know, whether the Goldbach TM eventually stops, or not.

It is therefore misleading to say "BB(27) includes the answer to Goldbach". Though it does, more to the point is: "Goldbach (and many many others) are prerequisites to the number BB(27)", in other words there is no such thing as a "BB-function" you challenge at 27. We just run all 27-state machines, inkl. Goldbach, and only after the fact see BB(27). And, from a practical POV, even BB(6) seems elusive.

Improve this answer
$\endgroup$
0
$\begingroup$

I think it feels less mysterious if we restate Aaronson's point in terms of proofs:

We can name a constant $C$ so that, if there were any disproof of Goldbach's, it would be at most $C$ characters long. Thus, if we knew $C$, we could prove or disprove the conjecture by listing all strings of length at most $C$ and checking if any of them is a valid proof.

It's somewhat magical that one could name $C$ without knowing whether Goldbach's is true or not (though in practice $C$ is way too large). I feel like the easiest way to see this is via Turing Machines. The TM that enumerates and checks all possible counterexamples to Goldbach's has finite description length $n$, so if it halts, it does so in fewer than $BB(n)$ steps. A transcript of this computation would be a valid disproof and would take only $C = O(BB(n))$ characters.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.