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

31–40 of 232 posts

Re: BusyBeaver(6) Is Quite Large

#31

Post by [deleted] »

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.

[deleted]

Re: BusyBeaver(6) Is Quite Large

#32

Post by lupire »

dtech wrote: post #26
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.

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.

Re: BusyBeaver(6) Is Quite Large

#33

Post by ajkjk »

lupire wrote: post #23
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…

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

I am aware it's an infinite tape and finite state (maybe I misspoke somewhere), as well as the halting machines using finite tape (because of course they do).

But the overall 'complexity' (at a timestep, say) is going to be due to the states and the tape together. The BB(5) example that was analyzed, iirc, was a Collatz-like problem (Aaronson describes it here: https://scottaaronson.blog/?p=8088 ). My interpretation of this is that:

1. collatz-like functions have a lot of complexity just due to math alone 2. 5 states turned out to be enough to "reach" that one that 3. more states means you're going to reach more possible Collatz-like functions (they don't have to be Collatz-like; it's just easier to think about them like that) 4. eventually you reach ones that ZFC cannot show to halt, because there is effectively no way to prove it other than running them, and then you would have to solve the halting problem.

The part that was helpful for me to be less unsettle by BB(745) being independent of the ZFC was the notion that it eventually boils down to a halting problem, and asking ZFC to "solve" it... which is more agreeable than the idea that "ZFC cannot compute a function that seems to be solvable by brute force".

Re: BusyBeaver(6) Is Quite Large

#34

Post by Scarblac »

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…

And also, if BB were computable, then it could be used to solve the halting problem: run the Turing machine of size n for BB(n) steps, and if it hasn't halted yet, it never will. So the BB function is clearly not computable.

But to me as a layman that seems true regardless of formal axioms chosen, but I guess I need to read that linked thesis.

Re: BusyBeaver(6) Is Quite Large

#35

Post by lupire »

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.

Re: BusyBeaver(6) Is Quite Large

#36

Post by ajkjk »

Scarblac wrote: post #34
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…

And also, if BB were computable, then it could be used to solve the halting problem: run the Turing machine of size n for BB(n) steps, and if it hasn't halted yet, it never will. So the BB function is clearly not computable. But to me as a layman that seems true regardless of formal axioms chosen, but I guess I need to read that linked thesis.

That is the standard argument for why BB is uncomputable for general n, but it's not the same as why BB(n) would be independent of ZFC for fixed n.

Re: BusyBeaver(6) Is Quite Large

#37

Post by lupire »

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.

That's not ad hominem at all.

Re: BusyBeaver(6) Is Quite Large

#38

Post by Scarblac »

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.

There is a finite number of Turing machines of size 748. The number of them that eventually halt is thus also finite, and BB(748) is the highest number of steps in the finite list of how many steps each took to halt. It has to be a number.

We just can't prove which number it is, we don't know which of the machines halt.

Re: BusyBeaver(6) Is Quite Large

#39

Post by nyssos »

perthmad wrote: post #25
jerf wrote: post #19

Earlier quoted context omitted.

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.

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

Re: BusyBeaver(6) Is Quite Large

#40

Post by Xcelerate »

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.

It boggles my mind that we ever thought a small amount of text that fits comfortably on a napkin (the axioms of ZFC) would ever be “good enough” to capture the arithmetic truths or approximate those aspects of physical reality that are primarily relevant to the endeavors of humanity. That the behavior of a six state Turing machine might be unpredictable via a few lines of text does not surprise me in the slightest.

As soon as Gödel published his first incompleteness theorem, I would have thought the entire field of mathematics would have gone full throttle on trying to find more axioms. Instead, over the almost century since then, Gödel’s work has been treated more as an odd fact largely confined to niche foundational studies rather than any sort of mainstream program (I’m aware of Feferman, Friedman, etc., but my point is there is significantly less research in this area compared to most other topics in mathematics).

Post reply on HN