A number that can't be calculated
amolas.dev
A number that can't be calculated
1–10 of 79 posts
Re: A number that can't be calculated
#2I’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-illumina...
Re: A number that can't be calculated
#3I’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 fo…
> 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.
Re: A number that can't be calculated
#4I’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 fo…
Thanks 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> 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.
Re: A number that can't be calculated
#5cool series. In my opinion, Chaitin constant is the best example to understand incomputable numbers, hopefully author can include it later.
Re: A number that can't be calculated
#6cool series. In my opinion, Chaitin constant is the best example to understand incomputable numbers, hopefully author can include it later.
Thanks for your comment! Indeed, Chaitin constant is an amazing example, however I failed to understand how can it be computed at least approximately. What I like about the example in the post is that you can compute some digits of the $\Omega$ constant, which in my opinion is more pedagogical.
If you have some resources regarding Chaitin constant I would be very happy to read them :)
Re: A number that can't be calculated
#7cool series. In my opinion, Chaitin constant is the best example to understand incomputable numbers, hopefully author can include it later.
Thanks for your comment! Indeed, Chaitin constant is an amazing example, however I failed to understand how can it be computed at least approximately. What I like about the example in the post is that you can compute some digits of the $\Omega$ constant, which in my opinion is more pedagogical. If you have some resources regarding Chaitin constant I would be very happy to read them :)
I'll look some videos from a while ago. Again, great series, hope you keep publishing!
Re: A number that can't be calculated
#8Earlier quoted context omitted.
Thanks for your comment! Indeed, Chaitin constant is an amazing example, however I failed to understand how can it be computed at least approximately. What I like about the example in the post is that you can compute some digits of the $\Omega$ constant, which in my opinion is more pedagogical. If you have some resources regarding Chaitin constant I would be very happy to read them :)
I'll look some videos from a while ago. Again, great series, hope you keep publishing!
haha thank you very much! I'm happy you enjoyed it :)
Re: A number that can't be calculated
#9I think it’s much simpler than that. If you remember your maths well enough to remember the proof that the reals are uncountable and the rationals are countable, consider that the list of programs that produce a number is countable. You don’t need to check if the program halts or not, even if we “count” the “numbers” from
the programs that don’t halt _it’s still countable_. But we’re still left with an uncountable set of numbers for which we can’t even write a program.
Easiest way to construct one is to use the diagonal argument that’s used to prove, amongst other things, the halting problem.
Re: A number that can't be calculated
#10> Even if God himself came from Heaven, he could not compute these numbers. Uncomputable numbers are numbers that can’t be computed because of maths limitations.
I like to think that God has access to much better math and computational resources than we can even begin to conceive of. ;-)