Scott Aaronson | How Much Math Is Knowable? [Harward CMSA]: https://www.youtube.com/watch?v=VplMHWSZf5c
Recently on HN (couple of months ago): https://news.ycombinator.com/item?id=43776477
BusyBeaver(6) Is Quite Large
151–160 of 232 posts
Re: BusyBeaver(6) Is Quite Large
#152Earlier quoted context omitted.
What makes BB(748) independent of ZFC is not its value, but the fact that one of the 748-state machines (call it TM_ZFC_INC) looks for an inconsistency (proof of FALSE) in ZFC and only halts upon finding one. Thus, any proof that BB(748) = N must either show that TM_ZF_INC halts within N steps or never halts. By Gödel's famous results, neither of those cases is possible if ZFC is assumed to be consistent.
I think what's most unintuitive is that most (all?) "paradoxes" or "unknowables" in mathematics involve infinities. When limiting ourselves to finite whole numbers, paradoxes necessarily disappear. BB(748) is by definition a finite number, and it has some value - we just don't know what it is. If an oracle told us the number, and we ran TM_ZFC_INC that many steps we would know for sure whether ZFC was consistent or n…
It’s even more counterintuitive than you let on! If you are working in ZFC along with the axiom “ZFC is consistent” then there’s no issue: just a normal number[1]. Where things get really strange is in ZFC plus the axiom “ZFC is inconsistent”.
This already sounds like an inconsistent theory, but surprisingly isn’t: Godel’s second incompleteness theorem directly gives us that Con(ZFC) is independent, so there are models that validate both Con(ZFC) and ~Con(ZFC). The models that validate ~Con(ZFC) are very confused about what numbers are: from the models perspective, there is a number corresponding to a Godel code for the supposed proof of inconsistency, but from the external view this is a “nonstandard number”: it’s not not a finite numeral!
Getting back to BB(748): what does this look like in a model of ZFC + ~Con(ZFC)? We can prove that the machine internal to the model will find that astronomically large Godel code, so BB(748) will be a nonstandard number. In other words, you can tell if a 748 state machine will terminate in this model: you’ve just got to run it for a number of steps that’s larger than every finite numeral!
[1]: unless there’s some machine that with 748 that enumerates theorems of ZFC+Con(ZFC) but that’s a different discussion.
Re: BusyBeaver(6) Is Quite Large
#153Earlier quoted context omitted.
Math's a cooperative endeavor, I want to know if I'm wrong! I'm not sure I understand the distinction you're trying to make though, and I'm not sure it's right... The argument that BB has to grow faster than any computable sequence is that if we have a computable f(n) where for all n f(n) > BB(n) then we can solve the halting problem by simulating turing machines of size n for f(n) steps and checking if they halt. Ev…
Thanks for the good attitude! Ah, I didn't realize 'computable' had a specific meaning in this domain -- showing the limits of my experience a bit. After looking at the wikipedia page and rereading your sketch, I think it is true that > it eventually needs to grow faster than any computable operator we define I'm not sure if this has implications about how quickly BB() grows compared to the "operator strength" ladder…
> We may find pentation(n) > BB(n) for all n greater than some threshold.
No, that is impossible. Tetration, pentation, etc. are all computable sequences and BB grows faster than any computable sequence. So you have the > sign where you really want a < sign.
Re: BusyBeaver(6) Is Quite Large
#154It 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 truth value of the continuum hypothesis is either 1 or 0 (at least from a platonistic perspective). But, it is proven to be independent of ZFC. No huge numbers involved, just a single bit whose value ZFC doesn't tell you.
Re: BusyBeaver(6) Is Quite Large
#155It 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. A…
> 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.
ZFC is way overpowered for that. https://mathoverflow.net/questions/39452/status-of-harvey-fr...
Re: BusyBeaver(6) Is Quite Large
#156It 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.
BB(748) is a natural number, and _all_ natural numbers are computable.
There is definitely a function f such that f() = n for all n ∈ ℕ.
But there is also a function g that you cannot prove whether g() = n.
Important distinction.
This means that somebody could claim that the value of BB(748) = n but you cannot be sure if they are correct (but you might be able to show they are wrong).
Re: BusyBeaver(6) Is Quite Large
#157> 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…
Yes, that's only some normal number amount of orders of magnitude. Even 10,000,000^10,000,000 is already so large that it doesnt matter, let alone after exponentiating _the exponent_ nine times more.
It's the other way around: we're talking about 10^(10^(10^(10^…))) (which is vastly bigger).
Re: BusyBeaver(6) Is Quite Large
#158People on the bbchallenge Discord server are keen to speculate on how many Turing Machine states are needed to surpass Graham's Number, which is vastly larger than the 2^^2^^2^^9 achieved by the latest BB(6) champion. We know from the functional busy beaver [1] that Graham behaviour can come surprisingly early; a 49-bit lambda term suffices. There are only 77519927606 closed lambda terms of at most that size [2], com…
I can't pretend to be an expert, but I'll argue BB(7) is probably larger than Graham's number. BB has to grow faster than any computable sequence. What exactly that means concretely for BB(7) is... nothing other than handwaving... but it sort of means it needs to walk up the "operator strength" ladder very quickly... it eventually needs to grow faster than any computable operator we define (including, for example, up…
I can’t edit my original comment anymore, but replying to say I went on a Wikipedia binge and I think you’re right. Thanks for humoring me and helping me learn!
Re: BusyBeaver(6) Is Quite Large
#159Earlier quoted context omitted.
I think what's most unintuitive is that most (all?) "paradoxes" or "unknowables" in mathematics involve infinities. When limiting ourselves to finite whole numbers, paradoxes necessarily disappear. BB(748) is by definition a finite number, and it has some value - we just don't know what it is. If an oracle told us the number, and we ran TM_ZFC_INC that many steps we would know for sure whether ZFC was consistent or n…
BB(748) is a finite number, but I'd argue its magic also comes from infinites: the fact some Turing Machines run forever and never halt.
Is it? If it's not possible to prove that it's the best solution to bb(748), does it even exist in any meaningful way?
Re: BusyBeaver(6) Is Quite Large
#160Earlier 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…
> 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 halts from one that just hasn't halted yet (since it has an infinite number of states, you can't just wait…
What happens if you take the larger of a and b and run all the Turing machines for that many steps?