Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

A number that can't be calculated

amolas.dev

Post reply on HN
Print view View original

11–20 of 79 posts

Re: A number that can't be calculated

#11

Post by fallingfrog »

Something about that proof feels wrong.. Are you sure the allusion to the halting problem applies here?

The proof that the halting problem can't be computed relies on a self-reference where you query whether the program halted and then do the opposite. But- and here's the important part- when the program references itself it requires at least one more symbol to do so as it needs somewhere to store the answer. It therefore needs an infinite stack. But we have a fixed number of symbols. Or, to put it another way: if your set of symbols is bounded, then you can only call functions that use at least one fewer symbol than the calling one, which means you will eventually run out of symbols and have a base case. Doesn't that mean the halting problem doesn't apply to the busy beaver problem?

Re: A number that can't be calculated

#12

Post by VyseofArcadia »

I mean, almost every real number is not computable. If you stick your hand into a grab-bag of reals, you will grab an incomputable number with probability 1. As another commenter mentioned, the computable reals are countable, and the reals are very much not.

There is a whole field of mathematics striving to see how far you can go, analysis-wise, with just computable numbers.[0]

[0] https://en.wikipedia.org/wiki/Computable_analysis

Re: A number that can't be calculated

#13

Post by kotlin2 »

moomin wrote: post #9

I 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 se…

You have an assumption that each number needs a unique program to compute the digits. You'd need to prove that statement first.

Re: A number that can't be calculated

#14

Post by tromp »

alexmolas wrote: post #6
sebastialonso wrote: post #5

cool 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 :)

Chaitin computed the first few bits of a LISP based version of Omega in one of his books. For my own lambda based version of Omega I was able to compute the first 4 bits [1].

[1] https://tromp.github.io/cl/Binary_lambda_calculus.html#Halti...

Re: A number that can't be calculated

#15

Post by tromp »

> If after these steps the program hasn’t halted it means it’ll never halt (by the definition of the Sigma(n))

This argument doesn't quite work since Sigma(n) is the maximum number of characters printed before halting rather than the maximum finite number of steps of computation. The argument would work for the other flavor of Busy Beaver though.

Re: A number that can't be calculated

#16

Post by NotYourLawyer »

swid wrote: post #2

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 fo…

Yes, an all-knowing oracle knows the busy beaver numbers.

Re: A number that can't be calculated

#17

Post by Kranar »

Don't think this article is correct when it says that Omega can't be computed to arbitrary precision, it certainly can be. While it's true that there is no algorithm that can compute BB(n) for all n, it is always possible to compute BB(k) for a specific and arbitrary k. This is a very subtle detail.

Similarly for Omega, while there's no algorithm that can compute Omega to an arbitrary precision, that is not the same as saying that there's some upper bound on the precision that Omega can be computed. For any precision k, it's possible to compute Omega up to that precision. The issue is that whatever algorithm you devise to compute Omega up to a precision of k, that algorithm will fail to compute Omega for some other precision q > k. You will need a fundamentally different algorithm for q > k, but such an algorithm does exist. You'll also need a fundamentally different algorithm for precision r > q, but that also exists... ad infinitum.

Re: A number that can't be calculated

#18

Post by kotlin2 »

I'm unfamiliar with BB(n), so this raises an interesting question for me. How do we know that BB(n) exists for all n? This is relevant to this post because the author's definition of omega relies on BB(n) being defined for all n. Obviously there are numbers that are not computable, but it seems one needs to be careful that the numbers discussed are sure to exist.

Re: A number that can't be calculated

#19

Post by morelisp »

kotlin2 wrote: post #18

I'm unfamiliar with BB(n), so this raises an interesting question for me. How do we know that BB(n) exists for all n? This is relevant to this post because the author's definition of omega relies on BB(n) being defined for all n. Obviously there are numbers that are not computable, but it seems one needs to be careful that the numbers discussed are sure to exist.

> How do we know that BB(n) exists for all n?

It's trivial to construct a candidate for each n, which gives a lower bound.

Re: A number that can't be calculated

#20

Post by craggyjaggy »

kotlin2 wrote: post #13
moomin wrote: post #9

I 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 se…

You have an assumption that each number needs a unique program to compute the digits. You'd need to prove that statement first.

How can the same program produce multiple different results?
Post reply on HN