Why Busy Beaver hunters fear the Antihydra
benbrubaker.com
benbrubaker.com
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 really is mind bending how fast this function grows.
While the BB function is obviously a well-defined function over the integers, I find it helpful to think of it as a function over qualitatively heterogeneous items—such as stones, bread toasters, mechanical watches, and computers. The key idea is to view the underlying computing devices not as “a little more powerful” than the previous ones, but as fundamentally different kinds of entities.
Either way, the only BB axiom you can add without blowing up ZFC is the correct one.
A similarly fast growing function is the functional busy beaver [3]. Among all 77519927606 closed lambda terms of size <= 49 bits, there is one whose normal form size exceeds the vastly larger Graham's Number [3].
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.
Well is there a best current UPPER bound, or at least a "probvious" one?
I find the question about a probvious upper bound more interesting - There is also not a probvious upper bound on BB(6), as this would require at least some understanding of the high-level behavior of all remaining holdout machines. However, there may soon be a 'probvious' upper bound on the value of BB(3,3) (BB for 3-state, 3-symbol machines). Up to equivalence, there are four remaining machines to decide to find the value of BB(3,3). One is a 'probviously halting' machine which will be the new champion if it halts, and for which probabilistic models of its behavior predict with high probability an exact halting time. One is a 'probviously nonhalting' machine. The two other machines are not well-understood enough to say whether they have any probvious long term behavior, but some suspect that they both 'probviously nonhalt'. If this is true it could be said that a 'probvious' upper bound exists for BB(3,3).
EDIT: For fun I converted it to Rust and expected to see it spew a few million numbers into my terminal, but no, this equivalent loop actually terminates after 15 steps, which is fascinating given that the Turing machine takes 47 million steps:
let mut x = 0;
loop {
x = match x % 3 {
0 => 5 * x + 18,
1 => 5 * x + 22,
_ => break
} / 3;
}
EDIT 2: Of course the article mentions this in the next paragraph, which is what I get for being immediately nerd-sniped.
By not using any math functions except for increment by one?
- “Avoid the Collatz Conjecture at All Costs!” (Math Kook) https://www.youtube.com/watch?v=TxBRcwkRjmc
- “Experienced mathematicians warn up-and-comers to stay away from the Collatz conjecture. It’s a siren song, they say: Fall under its trance and you may never do meaningful work again.” https://www.quantamagazine.org/mathematician-proves-huge-res...
- "Mathematics is not yet ready for such problems [as Collatz].” (Paul Erdős)
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 steps it could make before halting. Similarly, if you knew that all mortals died before age 200, then if Sally lived to be 200, you could conclude that Sally was immortal. So no Turing machine can list the Busy Beaver numbers—for if it could, it could solve the Halting Problem, which we already know is impossible.
But here’s a curious fact. Suppose we could name a number greater than the Nth Busy Beaver number BB(N). Call this number D for dam, since like a beaver dam, it’s a roof for the Busy Beaver below. With D in hand, computing BB(N) itself becomes easy: we just need to simulate all the Turing machines with N rules. The ones that haven’t halted within D steps—the ones that bash through the dam’s roof—never will halt. So we can list exactly which machines halt, and among these, the maximum number of steps that any machine takes before it halts is BB(N).
Conclusion? The sequence of Busy Beaver numbers, BB(1), BB(2), and so on, grows faster than any computable sequence. Faster than exponentials, stacked exponentials, the Ackermann sequence, you name it. Because if a Turing machine could compute a sequence that grows faster than Busy Beaver, then it could use that sequence to obtain the D‘s—the beaver dams. And with those D’s, it could list the Busy Beaver numbers, which (sound familiar?) we already know is impossible. The Busy Beaver sequence is non-computable, solely because it grows stupendously fast—too fast for any computer to keep up with it, even in principle.
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
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.
The key is that we can't prove that your function f grows faster than BB. That makes all the difference.
In the context that Scott Aaronson was using it probably yes as that is necessary for the most straightforward /obvious proof to work.
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.
[0] https://web.archive.org/web/20251027173129/https://benbrubak...
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?
Consider a simpler version, where you flip a coin three times, then four times, then five times, etc., and you stop if you ever get the same side for every flip in a given turn. The probability that you'll stop is equal to 1/4 + 1/8 + 1/16 + ... which is 50%. If you do this forever then you'll eventually see a run of ten trillion heads or tails, but you probably won't see that run before your ten trillionth turn.
So I think the question is, does the anti-hydra sequence ever diverge sufficiently from randomness?
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 - at some point - in an infinite sequence of fair flips is 1, is it not?
The anti-hydra may have a bias, and only if that bias is against the halt condition do we have a case where we can conclude that the anti-hydra does not halt.
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.
This problem is equivalent to a one-dimensional random walk where the terminating condition is reaching a value equal to the number of steps you've taken divided by 3. I'm not quite sure how to calculate the probability of that.
Intuitively, I'd expect this to have a finite probability. The variance grows with sqrt(n), which gets arbitrarily far away from n/3.
Looking at it another way, this should be very similar to the gambler's ruin problem where the gambler is playing against an infinitely rich house and their probability of winning a dollar is 2/3. If the gambler starts with $1 then the probability of ever reaching zero is 1 - (1/3)/(2/3) = 50%. Reference for that formula: https://www.columbia.edu/~ks20/FE-Notes/4700-07-Notes-GR.pdf
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/
That said, empirically and in all current analyses, the Antihydra's parity behaves as if it were roughly fair over long spans (neither a proven odd nor even bias), and the short-range statistics look pseudo-random. Non-halting is overwhelmingly plausible... but a concrete proof seems out of reach.
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.
13122 -> 50/18, 55/42, 539/2, 297/275, 2/55, 2/11
comp h^2 > comp H^2
comp h c > done H
comp > done c^2
done H^2 > done h^3
done H > comp
done > comp
Accumulator: comp h^8
15/6 red [green] > blue [green]
5/2 red > blue
red green
> The same variable cannot be both decremented and incremented in a single instruction (otherwise the fraction representing that instruction would not be in its lowest terms). Therefore each FRACTRAN instruction consumes variables as it tests them.
In the old days we used to just chop wood, and burn it to keep warm. Then sit down and watch the sportsball game on TV to waste time.
People who use this word should be banned from the internet for life.