10 ms·

Why Busy Beaver hunters fear the Antihydra

238 points by Bogdanp 1y ago

russdill 1y ago
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 1y ago
  Way worse than just very difficult: - “Avoid the Collatz Conjecture at All Costs!” (Math Kook) https://www.youtube.com/watch?v=TxBRcwkRjmc 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-result-on-dangerous-problem-20191211/ https://www.quantamagazine.org/mathematician-proves-huge-res... - "Mathematics is not yet ready for such problems [as Collatz].” (Paul Erdős)
  - hyghjiyhu 1y ago
    Iirc if you change the numerical values of the collatz problem some instances are undecidable.
    - gowld 1y ago
      A generalized Collatz problem ((mx + b mod n) instead of 3x+1 in Z) is undecidable.
gbacon 1y ago
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 https://www.scottaaronson.com/writings/bignumbers.html
- _alternator_ 1y ago
  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 1y ago
    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_ 1y ago
      This approach leaves open the possibility that f(x) = BB(p+d) right?
      - linschn 1y ago
        No, because f is assumed to be computable from the start, which BB is not (otherwise it could be used as a subroutine in a program that solves the halting problem).
  - gbacon 1y ago
    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 1y ago
    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.
kibwen 1y ago
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 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 1y ago
  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.)
  - achierius 1y ago
    What else comes to mind in terms of inefficiencies? I can think of quite a few but you seem to have deeper insight as to their ranking so I'm curious as to your thoughts.
  - tgv 1y ago
    Nitpicking: just as TMs can use binary or decimal arithmetic, so could Rust programs use unary. It's not an inefficiency in TMs per se, but I can see how it would help a TM to become a BB champion.
    - rini17 1y ago
      > could Rust programs use unary By not using any math functions except for increment by one?
      - 1y ago
fijiaarone 1y ago
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 1y ago
  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.
- weregiraffe 1y ago
  >sportsball People who use this word should be banned from the internet for life.
MarcelOlsz 1y ago
If it's not loading for anyone else [0] [0] https://web.archive.org/web/20251027173129/https://benbrubaker.com/why-busy-beaver-hunters-fear-the-antihydra/ https://web.archive.org/web/20251027173129/https://benbrubak...
CobrastanJorji 1y ago
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 1y ago
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 1y ago
  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 1y ago
    > 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 1y ago
      > 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.
emtel 1y ago
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 1y ago
  > 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 1y ago
  One of the curiosities about this function is that computing BB(748) is independent of ZFC. https://scottaaronson.blog/?p=4916 https://scottaaronson.blog/?p=4916
  - Sniffnoy 1y ago
    The record's been lowered since then, I should note. At least down into the 600s, I've seen claims of down in the 400s. But I haven't really kept up with this.
    - srcreigh 1y ago
      Link https://wiki.bbchallenge.org/wiki/Independence_from_ZFC https://wiki.bbchallenge.org/wiki/Independence_from_ZFC
      - Sniffnoy 1y ago
        Thank you!
entaloneralie 1y ago
Immediately implements the Antihydra in Fractran 13122 -> 50/18, 55/42, 539/2, 297/275, 2/55, 2/11
- sligocki 1y ago
  50/18 reduces to 25/9 right?
  - sligocki 1y ago
    And 297/275 to 27/25?
  - entaloneralie 11mo ago
    Conway's Fractran traditionally compares the accumulator against reduced fractions, but computationally-speaking, getting to the gcd of a fraction does little more than getting rid of otherwise valuable information used during comparison to match against a restricted set of fractions. The support for catalysts, symbols found on both sides of a rewrite rule, makes for a simpler and faster implementation. 15/6 red [green] > blue [green] 5/2 red > blue red green These two fractions are not equal and reducing the first into the second, eliminates the capability to match against it only when the catalyst green is present in the accumulator.
    - sligocki 11mo ago
      I see, so you are using a different model for computation that does not use rational numbers, but instead pairs of integers. From a computational point of view, that makes a lot of sense, disallowing catalysts is quite annoying, but I would not call this Fractran, instead I would call it something like a prioritized chemical reaction network or something like this. The wikipedia article explicitly states: > 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.
      - 11mo ago

238 points by Bogdanp 1y ago

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 1y ago
Way worse than just very difficult: - “Avoid the Collatz Conjecture at All Costs!” (Math Kook) https://www.youtube.com/watch?v=TxBRcwkRjmc 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-result-on-dangerous-problem-20191211/ https://www.quantamagazine.org/mathematician-proves-huge-res... - "Mathematics is not yet ready for such problems [as Collatz].” (Paul Erdős)
- hyghjiyhu 1y ago
  Iirc if you change the numerical values of the collatz problem some instances are undecidable.
  - gowld 1y ago
    A generalized Collatz problem ((mx + b mod n) instead of 3x+1 in Z) is undecidable.

gbacon 1y ago

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 https://www.scottaaronson.com/writings/bignumbers.html

_alternator_ 1y ago
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 1y ago
  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_ 1y ago
    This approach leaves open the possibility that f(x) = BB(p+d) right?
    - linschn 1y ago
      No, because f is assumed to be computable from the start, which BB is not (otherwise it could be used as a subroutine in a program that solves the halting problem).
- gbacon 1y ago
  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 1y ago
  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.

kibwen 1y ago

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 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 1y ago
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.)
- achierius 1y ago
  What else comes to mind in terms of inefficiencies? I can think of quite a few but you seem to have deeper insight as to their ranking so I'm curious as to your thoughts.
- tgv 1y ago
  Nitpicking: just as TMs can use binary or decimal arithmetic, so could Rust programs use unary. It's not an inefficiency in TMs per se, but I can see how it would help a TM to become a BB champion.
  - rini17 1y ago
    > could Rust programs use unary By not using any math functions except for increment by one?
    - 1y ago

fijiaarone 1y ago

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 1y ago
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.
weregiraffe 1y ago
>sportsball People who use this word should be banned from the internet for life.

MarcelOlsz 1y ago

If it's not loading for anyone else [0] [0] https://web.archive.org/web/20251027173129/https://benbrubaker.com/why-busy-beaver-hunters-fear-the-antihydra/ https://web.archive.org/web/20251027173129/https://benbrubak...

CobrastanJorji 1y ago

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 1y ago

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 1y ago
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 1y ago
  > 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 1y ago
    > 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.

emtel 1y ago

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 1y ago
> 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 1y ago
One of the curiosities about this function is that computing BB(748) is independent of ZFC. https://scottaaronson.blog/?p=4916 https://scottaaronson.blog/?p=4916
- Sniffnoy 1y ago
  The record's been lowered since then, I should note. At least down into the 600s, I've seen claims of down in the 400s. But I haven't really kept up with this.
  - srcreigh 1y ago
    Link https://wiki.bbchallenge.org/wiki/Independence_from_ZFC https://wiki.bbchallenge.org/wiki/Independence_from_ZFC
    - Sniffnoy 1y ago
      Thank you!

entaloneralie 1y ago

Immediately implements the Antihydra in Fractran 13122 -> 50/18, 55/42, 539/2, 297/275, 2/55, 2/11

sligocki 1y ago
50/18 reduces to 25/9 right?
- sligocki 1y ago
  And 297/275 to 27/25?
- entaloneralie 11mo ago
  Conway's Fractran traditionally compares the accumulator against reduced fractions, but computationally-speaking, getting to the gcd of a fraction does little more than getting rid of otherwise valuable information used during comparison to match against a restricted set of fractions. The support for catalysts, symbols found on both sides of a rewrite rule, makes for a simpler and faster implementation. 15/6 red [green] > blue [green] 5/2 red > blue red green These two fractions are not equal and reducing the first into the second, eliminates the capability to match against it only when the catalyst green is present in the accumulator.
  - sligocki 11mo ago
    I see, so you are using a different model for computation that does not use rational numbers, but instead pairs of integers. From a computational point of view, that makes a lot of sense, disallowing catalysts is quite annoying, but I would not call this Fractran, instead I would call it something like a prioritized chemical reaction network or something like this. The wikipedia article explicitly states: > 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.
    - 11mo ago