I wonder if the visible universe is large enough to write down the exact value of BB(6).
Just the starting number in the article is ¹⁵10. That means it's 10^(¹⁴10). That means it has ¹⁴10 digits. So no, you can't.
BusyBeaver(6) Is Quite Large
71–80 of 232 posts
Re: BusyBeaver(6) Is Quite Large
#72It 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…
Within ZFC one can prove that any two models of second order PA are isomorphic. ZFC proves that PA is consistent. ZFC is good enough to capture arithmetical truth.
Re: BusyBeaver(6) Is Quite Large
#73It 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.
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 don't understand, surely if we assume ZFC is consistent then it's obvious that it won't halt? Even if its consistency can't be proven, neither can its inconsistency, so it won't halt. Or is that only provable outside of ZFC?
I guess it's also hard when we have an arbitrary Turing machine and have to prove that what it's doing isn't equilavent to trying to prove an undecibable statement.
Re: BusyBeaver(6) Is Quite Large
#74Earlier quoted context omitted.
Continuing the theme of iteration: it was the first time I encountered pentation
One of the reasons I like the use of the number line in schools is that on the line it's more obvious when you're shown addition and multiplication and then later exponeniation that this is a pattern . With the number line, two natural questions arise and, hopefully by the time you're taught exponentiation the Math teacher knows enough math to confidently affirm the answer to both. Yes, it keeps going like this forev…
Don't forget identity. Its range is small but important!
Re: BusyBeaver(6) Is Quite Large
#75It 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…
This ignores the fact that it is not so easy to find natural interesting statements that are independent of ZFC.
Statements that are independent of ZFC are a dime a dozen when doing foundations of mathematics, but they're not so common in many other areas of math. Harvey Friedman has done interesting work on finding "natural" statements that are independent of ZFC, but there's dispute about how natural they are. https://mathoverflow.net/questions/1924/what-are-some-reason...
In fact, it turns out that a huge amount of mathematics does not even require set theory, it is just a habit for mathematicians to work in set theory. https://en.wikipedia.org/wiki/Reverse_mathematics.
Re: BusyBeaver(6) Is Quite Large
#76Earlier quoted context omitted.
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.
But the comment is not just saying something negative. It is implying that claims from the article like "Then, three days ago, Tristan wrote again to say that mxdys has improved the bound again, to BB(6)>9_2_2_2" are not real results. The justification for these not being real results is solely based off whether author is actually on the forefront of research.
I think you're touching on something important here.
OP isn't making a ad hominem fallacy in a logical argument sense - it's not saying "Aaronson is wrong because he's not a frontline researcher."
But you're absolutely right to feel uncomfortable with their approach. There's something off-putting about dismissing someone's reporting of research developments, even if you prefer more comprehensive coverage, or there's more interesting things to say.
The thing is, if that's ad hominem, so is any recommendation preferring one second-hand reporting over another -- ex. "if you want the actual news, read Tucker, not Krugman" isn't an ad hominem towards Krugman.
Another example we see often on HN: saying "you should read the actual paper instead of this pop science" is a quite frequent, quite agreeable, and yet dull, contribution on say, a Quanta article. Yet, I imagine we agree this isn't an ad hominem.
The real issue might be that OP conflates two different things: being a primary researcher versus being a good science communicator who accurately reports on others' work.
Both roles have value, and questioning whether someone has filled one role doesn't necessarily invalidate their ability to fill the other.
(this helped me understand my odd frustration with the dull comments on science articles: I emotionally engage with it as being mean / out of bounds, but its true, and in reality, what I'm frustrated with is there could always be a more detailed article, or even paper, but yet we all must publish)
Re: BusyBeaver(6) Is Quite Large
#77>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…
If the universe rounds to the nearest Planck unit, then a grain of sand suddenly has not all that many states.
Using infinite precision to make things seem tractable is sleight of hand in my book. Stick with integers when you're describing scale.
Re: BusyBeaver(6) Is Quite Large
#78It 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.
Many replies don't seem to understand Godel and independence (and one that might is heavily downvoted). Cliff notes:
* ZFC is a set of axioms. A "model" is a structure that respects the axioms.
* By Godel, we know that ZFC proves a statement if and only if the statement is true in all models of ZFC.
* Therefore, the statement "BB(748) is independent of ZFC" is the same as the statement "There are two different models of ZFC where BB(748) are two different numbers.
* We can take one of these to be the "standard model"[1] that we all think of when we picture a Turing Machine. However, the other would be a strange "non-standard" model that includes finite "natural numbers" that are not in the set {0,1,2,3,...} and it includes Turing Machines that halt in "finite" time that we would not say halt at all in the standard model.
* So BB(748) is indeed a number as far as the standard model is concerned, the problem only comes from non-standard models.
TL;DR this is more about the fact that ZFC axioms allow weird models of Turing Machines that don't match how we think Turing Machines usually work.
[1] https://en.wikipedia.org/wiki/Non-standard_model_of_arithmet...
Re: BusyBeaver(6) Is Quite Large
#79People 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], compared to 4^12*23836540=399910780272640 unique 6-state Turing Machines [3].
With the achievement of pentation in only 6 states, several people now believe that 7 states should suffice to surpass Graham's. I would still find that rather surprising. A few days ago, I made a large bet with one of them on whether we would see proof of BB(7)>Graham's within the next 10 years.
What do people here think?
Re: BusyBeaver(6) Is Quite Large
#80Earlier quoted context omitted.
Gödel's theorem shows that you need an infinite number of axioms to describe reality (given that available reality isn't finite), so any existing axiomatic system isn't enough.
Well, obviously we could simply take every true sentence of Peano arithmetic as an axiom to obtain a consistent and complete system, but if we think in that spirit, then almost every mathematician in the world is working on finding a better set of axioms (because every proof would either give us new axiom or show that something should not be included as axiom), right?
> obviously we could simply take every true sentence of Peano arithmetic as an axiom to obtain a consistent and complete system
If you’re talking about every true sentence in the language of PA, then not all such sentences are derivable via the theory of PA. If you are talking about the theorems of PA, then these are missing an infinite number of true statements in the language of PA.
Harvey Friedman’s “grand conjecture” is that virtually every theorem that working mathematicians actually publish can already be proved in Elementary Function Arithmetic (much weaker than PA in fact). So the majority of mathematicians are not pushing the boundaries of the existing foundational theories of mathematics, although there is certainly plenty of activity regardless.