Why Busy Beaver hunters fear the Antihydra

Post by ted_dunning » Tue, Oct 28, 2025, 3:11 AM UTC

_alternator_ wrote: post #32

KalMann wrote: post #28

Earlier quoted context omitted.

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.

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

Post by red75prime » Tue, Oct 28, 2025, 5:02 AM UTC

henry2023 wrote: post #23

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

Post by throwaway81523 » Tue, Oct 28, 2025, 6:08 AM UTC

shawnz wrote: post #40

throwaway81523 wrote: post #37

Earlier quoted context omitted.

> best current lower bound Well is there a best current UPPER bound, or at least a "probvious" one?

I think finding an upper bound is basically just as difficult as finding the actual value itself, since both would require proving that all of the programs which run longer than that will run forever. That's why we can say BB(x) grows faster than any computable function. Being able to compute BB(x) algorithmically or any faster growing function would let you solve the halting problem

Post by Eliezer » Tue, Oct 28, 2025, 6:59 AM UTC

tromp wrote: post #30

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

Post by tgv » Tue, Oct 28, 2025, 8:32 AM UTC

ameliaquining wrote: post #11

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