Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Why Busy Beaver hunters fear the Antihydra

benbrubaker.com

Post reply on HN
Print view View original

31–40 of 80 posts

Re: Why Busy Beaver hunters fear the Antihydra

#31

Post by LegionMammal978 »

gowld wrote: post #18
altruios wrote: post #14

Earlier quoted context omitted.

> As the sequence as a whole gets larger, the run length needed to end it also gets longer, and thus the probability gets smaller. The result should be something like a geometric sequence with a finite sum. This is true. But it would still halt. Infinity is weird like that. To be clear, I mean the sequence of coin flips where the total value of heads/tails is 2:1. The probability of having a 2:1 ratio of heads/tails…

> But it would still halt. Infinity is weird like that What are you tring to say? > The probability of having a 2:1 ratio of heads/tails - at some point - in an infinite sequence of fair flips is 1, is it not? Yes, but "probability = 1" absolutely does not mean "will happen eventually" in pure mathematics. Infinity is weird like that .

The probability is less than 1, and in fact it exponentially goes to 0, since the halting condition can be modeled as a biased random walk [0].

[0] https://wiki.bbchallenge.org/wiki/Antihydra#Trajectory

Re: Why Busy Beaver hunters fear the Antihydra

#32

Post by _alternator_ »

KalMann wrote: post #28
_alternator_ wrote: post #21

Earlier quoted context omitted.

Ok, I read this post quite a while ago and something about the reasoning bothered me then, and it still bothers me now. In short, my read is that the argument does not rule out that there is a computable function that grows faster than BB(N), but rather it shows that it is impossible to prove or “decide” whether a given computable function grows faster than BB(N). Maybe this is equivalent to the conclusion stated? Am…

I think Scott's reasoning is correct in the end. If you suppose you had a computable function f(N) such that f(N) is always greater than BB(N). Then you could exploit the function f to solve the halting problem. Given a program of length N, run the program for f(N) steps. If it halts within that time, you know it's a halting program. If it doesn't halt within that time you know it will never halt.

Yes, this I understand. I agree that it is impossible to “prove” that a computable function f(N) is always greater than BB(N).

My concern is that the argument leaves open the possibility of a larger computable function, even if it would be impossible to demonstrate that it is in fact larger for all N.

I’m sure that this possibility is somehow foreclosed (that is, I’m not trying to say that the claim is wrong, just that I think there is a case that isn’t covered by the argument). But I don’t quite see it.

Re: Why Busy Beaver hunters fear the Antihydra

#33

Post by _alternator_ »

pmb wrote: post #22
_alternator_ wrote: post #21

Earlier quoted context omitted.

Ok, I read this post quite a while ago and something about the reasoning bothered me then, and it still bothers me now. In short, my read is that the argument does not rule out that there is a computable function that grows faster than BB(N), but rather it shows that it is impossible to prove or “decide” whether a given computable function grows faster than BB(N). Maybe this is equivalent to the conclusion stated? Am…

Any computable function f on one variable x has a program. That function is a program of size p. The input x also has a data size d. BB(p+d) >= f(x), by definition, for all f and x. If you think you might have a (function, input) pair (and corresponding (program, data) pair) for which this is not true, see the previous sentence.

This approach leaves open the possibility that f(x) = BB(p+d) right?

Re: Why Busy Beaver hunters fear the Antihydra

#34

Post by jcranmer »

_alternator_ wrote: post #21
gbacon wrote: post #3

Why we care about Busy Beaver numbers, from “Who Can Name the Bigger Number?” by Scott Aaronson: Now, suppose we knew the Nth Busy Beaver number, which we’ll call BB(N). Then we could decide whether any Turing machine with N rules halts on a blank tape. We’d just have to run the machine: if it halts, fine; but if it doesn’t halt within BB(N) steps, then we know it never will halt, since BB(N) is the maximum number of…

Ok, I read this post quite a while ago and something about the reasoning bothered me then, and it still bothers me now. In short, my read is that the argument does not rule out that there is a computable function that grows faster than BB(N), but rather it shows that it is impossible to prove or “decide” whether a given computable function grows faster than BB(N). Maybe this is equivalent to the conclusion stated? Am…

It is definitely way too easy to accidentally confuse "x is true" and "x is proven to be true" on topics of undecidability, and this is one of those times where the answer is in fact obvious, but it takes you 15 minutes to realize that it's obvious.

The halting problem is uncomputable (by diagonalization)--that is no computable function can solve the halting problem, rather than the weaker statement that we cannot assert that "this" function solves it. As a result, if somebody asserts a function that purports to solve the halting problem, then we can definitively say that either it isn't computable, or the thing it solves isn't the halting problem.

For the Busy Beaver function, it's obvious that the resulting program (if it existed) would solve the halting problem, so clearly it's not a computable function, and analyzing what part of it isn't computable leads you to the Busy Beaver as the only option.

For the D(N) function... well, since we assume D(N) ≥ BB(N), D(N) is still an upper bound on the number of steps a halting TM could run, so the resulting program using D(N) in lieu of BB(N) would still solve the halting problem, which forces us to conclude that it's not computable.

A different argument that may make more sense is this:

Consider the program "if machine M has not halted after f(sizeof M) steps, print not halt, else print halt." If f is a computable function, then the program is clearly computable. But since no computable program can solve the halting problem, we know that this program cannot either. Therefore, for every computable function f, there must exist some machine M such that M halts only after more than f(sizeof M) steps. In other words, f cannot be an upper bound on the Busy Beaver function.

Re: Why Busy Beaver hunters fear the Antihydra

#35

Post by KalMann »

_alternator_ wrote: post #32
KalMann wrote: post #28

Earlier quoted context omitted.

I think Scott's reasoning is correct in the end. If you suppose you had a computable function f(N) such that f(N) is always greater than BB(N). Then you could exploit the function f to solve the halting problem. Given a program of length N, run the program for f(N) steps. If it halts within that time, you know it's a halting program. If it doesn't halt within that time you know it will never halt.

Yes, this I understand. I agree that it is impossible to “prove” that a computable function f(N) is always greater than BB(N). My concern is that the argument leaves open the possibility of a larger computable function, even if it would be impossible to demonstrate that it is in fact larger for all N. I’m sure that this possibility is somehow foreclosed (that is, I’m not trying to say that the claim is wrong, just th…

No, it has been proven that there exists no turing machine that can solve the halting problem. If we assume that there exists a computable f(N) that is always greater than BB(N) then we can construct a Turing machine that solves the halting problem. Therefore no computable f(N) can exist.

Re: Why Busy Beaver hunters fear the Antihydra

#36

Post by _alternator_ »

jcranmer wrote: post #34
_alternator_ wrote: post #21

Earlier quoted context omitted.

Ok, I read this post quite a while ago and something about the reasoning bothered me then, and it still bothers me now. In short, my read is that the argument does not rule out that there is a computable function that grows faster than BB(N), but rather it shows that it is impossible to prove or “decide” whether a given computable function grows faster than BB(N). Maybe this is equivalent to the conclusion stated? Am…

It is definitely way too easy to accidentally confuse "x is true" and "x is proven to be true" on topics of undecidability, and this is one of those times where the answer is in fact obvious, but it takes you 15 minutes to realize that it's obvious. The halting problem is uncomputable (by diagonalization)--that is no computable function can solve the halting problem, rather than the weaker statement that we cannot as…

This indeed helps me! The key distinction that there is no computable function that solves the halting problem, and whether we can prove it is irrelevant, clarifies the issue. Thanks, I definitely learned something here, even if it’s obvious in retrospect.

Re: Why Busy Beaver hunters fear the Antihydra

#37

Post by throwaway81523 »

emtel wrote: post #15

The best current lower bound for BB(6) is 2↑↑2↑↑2↑↑9 (google "Knuth Up Arrow" if this makes no sense), a number so inconceivably large it gives me the willies. In particular, this means that in going from BB(5) to BB(6), you have already crossed the line where the actual busy beaver TM can no longer be simulated step by step in the lifetime of our universe (or a googol lifetimes of our universe for that matter). It r…

> best current lower bound

Well is there a best current UPPER bound, or at least a "probvious" one?

Re: Why Busy Beaver hunters fear the Antihydra

#38

Post by _alternator_ »

KalMann wrote: post #35
_alternator_ wrote: post #32

Earlier quoted context omitted.

Yes, this I understand. I agree that it is impossible to “prove” that a computable function f(N) is always greater than BB(N). My concern is that the argument leaves open the possibility of a larger computable function, even if it would be impossible to demonstrate that it is in fact larger for all N. I’m sure that this possibility is somehow foreclosed (that is, I’m not trying to say that the claim is wrong, just th…

No, it has been proven that there exists no turing machine that can solve the halting problem. If we assume that there exists a computable f(N) that is always greater than BB(N) then we can construct a Turing machine that solves the halting problem. Therefore no computable f(N) can exist.

This was the key missing part for me; the program can’t exist, whether we can prove it is beside the point. Thanks.

Re: Why Busy Beaver hunters fear the Antihydra

#39

Post by cevi »

throwaway81523 wrote: post #37
emtel wrote: post #15

The best current lower bound for BB(6) is 2↑↑2↑↑2↑↑9 (google "Knuth Up Arrow" if this makes no sense), a number so inconceivably large it gives me the willies. In particular, this means that in going from BB(5) to BB(6), you have already crossed the line where the actual busy beaver TM can no longer be simulated step by step in the lifetime of our universe (or a googol lifetimes of our universe for that matter). It r…

> best current lower bound Well is there a best current UPPER bound, or at least a "probvious" one?

There is no general procedure for computing upper bounds on busy beaver numbers (this can be proven). We haven't even come close to enumerating all of the interesting six-state Turing machines, so right now we don't even have a wild guess for an upper bound on BB(6).

Re: Why Busy Beaver hunters fear the Antihydra

#40

Post by shawnz »

throwaway81523 wrote: post #37
emtel wrote: post #15

The best current lower bound for BB(6) is 2↑↑2↑↑2↑↑9 (google "Knuth Up Arrow" if this makes no sense), a number so inconceivably large it gives me the willies. In particular, this means that in going from BB(5) to BB(6), you have already crossed the line where the actual busy beaver TM can no longer be simulated step by step in the lifetime of our universe (or a googol lifetimes of our universe for that matter). It r…

> best current lower bound Well is there a best current UPPER bound, or at least a "probvious" one?

I think finding an upper bound is basically just as difficult as finding the actual value itself, since both would require proving that all of the programs which run longer than that will run forever. That's why we can say BB(x) grows faster than any computable function. Being able to compute BB(x) algorithmically or any faster growing function would let you solve the halting problem
Post reply on HN