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

51–60 of 79 posts

Re: A number that can't be calculated

#51

Post by morelisp »

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…

> By which process do you do that?

It's not a constructive proof, you don't need to give a process.

Re: A number that can't be calculated

#52

Post by [deleted] »

lmkg wrote: post #49
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 ei…

[deleted]

Re: A number that can't be calculated

#53

Post by dvt »

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.

It is not. There are a few proofs, most notably the fact that you'd have to solve the halting problem to find BB(k) for an arbitrary k. But the more interesting proof is when looking at the growth of the number of states required for larger BB(k)'s. You end up with a pretty cool contradiction[1] by constructing a very special Turing machine.

[1] http://www.coopersnotes.net/docs/langmach/CHAP10%20Busy%20Be... (pg. 403)

Re: A number that can't be calculated

#54

Post by [deleted] »

morelisp wrote: post #48
alexmolas wrote: post #38

Earlier quoted context omitted.

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

[deleted]

Re: A number that can't be calculated

#55

Post by kotlin2 »

morelisp wrote: post #51
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…

> By which process do you do that? It's not a constructive proof, you don't need to give a process.

That's true. The part that "feels" weird is that there is no algorithm that could perform the separation into halting / non-halting subsets. Choosing elements from a set based on uncomputable properties almost feels like an extension of the axiom of choice.

Re: A number that can't be calculated

#56

Post by alexmolas »

kotlin2 wrote: post #47
alexmolas wrote: post #45

Earlier quoted context omitted.

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.

no, because you can build an algorithm that fools the algorithm that solves the generic halting problem. I wrote a "proof" of that in my blog [1]

[1]: https://www.amolas.dev/blog/halting-problem/

Re: A number that can't be calculated

#57

Post by Kranar »

dvt wrote: post #53
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. It is not. There are a few proofs, most notably the fact that you'd have to solve the halting problem to find BB(k) for an arbitrary k. But the more interesting proof is when looking at the growth of the number of states required for larger BB(k)'s. You end up with a pretty cool contradiction[1] by constructing a very special Turing machine. [1]…

I feel like even after I point out the subtlety, people just read right past it and still don't recognize it.

Nothing in your source contradicts anything I've said.

Re: A number that can't be calculated

#58

Post by lcuff »

The code he gives, and the explanation of the busy beaver problem, strikes me as pretty poorly explained. If I didn't already know about the busy beaver problem, I don't think I could get it from this explanation.

Re: A number that can't be calculated

#59

Post by alexmolas »

lcuff wrote: post #58

The code he gives, and the explanation of the busy beaver problem, strikes me as pretty poorly explained. If I didn't already know about the busy beaver problem, I don't think I could get it from this explanation.

hi, author here! Thanks for your comment. Which where the parts that are poorly explained? I would love to get some feedback from you. I just started learning about computability theory, so maybe I explained some concepts wrong. Also, english is not my first language, so perhaps I lost something in translation.

Thanks :)

Re: A number that can't be calculated

#60

Post by kotlin2 »

alexmolas wrote: post #56
kotlin2 wrote: post #47

Earlier quoted context omitted.

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.

no, because you can build an algorithm that fools the algorithm that solves the generic halting problem. I wrote a "proof" of that in my blog [1] [1]: https://www.amolas.dev/blog/halting-problem/

Exactly. So your claim that:

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

Is impossible. You can’t, in general, inspect Turing machines one-by-one to determine if they halt.

Post reply on HN