YHK - yet another hacker news clone

BB(10) > Graham's Number

34 points surprisetalk 3 hours ago 16 comments

kekqqq 47 minutes ago | parent

I fail to understand why this is interesting or relevant. The README is very non-human-generated and hard to parse or understand.

amosj 40 minutes ago | parent

Busy beaver numbers are interesting from a computational perspective. They verge in some ways on unknowable, but as this post shows, sometimes there is some knowability, if you will. I've always enjoyed this blog post about them https://www.scottaaronson.com/writings/bignumbers.html

pcstl 39 minutes ago | parent

Since Graham's number is computable, it's an expected result even. The Busy Beaver sequence grows faster than any computable sequence.

im3w1l 25 minutes ago | parent

I feel like I keep failing to wrap my mind around computability in the same way over and over.

Would the following statement be correct?

"There is a turing machine that cannot be proven whether it will terminate or not. For any n we can construct a proof that it will run longer than n. But we cannot construct a proof that for any n it will run longer than n. Due to this particular turing machine, BB(k) cannot be determined for k large enough to admit that turing machine."

cobbal 15 minutes ago | parent

That's correct. In particular, k=8000 is enough (probably much lower)

https://scottaaronson.blog/?p=2725

GolDDranks 10 minutes ago | parent

The current "independent of ZF" upper bound seems to be BB(432).

Source: https://wiki.bbchallenge.org/wiki/Logical_independence

ogogmad 8 minutes ago | parent

Essentially yes, but it's simpler and stronger than that: Any oracle that can output BB(n) given n, can be harnessed to solve the halting problem. Exercise! Try to show that: For any computable integer sequence U, BB(n) > U(n) for all but finitely many exceptions.

hyperpape 15 minutes ago | parent

I don't follow the logic.

Every BB(n) is trivially computable, since any integer is computable. So for every BB(n), there is a computable sequence that grows faster than the BB numbers through n (annoyingly, given the word "grows", this can just be the constant sequence of BB(n) + 1).

So for any given computable number, the fact that it's computable gives no intrinsic reason to believe it's smaller than BB(n) for any particular n.

bonzini 3 minutes ago | parent

No, high enough busy beaver numbers are not computable. They can be defined but there's no way to know what they are.

That is because if you could compute BB(n) for arbitrary n, you could run a Turing machine for BB(n)+1 steps and if it hasn't stopped yet then you know that the input corresponds to a machine that never halts. So it's impossible to compute BB(n) for arbitrary n, because doing so is equivalent to the halting problem.

raincole 11 minutes ago | parent

No, it's not an obvious result. There is a BB(N) > Graham's Number, but in no way N=10 is obvious.

wat10000 5 minutes ago | parent

Would we expect that Graham's number is less than 47,176,870, since BB(5) = 47,176,870?

ogogmad 27 minutes ago | parent

It's code golf played with Turing machines. The game is: Make the smallest Turing machine whose runtime is bigger than Graham's number, but still terminates. The record right now is 10 states. At least 6 states are needed because any Turing machine with at most 5 states, that finishes running, has a runtime of at most 47,176,870, which is less than Graham's number. In summary:

  BB(10) > G > BB(5) = 47,176,870.

socializer 18 minutes ago | parent

It's not "relevant" in any sense, but I think many computer folks are fascinated by busy beaver numbers because it's fairly easy what the numbers mean - it's just a Turing machine with no icky math.

That said, functionally, they're more or less a restatement of the halting problem, essentially "if the halting problem was a sequence of numbers". Also see Godel's incompleteness. A bit mind-blowing that you have sequences of integers you can't "know" (i.e., compute or verify), but that's about it.

People have been working on them for fun, with no chance of any of this being applicable to anything, so throwing AI at it to produce new results seems a bit tone-deaf to me.

chvid 12 minutes ago | parent

Clicking the author name generates this for me:

Too many requests You have exceeded a secondary rate limit.

Please wait a few minutes before you try again; in some cases this may take up to an hour. Signing in may provide a higher rate limit if you are not already signed in.

For more on scraping GitHub and how it may affect your rights, please review our Terms of Service.

Ironic how now normal browsing of GitHub and this AI assisted proof is marked as scraping.