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

11–20 of 80 posts

Re: Why Busy Beaver hunters fear the Antihydra

#11

Post by ameliaquining »

kibwen wrote: post #4

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…

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.)

Re: Why Busy Beaver hunters fear the Antihydra

#12

Post by wat10000 »

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?

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?

Re: Why Busy Beaver hunters fear the Antihydra

#13

Post by A_D_E_P_T »

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?

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‑Löf 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.

Re: Why Busy Beaver hunters fear the Antihydra

#14

Post by altruios »

wat10000 wrote: post #12
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?

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

Re: Why Busy Beaver hunters fear the Antihydra

#15

Post by emtel »

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.

Re: Why Busy Beaver hunters fear the Antihydra

#16

Post by hyghjiyhu »

gbacon wrote: post #7
russdill wrote: post #2

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.

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

Iirc if you change the numerical values of the collatz problem some instances are undecidable.

Re: Why Busy Beaver hunters fear the Antihydra

#17

Post by gowld »

hyghjiyhu wrote: post #16
gbacon wrote: post #7

Earlier quoted context omitted.

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

Iirc if you change the numerical values of the collatz problem some instances are undecidable.

A generalized Collatz problem ((mx + b mod n) instead of 3x+1 in Z) is undecidable.

Re: Why Busy Beaver hunters fear the Antihydra

#18

Post by gowld »

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…

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

Re: Why Busy Beaver hunters fear the Antihydra

#19

Post by baruchel »

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…

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

Re: Why Busy Beaver hunters fear the Antihydra

#20

Post by wat10000 »

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…

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

Post reply on HN