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

61–70 of 79 posts

Re: A number that can't be calculated

#61

Post by gnramires »

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…

> Don't think this article is correct when it says that Omega can't be computed to arbitrary precision, it certainly can be.

It's not computable in this sense: there's no algorithm that given n returns Omega with n bits of precision, for any n. I think this qualifies as saying it cannot be computed to arbitrary precision :)

But I understand your point -- the language here is tricky.

Trying to make things clearer: Every program that does halt can be proven to halt -- simply run the program until it halts, if we assume it halts then you get its proof for free. However, if we make no assumptions a program may run forever, so we cannot know if it halts. I believe Godel's theorems also imply there must be non-halting programs for which no proof that they do not halt exists. This closes a very interesting loophole: you might, instead of just trying to run every program until it halts, to check every proof to see if it is a valid proof that a given program P does not -- if it exists, you will always find it. But because sometimes P does not halt yet no proof exists, this loophole is closed.

As others have mentioned, indeed I believe 'different algorithm for q > k, but such an algorithm does exist' does not pan out in the sense that we could prove the correctness of such algorithms, even though they do exist! :)

Another interesting angle: you can think that, even if you had an "oracle" that gives the "true" halting value (halts or does not halt), the size of a program that decides (by encoding the oracle values somehow) all halting programs up to n must grow with n. In other words, the halting values are incompressible somehow; if it were the case that the growth was bounded, then there would exist some program P that returns the true halting value of any program (false by Turing). This leads to the notion that non-computable numbers are random (or random-like), because they are fundamentally incompressible in a certain way (and you can't, on average, compress a random string).

Edit: minor corrections

Re: A number that can't be calculated

#62

Post by NotYourLawyer »

alexmolas wrote: post #26
NotYourLawyer wrote: post #16

Earlier quoted context omitted.

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.

Yes, that’s my point. The all-knowing oracle could also just tell you whether or not your program halts.

Re: A number that can't be calculated

#63

Post by aaplok »

> since we don’t know Σ(n) we can’t know the exact value of Ω.

Hmmm. Just because you don't know the individual terms of the sequence, it doesn't follow that you don't know their infinite sum. Here's a trivial example: take the sum `(-1)^n Σ(floor(n/2))`. The infinite sum is obviously 0, yet we can't calculate each of the terms, nor many of the partial sums.

Re: A number that can't be calculated

#64

Post by alexmolas »

aaplok wrote: post #63

> since we don’t know Σ(n) we can’t know the exact value of Ω. Hmmm. Just because you don't know the individual terms of the sequence, it doesn't follow that you don't know their infinite sum. Here's a trivial example: take the sum `(-1)^n Σ(floor(n/2))`. The infinite sum is obviously 0, yet we can't calculate each of the terms, nor many of the partial sums.

> Just because you don't know the individual terms of the sequence, it doesn't follow that you don't know their infinite sum

Yes, this is not true in general. But I think it's true for the specific definition of Ω we use in the post.

Re: A number that can't be calculated

#65

Post by aaplok »

alexmolas wrote: post #64
aaplok wrote: post #63

> since we don’t know Σ(n) we can’t know the exact value of Ω. Hmmm. Just because you don't know the individual terms of the sequence, it doesn't follow that you don't know their infinite sum. Here's a trivial example: take the sum `(-1)^n Σ(floor(n/2))`. The infinite sum is obviously 0, yet we can't calculate each of the terms, nor many of the partial sums.

> Just because you don't know the individual terms of the sequence, it doesn't follow that you don't know their infinite sum Yes, this is not true in general. But I think it's true for the specific definition of Ω we use in the post.

Intuitively I'd say you're probably right. But computation theory is full of counter-intuitive results. Your statement might be provable by adapting the argument that Σ(n) is not always computable. Something like computing the sum would require solving some version of the halting problem.

Perhaps add a small edit to your article to highlight that this particular statement isn't to be taken as a mathematical proof?

Re: A number that can't be calculated

#66

Post by gnramires »

gnramires wrote: post #61
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…

> Don't think this article is correct when it says that Omega can't be computed to arbitrary precision, it certainly can be. It's not computable in this sense: there's no algorithm that given n returns Omega with n bits of precision, for any n. I think this qualifies as saying it cannot be computed to arbitrary precision :) But I understand your point -- the language here is tricky. Trying to make things clearer: Eve…

This makes me consider a second loophole: even with, for a given set of axioms, we cannot prove some given P does not halt (Godel's incompleteness theorems). However, that makes us wonder if there can be a procedure that suggests stronger, but still minimal axioms (consistent with say Peano arithmetic or ZFC) and proves them in this new axiomatic basis?

(1) Would this proof be considered acceptable? (or can we devise a system that guarantees found proofs to be acceptable)

(2) Is this procedure feasible?

If anyone has literature on this topic, this is interesting! (an optimistic alternative to incompleteness)

Re: A number that can't be calculated

#67

Post by elijaht »

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…

You don’t need to show a process.

Trivially a non-halting program for any n exists. Also trivially there must be some non-halting program with the highest number of steps.

We can’t necessarily find that program, but there is almost by definition some non halting program with the highest number of steps

Re: A number that can't be calculated

#68

Post by kevinventullo »

kevinventullo wrote: post #41
dllthomas wrote: post #21

Earlier quoted context omitted.

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

Ah, the issue is that one system may be able to prove the correct answer but it remains independent for the other system.

Re: A number that can't be calculated

#69

Post by puffoflogic »

vainguard wrote: post #37
dllthomas wrote: post #21

Earlier quoted context omitted.

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

> BB(k) for a specific k is just a number.

That's not as obvious as you might think. The value of BB(800) is independent of ZFC. So it isn't "just a number" if you're working in ZFC.

Re: A number that can't be calculated

#70

Post by puffoflogic »

elijaht wrote: post #67
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…

You don’t need to show a process. Trivially a non-halting program for any n exists. Also trivially there must be some non-halting program with the highest number of steps. We can’t necessarily find that program, but there is almost by definition some non halting program with the highest number of steps

> Also trivially there must be some non-halting program with the highest number of steps.

That isn't trivial. Whether a given program halts might be independent of ZFC, or of any consistent logical system you might try to use. The question of whether such a program "really" halts is one which might not have an answer. ZFC claims there must be an answer, because LEM, but why should we care what ZFC or first order logic or anything has to say on the matter, if they can't actually tell us whether it halts?

Post reply on HN