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

21–30 of 232 posts

Re: BusyBeaver(6) Is Quite Large

#21

Post by thechao »

Straw wrote: post #14
ChadNauseam wrote: post #11

Earlier quoted context omitted.

The number itself is not independent of ZFC. (Every integer can be expressed in ZFC.) What's independent of ZFC is the process of computing BB(748).

Sure, if someone just gives you the number, ZFC can represent it. But ZFC cannot prove that the value is correct, so how do you know you have the right number? Use a stronger proof system? Go a bit bigger and same issue.

We need to distinguish between a computer that's equivalent to BB(n), and a computer big enough to compute the value of the number that is BB(n). By (terrible) analogy: a 4004 can be made to write a finite loop that describes how many FLOPs the number 1 supercomputer can compute without, itself, being able to usefully perform the computations of that supercomputer. (The 4004 will run out of memory/addressable disk space.) Similarly, we can no longer build decidable programs in ZFC that can compute the number BB(748). Scott is saying that they now think this "disassociation" might occur at BB(7)!

Re: BusyBeaver(6) Is Quite Large

#23

Post by lupire »

ajkjk wrote: post #20
Straw wrote: post #14

Earlier quoted context omitted.

Sure, if someone just gives you the number, ZFC can represent it. But ZFC cannot prove that the value is correct, so how do you know you have the right number? Use a stronger proof system? Go a bit bigger and same issue.

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…

It has to come from a finite value (specifically, the amount of complexity that can be enocoded in 745 pieces of information https://turingmachinesimulator.com/shared/vgimygpuwi), because the finite size 745 with infinite tape leads to uncomputability, but the size 5 does not.

In a very real sense, a deep kind of infinite complexity can be generated from 745 objects of certain kind, but not from 5 objects of that kind..

Turing machines have infinite tape, not infinite state. The entire set of all halting machines of a given size collectively only use finite tape. Totally finite. Only (some of) the non-halting machines use infinite tape.

The problem is that we don't know in advance how large the (definitely finite) upper bound on the amount of tape all the size-N halting machines use, until after enough of them (one per known equivalence class) halt. And we don't know (in general) how to run all the halting ones until they halt, without also running a non-halting program for an unbounded amount of time.

TL:DR: unbounded is not infinite, but big enough to be a problem.

Re: BusyBeaver(6) Is Quite Large

#24

Post by dtech »

ajkjk wrote: post #20
Straw wrote: post #14

Earlier quoted context omitted.

Sure, if someone just gives you the number, ZFC can represent it. But ZFC cannot prove that the value is correct, so how do you know you have the right number? Use a stronger proof system? Go a bit bigger and same issue.

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.

Re: BusyBeaver(6) Is Quite Large

#25

Post by perthmad »

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…

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

Re: BusyBeaver(6) Is Quite Large

#26

Post by dtech »

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.

It's as much a number as 12

Re: BusyBeaver(6) Is Quite Large

#27

Post by moralestapia »

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.

Re: BusyBeaver(6) Is Quite Large

#28

Post by tedunangst »

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

Can you elaborate on what's wrong with this post?

Re: BusyBeaver(6) Is Quite Large

#29

Post by griffzhowl »

sedatk wrote: post #17

> Also, the left-superscript means tetration, or iterated exponentiation: for example, 1510 means 10 to the 10 to the 10 and so on 15 times. I thought it was a typo. First time I encounter tetration.

Continuing the theme of iteration: it was the first time I encountered pentation

Re: BusyBeaver(6) Is Quite Large

#30

Post by lupire »

seeknotfind wrote: post #2

> So I said, imagine you had 10,000,000sub10 grains of sand. Then you could … well, uh … you could fill about 10,000,000sub10 copies of the observable universe with that sand. I don't get this part. Is it really rounding away the volume of the observable universe divided by the average volume of a grain of sand? That is many more orders of magnitude than the amount of mass in the universe, which is a more usual compa…

Here's a more common example of this sort of comparison:

In significant figures, 1.0 billion minus 1.0 million equals 1.0 billion.

Post reply on HN