Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

BusyBeaver(6) Is Quite Large

scottaaronson.blog

Post reply on HN
Print view View original

41–50 of 232 posts

Re: BusyBeaver(6) Is Quite Large

#41

Post by Dylan16807 »

jerf wrote: post #19
Straw wrote: post #13

Earlier quoted context omitted.

The category error is in thinking that BB(748) is in fact, a number. It's merely a mathematical concept.

No, that's one of the freakiest things about things like the Busy Beaver function. There is an exact integer that BB(748) defines. You can add one to it and then it would no longer be that number anymore. If you are refering to the idea that nothing that can't exist in the real universe "really exists", then the "Busy Beaver" portion of that idea is extraneous, as 100% of integers can't exist in the real universe, an…

> that's one of the freakiest things about things like the Busy Beaver function

Every sentence ever spoken and every view ever looked at is also a number. It's not a freaky thing about "things like" busy beaver, it's a freaky thing about the concept of information.

But even though everything is a number, saying "it's crazy that a number can be X" is usually someone making a mistake, using the everyday concept of numbers in their head. If you replace "a number" with "some text and code and data", people wouldn't say it's surprising that "some text and code and data" can be unprovable in ZFC.

Technically a photograph is a number, but primarily it's something else. BB(748) is the same, technically a number but primarily it's a series of detailed computer calculations.

Re: BusyBeaver(6) Is Quite Large

#42

Post by charcircuit »

>imagine you had 10,000,000_10 grains of sand. Then you could … well, uh … you could fill about 10,000,000_10 copies of the observable universe with that sand. I hope that helps people visualize it!

People can't visualize numbers that big. There's more ways to express numbers than just counting them. For example a single grain of sand has infinite states it can be in (there are an infinite amount of real numbers), so you could say a single grain of sand could represent BB(6). Combinations can grow exponentially, so that may be something useful to try and express it.

Re: BusyBeaver(6) Is Quite Large

#43

Post by ajkjk »

dtech wrote: post #24
ajkjk wrote: post #20

Earlier quoted context omitted.

Not an expert, but I've read about this a bit because it bothered me also and I think this is the answer: Most of these 'uncomputable' problems are uncomputable in the sense of the halting problem: you can write down an algorithm that should compute them, but it might never halt. That's the sense in which BB(x) is uncomputable: you won't know if you're done ever, because you can't distinguish a machine that never hal…

I am also not an expert, but this does not sound right to me. Godel's incompleteness theorem shows that there are certain things that cannot be proven. Being independent of ZFC means that something is such a case. So BB(643) being independent of ZFC means that we cannot prove or disprove that a certain number is BB(643). Aka we don't have the math to know for certain.

Yeah, but the vexing part is "how can that be true for e.g. N=643 but not N=642"? What happens at whatever number it starts true at?

Incidentally, Gödel's theorem eventually comes down to a halting-like argument as well (well, a diagonal argument). There is a presentation of it that is in like less than one page in terms of the halting problem---all of the Gödel-numbering stuff is essentially an antiquated proof. I remember seeing this in a great paper which I can't find now, but it's also mentioned as an aside in this blog post: https://scottaaronson.blog/?p=710

wait jk I found it: https://arxiv.org/abs/1909.04569

Re: BusyBeaver(6) Is Quite Large

#44

Post by refulgentis »

moralestapia wrote: post #27
NooneAtAll3 wrote: post #22

If you want to learn about actual Busy Beaver results, I suggest reading https://www.sligocki.com/ instead Unlike Aaronson, he actually is on the forefront of Busy Beaver research, and is one of the people behind the https://bbchallenge.org website

>Unlike Aaronson, he actually is on the forefront of Busy Beaver research [...] Extremely bad ad hominem , I enjoyed Aaronson's read, nothing wrong with it.

Gently, seconding peer: that is not ad hominem :)

Colloquially, I understand it's easy to think it means "saying something about someone that could be interpreted negatively" because that's the context it is read in it when it is used.

The meaning is saying a logical argument is incorrect because of who wrote the argument.

Re: BusyBeaver(6) Is Quite Large

#45

Post by refulgentis »

lupire wrote: post #35
NooneAtAll3 wrote: post #22

If you want to learn about actual Busy Beaver results, I suggest reading https://www.sligocki.com/ instead Unlike Aaronson, he actually is on the forefront of Busy Beaver research, and is one of the people behind the https://bbchallenge.org website

https://www.sligocki.com/ hasn't posted since April, and the very first link on that blog is a link to... Scott Aaronson.

Could I bother you for some more info?

I spent 5 minutes trying to verify any link in the post above links to Scott Aaronson, or mentions him, and found nothing. :\ (both the siglocki, and when I found nothing there, the busy beaver site)

Re: BusyBeaver(6) Is Quite Large

#46

Post by gylterud »

Straw wrote: post #13
Scarblac wrote: post #4

It boggles my mind that a number (an uncomputable number, granted) like BB(748) can be "independent of ZFC". It feels like a category error or something.

The category error is in thinking that BB(748) is in fact, a number. It's merely a mathematical concept.

A constructive mathematician would indeed deny that BB(748) is a well defined number. One could define it as a predicate on natural numbers, but lest we find a contradiction in ZFC we cannot hope to constructively prove that it holds for any number.

Re: BusyBeaver(6) Is Quite Large

#47

Post by Xcelerate »

charcircuit wrote: post #42

>imagine you had 10,000,000_10 grains of sand. Then you could … well, uh … you could fill about 10,000,000_10 copies of the observable universe with that sand. I hope that helps people visualize it! People can't visualize numbers that big. There's more ways to express numbers than just counting them. For example a single grain of sand has infinite states it can be in (there are an infinite amount of real numbers), so…

At some point big numbers become much more about the consistency strength of formal systems than “large quantities”.

I.e., how well can a system fake being inconsistent before that fact it discovered? An inconsistent system faking consistency via BB(3) will be “found out” much quicker than a system faking consistency via BB(6). (What I mean by faking consistency is claiming that all programs that run longer than BB(n) steps for some n never halt.)

Re: BusyBeaver(6) Is Quite Large

#48

Post by unsnap_biceps »

charcircuit wrote: post #42

>imagine you had 10,000,000_10 grains of sand. Then you could … well, uh … you could fill about 10,000,000_10 copies of the observable universe with that sand. I hope that helps people visualize it! People can't visualize numbers that big. There's more ways to express numbers than just counting them. For example a single grain of sand has infinite states it can be in (there are an infinite amount of real numbers), so…

I'm confused about this example, isn't the count of grains of sand equal to the count of observable universes so it'd be a single grain of sand per universe?

Re: BusyBeaver(6) Is Quite Large

#49

Post by falcor84 »

lupire wrote: post #32
dtech wrote: post #26

Earlier quoted context omitted.

It's as much a number as 12

Only if you believe that a number you can't count is a number. You can believe that, but it's a leap.

Couldn't you make the same argument for sqrt(2), or better yet for zero [0]?

[0] https://en.wikipedia.org/wiki/Zero:_The_Biography_of_a_Dange...

Re: BusyBeaver(6) Is Quite Large

#50

Post by gylterud »

nyssos wrote: post #39
perthmad wrote: post #25

Earlier quoted context omitted.

This integer only exists if you assume classical logic. Otherwise, there is no such integer a priori, and actually there is none in general.

Classical logic is the presumed default for mathematics, if someone is working in a different system they will say so explicitly.

Pondering mathematical objects such as BB(n) is exactly the kind of stuff which rooks one’s faith in classical logic.
Post reply on HN