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

21–30 of 80 posts

Re: Why Busy Beaver hunters fear the Antihydra

#21

Post by _alternator_ »

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 I missing something obvious? (That sees likely; Scott Aaronson is much better at this than me.)

Edited for clarity

Re: Why Busy Beaver hunters fear the Antihydra

#22

Post by pmb »

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

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.

Re: Why Busy Beaver hunters fear the Antihydra

#23

Post by henry2023 »

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…

One of the curiosities about this function is that computing BB(748) is independent of ZFC.

https://scottaaronson.blog/?p=4916

Re: Why Busy Beaver hunters fear the Antihydra

#24

Post by [deleted] »

altruios wrote: post #9

The Antihydra will halt if: The sequence is (truly/fairly) random in its distribution of mods 1/2. Even fair coins flipped infinitely would - on occasion - have arbitrary long results of heads or tails. So the question becomes, is the anti-hydra sequence 'sufficiently' random?

[deleted]

Re: Why Busy Beaver hunters fear the Antihydra

#25

Post by gbacon »

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

Aaronson’s argument shows by contradiction that a computable upper bound D(N) that grows more rapidly than BB(N) cannot exist because otherwise we’d be able to use it to solve the halting problem.

Re: Why Busy Beaver hunters fear the Antihydra

#26

Post by 7373737373 »

altruios wrote: post #14
wat10000 wrote: post #12

Earlier quoted context omitted.

I don't think a truly random sequence would necessarily halt under these rules. It's not enough to have arbitrarily long runs. 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. Consider a simpler version, where you flip a coin three times, then four times, then fiv…

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

Even if an event has probability 1 it is not inevitable, conversely probability 0 does not imply its impossibility.

For example, randomly picking the number 0.5 out of the interval of real numbers [0,1] has probability 0, and yet it might happen. The probability of picking an irrational number instead was 1 (because almost all real numbers are irrational), but that didn't happen.

Even if you consider a countably infinite number of events, as with the coinflip example, it might just happen that the coin flips to one side forever.

Since the machines under consideration just represent one specific sequence of events, probabilistic arguments may be misleading.

Relevant xkcd: https://xkcd.com/221/

Re: Why Busy Beaver hunters fear the Antihydra

#27

Post by LegionMammal978 »

altruios wrote: post #9

The Antihydra will halt if: The sequence is (truly/fairly) random in its distribution of mods 1/2. Even fair coins flipped infinitely would - on occasion - have arbitrary long results of heads or tails. So the question becomes, is the anti-hydra sequence 'sufficiently' random?

The peak run lengths of evens/odds 'should' go to infinity, but these runs become a smaller and smaller component of the overall average, so that it is expected to approach the long-term 50% regardless.

In other words, an unbiased random walk should almost surely return to the origin, but a biased random walk will fail to return to the origin with nonzero probability. This can be considered a biased random walk [0], since the halting condition linearly moves further and further away from the expected value of the 50/50 walk.

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

Re: Why Busy Beaver hunters fear the Antihydra

#28

Post by KalMann »

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

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.

Re: Why Busy Beaver hunters fear the Antihydra

#29

Post by LegionMammal978 »

wat10000 wrote: post #20
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…

No, I don't think it's 1. The weirdness of infinity can go both ways. A classic example being that a random walk on a line or a two-dimensional grid takes you back to your starting point an infinite number of times, but for a three dimensional grid you only return to the start a finite number of times, quite possibly zero. This problem is equivalent to a one-dimensional random walk where the terminating condition is…

You can solve it with a linear recurrence relation [0]: the halting probability from position n is ((sqrt(5)-1)/2)^(n+1), where n is twice the number of odds minus the number of evens. (In fact, this +2/-1 random walk is precisely how the machine implements its termination condition.) The expected value of n is 1/3 the number of iterations. At the end of the longest simulation that has been computed, n is greater than 2^37, so the halting probability is less than 10^(-10^10).

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

Re: Why Busy Beaver hunters fear the Antihydra

#30

Post by tromp »

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…

The BB function does grow mind bendingly fast. The machine running for 2↑↑2↑↑2↑↑9 steps is one of the 4^12*23836540 = 399910780272640 differently behaving 6-state machines [1].

A similarly fast growing function is the functional busy beaver [3]. Among all 77519927606 closed lambda terms of size Several beaver fans believe that BB(7) might exceed Graham's Number as well, which struck me as unlikely enough to offer a $1k bet against it, the outcome of which will be known in under a decade.

[1] https://oeis.org/A107668

[2] https://oeis.org/A333479

[3] https://en.wikipedia.org/wiki/Graham%27s_number

Post reply on HN