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

21–30 of 79 posts

Re: A number that can't be calculated

#21

Post by dllthomas »

Kranar wrote: post #17

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…

> it is always possible to compute BB(k) for a specific and arbitrary k

How do you do that once k is large enough that it admits Turing machines whose halting behavior is independent of our axioms?

Re: A number that can't be calculated

#22

Post by sblom »

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.

By definition, each program only produces the digits of one number. It's okay for more than one program to produce the same number. Am I misunderstanding your point?

Re: A number that can't be calculated

#23

Post by alexmolas »

Kranar wrote: post #17

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…

> it is always possible to compute BB(k) for a specific and arbitrary k

but wouldn't this be equivalent to solve the Halting Problem?

Re: A number that can't be calculated

#24

Post by kibwen »

ashton314 wrote: post #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. ;-)

There are numbers that god can't compute, but that supergod can compute. Of course, that also means there are numbers that supergod can't compute, but that superdupergod can compute. And from there it's turtles all the way up.

Re: A number that can't be calculated

#25

Post by alexmolas »

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…

yes, I didn't think about it, but you're right! However, I liked the idea to have a constructive way to build an uncomputable number

Re: A number that can't be calculated

#26

Post by alexmolas »

NotYourLawyer wrote: post #16
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.

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

Re: A number that can't be calculated

#27

Post by tshaddox »

alexmolas wrote: post #23
Kranar wrote: post #17

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…

> it is always possible to compute BB(k) for a specific and arbitrary k but wouldn't this be equivalent to solve the Halting Problem?

No, because the halting problem requires implementing a function that can compute whether any other function halts. It has to work for any possible function you give it. You can, of course, compute whether some functions halt. Two easy ways to do so are to observe that it halts or observe an infinite loop.

Re: A number that can't be calculated

#28

Post by opportune »

VyseofArcadia wrote: post #12

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/Compu…

This is pretty trivial because given countably infinite sized Turing machines (for the machine instructions to be enumerable its size must be countably infinite) T and countably infinite sized number of iterations N, we have the mapping f(t, n) -> x where by definition all X are the computible numbers. Since all x have at least one corresponding pair t, n, then |X| <= |T| * |N|. As T and N are countably infinite, then X must also be countably infinite by the Cantor-Bernstein theorem

Re: A number that can't be calculated

#29

Post by nimih »

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?

What would it mean for BB(n) to "not exist"? Recall that BB(n) is defined in a very concrete way: you take all the Turing machines of size n (which are easily enumerable combinatorial objects), remove ones which do not halt, then take the largest runtime of the ones that are left. Since we can always write down a Turing machine which halts immediately, we know that there's a trivial lower bound for each BB(n), and since the Turing machines are deterministic, we know that any machine that halts must do so in a fixed number of steps. With such a straightforward construction, it's hard to see how such a number could "not exist," at least not without appealing to an ontology somewhat outside of the mainstream (e.g. ultrafinitism).

Re: A number that can't be calculated

#30

Post by kevinventullo »

tshaddox wrote: post #27
alexmolas wrote: post #23

Earlier quoted context omitted.

> it is always possible to compute BB(k) for a specific and arbitrary k but wouldn't this be equivalent to solve the Halting Problem?

No, because the halting problem requires implementing a function that can compute whether any other function halts. It has to work for any possible function you give it. You can, of course, compute whether some functions halt. Two easy ways to do so are to observe that it halts or observe an infinite loop.

Isn’t the crux of the issue that you can’t “observe” an infinite loop?
Post reply on HN