[HN Gopher] Why Busy Beaver hunters fear the Antihydra
___________________________________________________________________
Why Busy Beaver hunters fear the Antihydra
Author : Bogdanp
Score : 116 points
Date : 2025-10-27 16:56 UTC (6 hours ago)
(HTM) web link (benbrubaker.com)
(TXT) w3m dump (benbrubaker.com)
| russdill wrote:
| TLDR; As BB(n) gets larger, they can encode more random walk
| style problems that have a stop condition related to the position
| of the random walk. Proving that such a condition is unlikely may
| be easy, but proving it never occurs is very difficult.
| gbacon wrote:
| Way worse than just very difficult:
|
| - "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 Erdos)
| hyghjiyhu wrote:
| Iirc if you change the numerical values of the collatz
| problem some instances are undecidable.
| gowld wrote:
| A _generalized_ Collatz problem ((mx + b mod n) instead of
| 3x+1 in Z) is undecidable.
| gbacon wrote:
| 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 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._
|
| https://www.scottaaronson.com/writings/bignumbers.html
| _alternator_ wrote:
| 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
| pmb wrote:
| 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.
| _alternator_ wrote:
| This approach leaves open the possibility that f(x) =
| BB(p+d) right?
| gbacon wrote:
| 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.
| KalMann wrote:
| 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.
| _alternator_ wrote:
| 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.
| kibwen wrote:
| Despite all the reporting on BB(5) I had never seen anyone convey
| that equivalent high-level formulation from 1993, that's very
| cool!
|
| 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; }
|
| OEIS link: https://oeis.org/A386909
|
| EDIT 2: Of course the article mentions this in the next
| paragraph, which is what I get for being immediately nerd-sniped.
| ameliaquining wrote:
| This is because your Rust program represents the numbers in
| binary, while the BB(5) champion Turing machine represents them
| in unary. And unary arithmetic is exponentially slower than
| place-value arithmetic, which is why we invented the latter.
| (There are other inefficiencies in the Turing machine, but
| that's the big conceptual one.)
| fijiaarone wrote:
| Is this like SETI@home, Bitcoin, and Ai code generation?
|
| 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.
| ameliaquining wrote:
| No, it's not a distributed-computing thing; raw compute isn't
| the bottleneck. (That would only help if there were a need to
| check many machines that halt after a tractable-but-nontrivial
| number of steps; that's a narrow sweet spot, given the
| superexponential nature of the problem, and few machines of
| interest are believed to be in it.) Rather, it's a
| collaboration of human (mostly amateur) mathematicians chipping
| away at different parts of the problem.
| MarcelOlsz wrote:
| If it's not loading for anyone else [0]
|
| [0]
| https://web.archive.org/web/20251027173129/https://benbrubak...
| CobrastanJorji wrote:
| That was a really well written article. I think even somebody who
| had never heard of a Turing Machine could probably have gotten a
| pretty reasonable quick understanding of roughly what BB(5) and
| BB(6) are and how the Antihydra works and its greater
| mathematical/historical context. That's hard to do, good job!
| altruios wrote:
| 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?
| wat10000 wrote:
| 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 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?
| altruios wrote:
| > 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 - 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.
| gowld wrote:
| > 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_.
| LegionMammal978 wrote:
| 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
| wat10000 wrote:
| 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 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
| LegionMammal978 wrote:
| 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
| 7373737373 wrote:
| 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/
| A_D_E_P_T wrote:
| It is by definition _not_ random. The Antihydra is generated by
| a fixed computable map, so it is compressible and would fail
| some effective statistical tests. You can 't get true
| randomness via a deterministic algorithm; any computable
| infinite sequence fails Martin-Lof randomness.
|
| 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.
| LegionMammal978 wrote:
| 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
| emtel wrote:
| 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 really is mind bending how fast this function grows.
| baruchel wrote:
| > 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.
| henry2023 wrote:
| One of the curiosities about this function is that computing
| BB(748) is independent of ZFC.
|
| https://scottaaronson.blog/?p=4916
| tromp wrote:
| 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 <= 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.
|
| [1] https://oeis.org/A107668
|
| [2] https://oeis.org/A333479
|
| [3] https://en.wikipedia.org/wiki/Graham%27s_number
___________________________________________________________________
(page generated 2025-10-27 23:00 UTC)