4 ms·
I’m not sure I buy the argument that you can say that we know the halting problem is unsolvable and therefore we can’t calculate BB. The halting problem is uns
by swid 4y ago
I’m not sure I buy the argument that you can say that we know the halting problem is unsolvable and therefore we can’t calculate BB.
The halting problem is unsolvable due to a contradiction, but there is a finite set of programs with given number of symbols; one or more of them share the max non infinite running time, and if you did have the oracle to answer that, you can in fact run the algorithm provided, except for how long this would take in real time.
A different take is that you can write a program that will only terminate if ZF set theory is false, which is impossible to prove using math due to Gödel's incompleteness theorems. We assume this program should run forever, but would not be able to prove it. That program provides some upper bound to the highest BB number we could ever hope to prove with certainty: 748 according to this article from a few years back.
The problem of the post is that an all knowing oracle doesn’t have this problem, and assuming the program has finite length, our being able to prove whether it halts or not does not stop there from being an answer to that question.
https://www.quantamagazine.org/the-busy-beaver-game-illuminates-the-fundamental-limits-of-math-20201210/ https://www.quantamagazine.org/the-busy-beaver-game-illumina...
- zaik 4y ago> if you did have the oracle to answer that I think you are correct, but the question is simply if we can compute this maximum number - without any oracles. Then the answer will be no, since we could decide the halting problem as shown by the author.
- alexmolas 4y agoThanks for the link, it was an interesting read! I'm not arguing that you can't calculate BB numbers, in fact we've calculated some of them. What I'm arguing is that you can't calculate all the BB numbers, since this will mean that the Halting Problem is solvable. Using the results of your link I guess we can say that BB numbers can be computed if n<748 (or <20 according to Aaronson). > In 2016, he and his graduate student Adam Yedidia specified a 7,910-rule Turing machine that would only halt if ZF set theory is inconsistent. This means BB(7,910) is a calculation that eludes the axioms of ZF set theory. Those axioms can’t be used to prove that BB(7,910) represents one number instead of another, which is like not being able to prove that 2 + 2 = 4 instead of 5. OMG! A number that's so much big that can be contained in the ZF set theory.
- NotYourLawyer 4y agoYes, an all-knowing oracle knows the busy beaver numbers.
- alexmolas 4y agoI don't think so. If that was the case, then for any program we could compute its length n, and then ask the all-knowing oracle the value of BB(n). And knowing BB(n) for any n we could solve the Halting Problem, but we know that the Halting Problem is unsolvable. Therefore we must conclude that such an all-knowing oracle can't exist.
- NotYourLawyer 4y agoYes, that’s my point. The all-knowing oracle could also just tell you whether or not your program halts.