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

41–50 of 79 posts

Re: A number that can't be calculated

#41

Post by kevinventullo »

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?

Perhaps you need larger and larger sets of axioms as k increases.

This is fascinating to me, because Turing machines can in principle be manifested as physical objects. It feels like you shouldn’t need axioms if you have the thing sitting in front of you, but on the other hand how else are you supposed to prove something doesn’t halt?

Still, if you have two axiomatic systems that disagree, what does that mean? Surely you can just run the machine in question for a certain number of steps to determine which system is right.

Re: A number that can't be calculated

#42

Post by alexmolas »

zokier wrote: post #34

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

Oh yeah, you're right, I mixed up the terms. I just started learning about this topic and I got excited and wrote the post. I'll fix it ASAP. Thank you very much for spotting it :)

Re: A number that can't be calculated

#43

Post by Kranar »

tromp wrote: post #35
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.

Fair enough, one misconception I always hear from people learning about Godel's incompleteness theorem or the halting problem is that it means there exist algorithms where we can never know if it halts or not. Like there's some limit to math that makes it impossible for us to know whether a particular algorithm just keeps running forever or will eventually stop.

No such algorithm exists, no such example exists because for any particular algorithm it's always possible to determine whether it halts or not (at least in principle). It might not be practical, the proof might be incredibly difficult, but math does not have any kind of intrinsic limitation that prevents us from proving whether a specific algorithm halts.

Re: A number that can't be calculated

#44

Post by gotthetshirt »

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…

No, you cannot compute BB(k) for a given k. https://scottaaronson.blog/?p=2725

Re: A number that can't be calculated

#45

Post by alexmolas »

kotlin2 wrote: post #39
nimih wrote: post #29

Earlier quoted context omitted.

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

The Halting Problem forbids you to build an algorithm that proves if a generic problem halts or not. This doesn't forbid you to check if a specific algorithm halts or not. For example, you know that the specific program `print("Hello World")` halts. So you can remove the ones that do not halt by inspecting them one by one and developing a specific algorithm for each one that determines if it halts or not.

Re: A number that can't be calculated

#46

Post by Kranar »

gotthetshirt wrote: post #44
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…

No, you cannot compute BB(k) for a given k. https://scottaaronson.blog/?p=2725

I love that article but that does not state what you are claiming it does. What that states is that there exists a k (whose upper bound is 8000) whose solution is independent of ZFC. That does not mean it can't be computed.

In the very comment section of that blog post someone brings this issue up, and Scott himself says:

"Yes, fine, you’re right, there’s not a single “boundary between the knowable and the knowable.” What there is, is more like a concentric series of boundaries, with signs warning you that as you proceed outward you need to take on bolder and bolder axioms (which might be large-cardinal axioms and might be something else). What’s significant about going beyond ZFC is just that, by that point, you’ve clearly passed the first of those boundaries."

Re: A number that can't be calculated

#47

Post by kotlin2 »

alexmolas wrote: post #45
kotlin2 wrote: post #39

Earlier quoted context omitted.

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…

The Halting Problem forbids you to build an algorithm that proves if a generic problem halts or not. This doesn't forbid you to check if a specific algorithm halts or not. For example, you know that the specific program `print("Hello World")` halts. So you can remove the ones that do not halt by inspecting them one by one and developing a specific algorithm for each one that determines if it halts or not.

If you could inspect any Turing machine and devise a specific algorithm that determines if it halts, then you yourself would be an algorithm that solves the generic halting problem.

Re: A number that can't be calculated

#48

Post by morelisp »

alexmolas wrote: post #38
Kranar wrote: post #31

Earlier quoted context omitted.

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?

> But imagine that we could compute BB(n) for any n, even if we need to use a different algorithm for each n.

This is itself uncomputable; therefore

> Then, we could build the mapping n -> BB(n).

This mapping is not computable.

Edit as I'm rate-limited:

What I mean is, informally, the incomputability of the algorithm to select the correct algorithm to compute BB(n) is sufficient to make that mapping uncomputable.

However, that does not mean that an algorithm to compute BB(n) for a specific n does not exist. Trivially, it does; "output BB(n)". It's just very uninteresting! What you're asking for, rather, is more like "an algorithm to prove BB(n)=x", which is a closely related but distinct problem.

Re: A number that can't be calculated

#49

Post by lmkg »

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 not true.

There is a number N where BB(n) is incomputable for all n > N. This fact tie back to being able to solve the Halting Problem, in various clever ways if you knew BB(n).

The value of BB(744) depends on whether the Riemann Hypothesis is true or false. This means that it cannot be computed in general. The Riemann Hypothesis being either true or false are both consistent with ZFC. The value of BB(748) depends on the self-consistency of ZFC.

Re: A number that can't be calculated

#50

Post by morelisp »

kevinventullo wrote: post #30
tshaddox wrote: post #27

Earlier quoted context omitted.

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?

No, the crux of the issue is that you can't observe every infinite loop.
Post reply on HN