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

51–60 of 80 posts

Re: Why Busy Beaver hunters fear the Antihydra

#51

Post by thaumasiotes »

throwaway81523 wrote: post #46
shawnz wrote: post #40

Earlier quoted context omitted.

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

Sure, but I only asked about the single case x=6.

If you want an unproven-but-almost-certainly-correct upper bound on BB(6), consider BB(12).

Re: Why Busy Beaver hunters fear the Antihydra

#52

Post by linschn »

_alternator_ wrote: post #33
pmb wrote: post #22

Earlier quoted context omitted.

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.

This approach leaves open the possibility that f(x) = BB(p+d) right?

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

Re: Why Busy Beaver hunters fear the Antihydra

#53

Post by cwillu »

red75prime wrote: post #44
henry2023 wrote: post #23

Earlier quoted context omitted.

One of the curiosities about this function is that computing BB(748) is independent of ZFC. https://scottaaronson.blog/?p=4916

In other words, Turing machine creates mathematical reality, which is independent from our assumptions.

No, that's a misconception. If you add BB(748)==‹any N but the correct number›, you get an inconsistent system that will either claim that a machine doesn't halt even though it does (e.g. the real BB champion), or that some machine does halt at N steps, which you can then disprove by enumerating all the turing machines of the relevant number of states for N steps, and showing that no machine halts at that step.

Either way, the only BB axiom you can add without blowing up ZFC is the correct one.

Re: Why Busy Beaver hunters fear the Antihydra

#54

Post by rini17 »

tgv wrote: post #50
ameliaquining wrote: post #11

Earlier quoted context omitted.

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

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.

> could Rust programs use unary

By not using any math functions except for increment by one?

Re: Why Busy Beaver hunters fear the Antihydra

#55

Post by shawnz »

throwaway81523 wrote: post #46
shawnz wrote: post #40

Earlier quoted context omitted.

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

Sure, but I only asked about the single case x=6.

The point stands: the hard part is proving that all the programs with longer runtime than your upper bound will never terminate, and once you've solved that, getting the exact value is just a little extra work

Re: Why Busy Beaver hunters fear the Antihydra

#56

Post by JulianChastain »

rini17 wrote: post #54
tgv wrote: post #50

Earlier quoted context omitted.

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.

> could Rust programs use unary By not using any math functions except for increment by one?

By representing all numbers with lists (or sets). 0 = [] 1 = [True] 2 = [True, True] Etc. Then for example addition becomes appending two lists together

Re: Why Busy Beaver hunters fear the Antihydra

#58

Post by JulianChastain »

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

It seems totally inconceivable to me that you could accurately predict how long until we will know whether BB(7) is greater than Graham's Number.

Re: Why Busy Beaver hunters fear the Antihydra

#59

Post by tromp »

JulianChastain wrote: post #58
tromp wrote: post #30

Earlier quoted context omitted.

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

It seems totally inconceivable to me that you could accurately predict how long until we will know whether BB(7) is greater than Graham's Number.

I do not predict that. We just need the bet to have a time limit because BB(7) will always have holdouts as long as I live. I chose 10 years because I have prior experience with that timeframe [1].

[1] https://senseis.xmp.net/?ShodanGoBet

Re: Why Busy Beaver hunters fear the Antihydra

#60

Post by emtel »

red75prime wrote: post #44
henry2023 wrote: post #23

Earlier quoted context omitted.

One of the curiosities about this function is that computing BB(748) is independent of ZFC. https://scottaaronson.blog/?p=4916

In other words, Turing machine creates mathematical reality, which is independent from our assumptions.

Nope, that’s the crazy thing. busy beaver numbers are simple arithmetical constructions. There is a fact of the matter about each value of BB(n)! We just can’t ever know more than a small handful of them.
Post reply on HN