A number that can't be calculated • Hacker News Board

Re: A number that can't be calculated

#31

Post by Kranar » Tue, Oct 25, 2022, 7:47 PM UTC

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?

If you recall from predicate logic, these two statements are not the same:

1) For all Turing Machines A, there exists a Turing Machine M such M can compute whether A halts.

2) There exists a Turing Machine M such that for all Turing Machines A, M can compute whether A halts.

Statement 1 is true, statement 2 is false.

You can apply a similar reasoning to BB(n) or your notion of Omega. For any particular choice of n, there is an algorithm that can compute BB(n) and similarly for any arbitrary precision p, there is an algorithm that can compute Omega up to that precision.

None of this is to be taken that there exists an algorithm that can compute BB(n) for all n, or that there exists an algorithm that can compute Omega up to precision p for all p.

Re: A number that can't be calculated

#32

Post by alexmolas » Tue, Oct 25, 2022, 7:47 PM UTC

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.

But if you know BB(n) for any n then you can just make run a program of length n for BB(n) steps. If after BB(n) steps it hasn't halted you know that the program will loop forever. Since you can do that for any arbitrary program then you could solve the halting problem.

Re: A number that can't be calculated

#33

Post by kotlin2 » Tue, Oct 25, 2022, 7:48 PM UTC

sblom wrote: post #22

kotlin2 wrote: post #13

Earlier quoted context omitted.

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?

I didn’t realize the initial state of the tape was part of the definition of a Turing machine. I was picturing having the same operations applied to different tapes, but that’s not the definition so I’m wrong.

Re: A number that can't be calculated

#34

Post by zokier » Tue, Oct 25, 2022, 7:48 PM UTC

I feel the article is mixing up S(n) (max number of steps) and Σ(n) (max number of 1s written), going by the wikipedia article of BB https://en.wikipedia.org/wiki/Busy_beaver

Notably the list of BB numbers in the article matches the values of S(n) in wikipedia instead of Σ(n). Also this sentence makes more sense if you replace Σ(n) with S(n)

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

Re: A number that can't be calculated

#35

Post by tromp » Tue, Oct 25, 2022, 7:50 PM UTC

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. This is a very subtle detail.

That's not subtle at all. Any finite number or string can be computed by a program consisting of a single very long print statement.

Re: A number that can't be calculated

#36

Post by opportune » Tue, Oct 25, 2022, 7:50 PM UTC

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…

Ah, I wrote the same proof above. I agree this is a much simpler way of proving the existence and size of the uncomputible numbers. The busy beavers problem is just an example of an interesting case

Re: A number that can't be calculated

#37

Post by vainguard » Tue, Oct 25, 2022, 7:52 PM UTC

dllthomas wrote: post #21

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?

BB(k) for a specific k is just a number. Ao just write it to the output. Proofing correctness is different from „computing“ and not required here.

Re: A number that can't be calculated

#38

Post by alexmolas » Tue, Oct 25, 2022, 7:55 PM UTC

Kranar wrote: post #31

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?

If you recall from predicate logic, these two statements are not the same: 1) For all Turing Machines A, there exists a Turing Machine M such M can compute whether A halts. 2) There exists a Turing Machine M such that for all Turing Machines A, M can compute whether A halts. Statement 1 is true, statement 2 is false. You can apply a similar reasoning to BB(n) or your notion of Omega. For any particular choice of n, t…

But imagine that we could compute BB(n) for any n, even if we need to use a different algorithm for each n. Then, we could build the mapping n -> BB(n). But the existence of this mapping is forbidden by the unsolvability of the Halting Problem, isn't it?

Re: A number that can't be calculated

#39

Post by kotlin2 » Tue, Oct 25, 2022, 7:55 PM UTC

nimih wrote: post #29

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

In the proof you just provided, you have a step "remove ones which do not halt". By which process do you do that? By the halting-problem, you can't actually make that selection. This ties back into the fact that BB(n) is not computable for all n. I guess what I'm looking for is a proof that the number exists without violating the halting problem. Intuitively, we feel BB(n) should exist because there are finite turing machines with n states. But I'm not sure how to express that rigorously. Or maybe relying on a solution to the halting problem doesn't matter in terms of a proof.

Re: A number that can't be calculated

#40

Post by WhitneyLand » Tue, Oct 25, 2022, 7:56 PM UTC

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…

Nice observation. Unless you’re missing something that seems to kind of shoot down the main point.

The post and it’s analysis are still interesting, but it should probably be updated else a lot of people might take away this key point into their memory as they think about computability.