People 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.
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-arrow^n, and up-arrow^f(n) for any computable f).
My gut feeling is that the growth between 47 million and 2^^2^^2^^9 is qualitatively larger than the growth between 2^^2^^2^^9 and graham's number in terms of how strong the operator we need is (with gramah's number being g_64 and g here being roughly one step "above" up_arrow^n). So probably we should have BB(7)>Graham's number.
Apologies if this feels adversarial, but I think your informal proof has an error, and I think I can explain it!
Your proof rests primarily on this assertion:
> BB has to grow faster than any computable sequence.
This is almost true! BB(n) has to grow faster than any computable sequence _defined by an n-state Turing machine_. That last part is really important. (Note that my restatement is probably incorrect too, it is just correct enough to point out the important flaw I saw in your statement). This means that up-arrow^f(n) _can_ be larger than BB(n) — up-arrow^f(n) is not restricted by a Turing machine at all. As an easy example, consider f(n) = BB(n)^2.
You may still be right about BB(7) being bigger than Graham’s number, even if your proof is not bulletproof
Sure, but the example I'm providing is just meant to illustrate that BB(n) is not greater than arbitrary f(n). I'm not trying to provide the biggest number, I'm trying to illustrate that the sketched-out proof is incorrect. If you want me to provide a bigger number, I suppose another easy example is to define f(n) = BB(BB(n)).
Edit: Oh sorry, I see I misread the direction of your greater than signs. Leaving comments as-is though, hopefully that results in the least confusion
oops, my greater than signs are in the wrong direction. specifically, for any computable function f, there exists some constant c such that f(BB(n))<<BB(n+c)
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.
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 not based on whether it terminated.
The execution of the turing machine can be encoded in ZFC, so it really is the value of BB(748) that is the magic ingredient. Somehow even knowledge of the value of this finite number is a more potent axiomatic system than any we've developed.
You’d know the value in a more powerful system than ZFC (as it includes such an oracle) — but you can already reason about ZFC in a more powerful system.
We already have more powerful systems, but what causes the inability to self-reason is exactly that power: only first order logic can prove its own consistency. Once you get powerful enough to model arithmetic, you can build statements with self-referential weirdness.
I don’t see it as a paradox, but as growth: a sufficiently rich system can pose questions which suggest a richer system — and thereby scaffold up the universe hierarchy.
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.
If we assume ZFC to be consistent, then Gödel's 2nd incompleteness theorem tells us that it cannot prove its own consistency. So in particular it cannot prove than TM_ZFC_INC will never halt.
If you believe that ZF is consistent, then you believe that the machine cannot halt (assuming you trust its construction). But you cannot write a proof in ZF that the machine cannot halt. Such a proof must include a new axiom "ZF is consistent", or some stronger axiom.
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).
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.
Yeah, I’m quite familiar with Friedman’s work. I mentioned him and his Grand Conjecture in another comment.
> This ignores the fact that it is not so easy to find natural interesting statements that are independent of ZFC.
I’m not ignoring this fact—just observing that the sheer difficulty of the task seems to have encouraged mathematicians to pursue other areas of work beside foundational topics, which is a bit unfortunate in my opinion.
I agree most working mathematicians have limited interest in foundational topics. To me, that seems harmless enough.
> approximate those aspects of physical reality that are primarily relevant to the endeavors of humanity.
This is the comment that made me think that you were saying we needed more work on foundations for math as it is used in the sciences, and that doesn't match my understanding. Did I read it differently than you meant it?
> 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.
But why? Gödel's theorem does not depend on number of axioms but on them being recursively enumerable.
Right, Hilbert’s goal was (loosely speaking) to “find a finitely describable formal system” sufficient to “capture all truths”. When Gödel showed that can’t be done, that shouldn’t imply we just stop with the best theory we have so far and call it a day—it means there are an infinite number of more powerful theories (with necessarily longer minimal descriptions) waiting to be discovered.
In fact, both Gödel and Turing worked on this problem quite a bit. Gödel thought we might be able to find some sort of “meta-principle” that could guide us toward discovering an ever increasing hierarchy of more powerful axioms, and Turing’s work on ordinal progressions followed exactly this line of thinking as well. Feferman’s completeness theorem even showed that all arithmetical truths could be discovered via an infinite process. (Now of course this process is not finitely axiomatizable, but one can certainly extract some useful finite axioms out of it — the strength of PA after all is equivalent to the recursive iteration up to ε_0 of ‘Q_{n+1} = Q_n + Q_n is consistent’ where Q_0 is Robinson arithmetic).
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.
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.
Unfortunately no, ZFC isn't good enough to capture arithmetical truth. The problem is that there are nonstandard models of ZFC where every single model of second-order PA within is itself nonstandard. There are even models of ZFC where a certain specific computer program, known as the "universal algorithm" [1], solves the halting problem for all standard Turing machines.
ZFC allows models of second order PA and proves that those models are all isomorphic. Within each model of ZFC there is no such thing as a nonstandard model of second order PA. One can only think it is nonstandard by looking from outside the model, no? What theorem of second order PA is ZFC unable to prove?
This is similar to how there are countable models of ZFC but those models think of themselves as uncountable. They are countable externally and not internally.
> It boggles my mind that a number (an uncomputable number, granted) like BB(748) can be "independent of ZFC".
It's BB(n) that is incomputable (that is there's no algorithm that outputs the value of BB(n) for arbitrary n).
BB(748) is computable. It's, by definition, a number of ones written by some Turing machine with 748 states. That is this machine computes BB(748).
> It feels like a category error or something.
The number itself is just a literally unimaginably large number. Independence of ZFC comes in when we try to prove that this number is the number we seek. And to do that you need theory more powerful than ZFC to capture properties of a Turing machine with 748 states.
I think the more correct statement is that there are different models of ZFC in which BB(748) are different numbers. People find that weird because they don't think about non-standard models, as arguably they shouldn't.
Isn't that incompatible with the models being consistent?
Suppose model A proves BB(748) = X and model B proves BB(748) = Y > X. But presumably the models can interpret running all size 748 Turing machines for Y steps. Either one of the machines halts at step Y (forming a proof within A that BB(748) >= Y contradicting the assumed proof within A that BB(748) = X < Y) or none of the machines halts at step Y (forming a proof within B that BB(748) != Y contradicting the assumed proof within B that BB(748) = Y).
I'm guessing the only way this could ever work would be some kind of nastiness like X and Y aren't nailed down integers, so you can't tell if you've reached them or not, and somehow also there's a proof they aren't equal.
The issue is that X and Y are not actual natural numbers. They are mathematical objects that satisfy all the ZFC axioms and Peano arithmetic but are infinitely large. The issue is that ZFC underspecifies natural numbers.
How is that possible? That implies there’s at least one specific program whose execution changes based on the ZFC model. The rules of program execution are so simple, it doesn’t make sense that they’d change based on anything like that.
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 halts from one that just hasn't halted yet (since it has an infinite number of states, you can't just wait for a loop).
So presumably the independence of a number from ZFC is like that also: you can't prove it's the value of BB(745) because you won't know if you've proved it; the only way to prove it is essentially to run those Turing machines until they stop and you'll never know if you're done.
I'm guessing that for the very small Turing machines there is not enough structure possible to encode whatever infinitely complex states end up being impossible to deduce halting from, so they end up being Collatz-like and then you can go prove things about them using math. As you add states the possible iteration steps go wild and eventually do stuff that is beyond ZFC to analyze.
So the finite value 745 isn't really where the infinity/uncomputability comes from-it comes from the infinite tape that can produce arbitrarily complex functions. (I wonder if over a certain number of states it becomes possible to encoding a larger Turing machine in the tape somehow, causing a sort of divergence to infinite complexity?)
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.
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
> What happens at whatever number it starts true at?
Usually, "what happens" is that the machines become large enough to represent a form of induction too strong for the axioms to 'reason' about. It's a function of the axioms of your theory, and you can add more axioms to stave it off, but of course you can't prove that your new axioms are consistent without even more axioms.
> 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.
Only insofar as you can put faith into the Church–Turing thesis to sort out all the technicalities of enumerating and verifying proofs. There still must be an encoding, just not the usual Gödel numbering.
> 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
Those are two very different ideas. Your second sentence says that Gödel's theorem is easy to prove if you have results about the halting problem. Your first one says that in order to prove Gödel's theorem, you need to establish results about the halting problem.
I'm saying that if you want to understand why Gödel's theorem is true, look at the one-paragraph proof based on the halting problem, not the like 20-page one with Gödel numbers.
Independence from ZFC means we can't prove that any given number is BB(643) using ZFC. It doesn't mean we can't prove it at all, e.g. one could use a stronger set theory like NBG which can prove the consistency of ZFC to verify the value of BB(643). But there would be some n for which BB(n) is independent of that set theory, requiring a yet-stronger theory, and so on ad infinitum.
ZF & ZFC are as important as they are because they're the weakest set theories capable of working as the foundations of mathematics that we've found. We can always add axioms, but taking axioms away & still having a usable theory on which to base mathematics is much more difficult.
> 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 for a loop).
> So presumably the independence of a number from ZFC is like that also: you can't prove it's the value of BB(745) because you won't know if you've proved it; the only way to prove it is essentially to run those Turing machines until they stop and you'll never know if you're done.
These aren't similar ideas. You can't know if a machine that hasn't halted yet will ever halt. But you can easily know if a machine that has already halted was going to halt.
Independence is the second case. For the value of BB(x) to be independent of ZFC, one of two things must hold:
(1) ZFC is inconsistent, and therefore all statements are independent of it.
(2) ZFC is consistent with two different statements, "BB(x) = a" and "BB(x) = b" for two different a, b. This means that a disproof of either statement cannot exist.
This, in turn, means that there is no observation you could ever make that would distinguish between the values a and b (for the identity of BB(x)). No matter what you believe the value of BB(x) might secretly be, there are no consequences; nothing anywhere could ever change if the value turned out to be different. Because, if there were an observable consequence of the value being different, the hypothetical observation of that consequence would be a disproof of the value that didn't cause it, and no such disproof can exist.
Neither value, a or b, can be more true than the other as the answer to the question "what is BB(x)?". It doesn't make sense to consider that question to have an answer at all.
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.
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".
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)!
To try and help people digging into this, the following helped me.
Two lenses for trying to understand this are potentially Chastain's limits on output of a lisp program being more complex than the program itself [1] or Markov's proof that you can't classify manifolds in d>= 4.
If you try the latter and need/want to figure out how the Russian school is so different this is helpful [2]
IMHO the former gives an intuition why, and the latter explains why IMHO.
In ZFC, C actually ends up implying PEM, which is why using constructionism as a form of reverse math helped it click for me .
This is because in the presence of excluded middle, every sequentially complete metric space is a complete space, and we tend to care about useful things, but for me just how huge the search space grows was hidden due to the typical (and useful) a priori assumption of PEM.
If you have a (in my view) dislike for the constrictive approach or don't want/have to invest in learning an obscure school of it,
This recent paper[3] on the limits for finding a quantum theory of everything is another lens.
Yet another path is through Type 2 TMs and the Borel hierarchy, where while you can have a uncomputable number on the input tape you algorithms themselves cannot use them, while you can produce uncomputable numbers by randomly selecting and/or changing an infinite sequence.
Really it is the difference between expressability and algorithms working within what you can express.
Hopefully someone else can provide more accessible resources. I think a partial understanding of the limits of algorithms and computation will become more important in this new era.
Looking at [3], they seem to argue that the system isn’t complete for the usual Gödel reasons, which, sure, it isn’t, but then they call the claim that the system fails to decide, which is a statement about probability, a “scientific fact”. This seems to me like a mistake?
Like, a TOE is not expected to decide all statements expressible in the theory, only to predict particular future states from past states, with as much specificity as such past states actually determine the future states. It should not be expected to answer “given a physical setup where a Turing machine has been built, is there a time at which it halts?” but rather to answer “after N seconds, what state is the machine (as part of the physical system) in?” (for any particular choice of N).
Whether a particular statement expressed in the language of the theory is provable in the theory, is not a claim about the finite-time behavior of a physical system, unless your model of physics involves like, oracle machines or something like that.
Edit: it later says:
“
Chaitin’s theorem states that there exists a constant
K_{ℱ_{QG}}
, determined by the axioms of
ℱ_{QG}
, such that no statement
S with Kolmogorov complexity
K(S) > K_{ℱ_{QG}}
can be proven within ℱ_{QG}
.”
But this, unless I’m badly misinterpreting it, seems very wrong? Most formal systems of interest have infinitely many distinct theorems. Given an infinite set of strings, there is no finite universal upper bound on the Kolmogorov complexity of the strings in that set.
Maybe this was just a typo or something?
They do then mention something about the Bekenstein bound, which I haven’t considered carefully yet but seems somewhat more promising than the parts of the article that preceded it.
I will admit that I added that cite mostly because of the very real barriers to even learning RUSS.
By the typos etc.. you. can probably also tell I was doing this on mobile, unfortunately as a passenger in a car.
To quote Chaitin’s explanation here:
> In contrast I would like to measure the power of a set of axioms and rules of inference. I would like to be able to say that if one has ten pounds of axioms and a twenty-pound theorem, then that theorem cannot be derived from those axioms.
This paper's notation does seem to be confusing, but I still think it is essentially complete with the above.
"K_{ℱ_{QG}}" would probably most commonly be L in most descriptions, a natural number that is the upper bound of complexity for provable statements in a formal system S
L is not a limit on complexity, it means that there is no formal proof for S that its Kolmogorov complexity exceeds L, for any string.
You can still prove that there are strings far more complex than L with S, and in fact there will often be far more of those strings than the ones equal to or less than L.
It is a limit on what you can prove about those strings with a greaterKolmogorov complexity in S.
Or to rewrite the above:
"There exists a natural number L such that we can't prove the Kolmogorov complexity of any specific string of bits is more than L."
Does that help or did I miss the mark on your objection?
It looks like the authors of [3] misunderstood Chaitin. What Chaitin said about the limits of provability is that no statements of the form "K(x) > c_F" can be proven in formal system F where c_F is some constant depending on F.
Let X = "1 if ZF is consistent, 0 otherwise". Then the statements "X = 0" and "X = 1" are independent of ZF. Whether the definition of X is a satisfactory definition of a particular number is a question of mathematical philosophy.
BB(748) is very similar, in that I'd call it a 'definition' independent of ZF rather than a 'number' independent of ZF.
No individual number is uncomputable. There’s no pair of a number and proof in ZFC that [that number] is the value of BB(748). And, so, there’s no program which ZFC proves to output the value of BB(748). There is a program that outputs BB(748) though, just like for any other number.
I think your mistake is your claim that BB(748) is a natural number. For you to know that, you would necessarily have to know an upper bound for the number of steps it takes for the BB-748 machine (whichever machine it is) to halt. But you definitely don't know that.
Related: It's incorrect to claim that each machine either halts or doesn't halt. To know that that dichotomy holds would require having a halting problem algorithm.
Individual numbers can be uncomputable! For example, take your favorite enumeration of Turing machines, (T1, T2...) and write down a real number in binary where the first bit is 0 if T1 halts and 1 otherwise, second bit is 0 if T2 halts... clearly this number is real and between 0 and 1, but it cannot be computed in finite time.
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.
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, and therefore, 100% of integers are equally just "mathematical concepts". That one of them is identified by BB(748) isn't a particularly important aspect. But certainly, a very specific number is identified by that designation, though nothing in this universe is going to know what it is in any meaningful sense.
I'm fairly certain that's wrong, and I see a couple of other people may be making that mistake elsewhere in this conversation too. A Turing Machine is a Turing Machine. The execution trace of a Turing Machine is fully determined by its ruleset and its initial input. It doesn't matter which axioms you "take", nor does it matter what the intent of the initial construction of the 748-state machine was, or indeed even if that proof is somehow flawed. The definition of a Turing Machine is effectively the axiom set for this particular case. There is a finite set of 748-state Turing machines, and it is absolutely the case that there is a set of them that loop infinitely, the complementary set that do not, and that there is a maximum length amoung the set that do not. There is no situation where "the next step" of the Turing Machine "depends on your axioms" and could thereby be affected by such a decision.
For that to be the case, there would have to be some symbol under the tape and some state the machine is in for which the action the machine takes and the next state it goes to would depend on the axioms taken somehow. There is no place where the Turing Machine has somehow been running for so long and just gotten so large that its behavior becomes non-deterministic somehow.
What this means is that even if we lived in a universe where we had the unfathomable resources to actually have this number somehow meaningfully "in hand", we would be unable to prove that it was the correct one with just ZFC. Maybe one of the really quite numerous other machines still spinning away would in fact terminate in the future and be the real BB winner, because even this staggeringly monstrously large universe is still piddling nothing next to infinity and the other machines still require infinite resources to run them to discover they never terminate. But that doesn't do anything to affect whether or not there in fact is a single concrete integer that corresponds to BB(748).
Although one imagines that any universe with the resources to "have" BB(748) in it might also have some much more powerful axiom systems to play with in the process. The amount of computational power this universe apparently possesses is beyond all comprehension and who knows what they could know. But even if they used a more powerful system, it wouldn't change what BB(748) is... it just might affect whether or not they were correct about it.
> There is no situation where "the next step" of the Turing Machine "depends on your axioms" and could thereby be affected by such a decision.
That's easy, you just have to be an ultrafinitist, and say, "The definition of a TM presupposes an infinite set of natural numbers for time steps and tape configurations. But there aren't actually infinitely many natural numbers, infinitely long executions, arbitrarily long proofs, etc., outside of the formalism. If a formal statement and its negation do not differ regarding any natural numbers small enough to actually exist (in whatever sense), then neither is more true than the other." In particular, consistency statements may have no definite truth value, if the hypothetical proof of an inconsistency would be too large.
Of course, metamathematics tells us "you can't do that, in principle you could tell the lie if you wrote out the whole proof!" But that principle also presupposes the existence of arbitrarily-long proofs.
(Personally, hearing some of the arguments people make about BB numbers, I've become attracted to agnosticism toward ultrafinitist ideas.)
To be honest I'm not even particularly impressed by that line of reasoning because even if you accept ultrafinitism, there's still a definite integer that it corresponds to. You can deny the "existence" of integers, and thus that the number "exists", but that's contingent on your definition of "existence". It doesn't change what it would be if it did exist.
Plus, ultafinitism is essentially relative to the universe you find yourself in. I hypothesized a universe in which BB(748) could actually exist, but you can equally hypothesize ones in which not only can it exist, it exists comfortably and is considered a small number by its denizens. We can't conceive of such a thing but there's no particular a priori reason to suppose it couldn't exist. If such a universe does actually "exist" does that mean our ultrafinitism is wrong? I'm actually a sort of a proponent of knowing whether your operating in a math space that corresponds to the universe (see also constructive mathematics), but concretely declaring that nothing could possibly exist that doesn't fit into our universe is a philosophical statement, not a mathematical one.
> there's still a definite integer that it corresponds to.
The formalism says that there's still a definite integer that it corresponds to. The ultrafinitist would deny that the formalism keeps capturing truth past where we've verified it to be true, or some unknown distance farther.
> I hypothesized a universe in which BB(748) could actually exist, but you can equally hypothesize ones in which not only can it exist, it exists comfortably and is considered a small number by its denizens.
Sure, but the ultrafinitist would argue, "All this is still just a shallow hypothesis: you've said the words, but that's not enough to breathe much 'life' into the concept. It is but the simplest of approximations that can fit into our heads, and such large things (if they could exist) would likely have an entirely different nature that is incomprehensible to us."
> We can't conceive of such a thing but there's no particular a priori reason to suppose it couldn't exist.
That's why I wouldn't call myself an ultrafinitist, but would prefer an agnostic approach. There may be no great a priori reason to suppose it cannot exist, but I similarly do not see any such reason it must necessarily exist. We empirically notice that our formalism works for numbers small enough to work with, and we pragmatically round it off to "this formalism is true", but one could argue that surprising claims about huge numbers need stronger support than mere pragmatism.
> 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.
> 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.
I'd say that's a bit of a wrong or misleading statement. I think the correct version is "everything[1] can be encoded as a number". The concept of number is a very particular concept! It's pretty absurd to say "a screwdriver is a number" or "a word is a number". That is true for the peano axiomatization of numbers; but to me in particular, I believe numbers are a generalization (and formalization) of the idea or concept of quantity. There's a particular idea that refers to say 'two' apples, the quantity of apples. A word is not a quantity, it's a different concept. Even though each of them could be encoded as a number somehow!
[1]: Everything that we believe to be finite and of interest, that is. We don't know presently anything that could be used in reality (a music, picture, etc.) that can't in principle be encoded as a large enough number.
I think this is quite interesting, because this encoding is critical, and it completes the system. You essentially need a machine to turn things into numbers and numbers into things; and this is unavoidable. You can actually encode this machine itself with numbers! This number (which encodes this transcoding machine) can even be decoded by its own machine! But we cannot actually avoid the machine itself, some actual realization in the real world, because any number, in order to represent something, can only be translated by one "machine" (which can be essentially a computer, or a mind, etc.).
Instead of thinking of machines, you can also think of conventions. So you can have a convention that say the number '5' encodes the concept 'word', or maybe it simply encodes the string of letters "word" ("w"+"o"+"r"+"d"). But the convention interpretation isn't complete, because you still need someone, or something, to interpret this convention in practice and potentially turn concepts into reality, or simply manipulate those concepts in significant and useful ways.
Some more examples: (1) you can encode objects by describing a series of solid operations, essentially CAD modelling, so you have numbers that represent solids. The machine that interprets this number and is able to translate it for example into a picture, a series of instructions to be interpreted by a 3d printer, of performs operations (inferences) about the relevant solid model (for example, a structural analysis) is your "machine", i.e. your software, without which a number, or string of bits by itself doesn't mean anything (except the quantity associated with that binary number, perhaps), and again this encoding or number is essentially arbitrary, it could be very different. (2) a JPEG file for example encodes an image that is read by a software stack (jpeg decoder+picture viewer+operating system+display driver) and forwarded to your monitor to be viewed as a pixel array. Again the string of bits associated with any image could in principle represent anything else representable.
Information (Shannon information in particular) simply implies the encoding possible.
It's really interesting that a lot of the time we are performing essentially translations between different representations of a thing: a series of bits into states of pixels on a screen (a picture), [a series of bits] into a 3d printed object, into a visualization of an object on a screen, etc. (one way), or a reading of a camera sensor (photograph) into a series of bits, a conception of an object (3d modelling), a conception of a story (writing), etc. (the other way). We of course can (and must for them to be built of course) conceptualize those "machines" themselves (e.g. the software part), represent them in some way (our encoding), and then turn this representation into a realization of those machines (a software, a piece of hardware, or just a representation convention, etc.).
In other words, the mind or computer itself is always an integral part of the process, and information in a vacuum doesn't represent anything necessarily.
Finally, most of what we do is some kind of translation, inference, and construction -- everything to assist our lives. Of course some "machines" are capable of generating new concepts, those are very interesting "machines" :)
> I'd say that's a bit of a wrong or misleading statement. I think the correct version is "everything[1] can be encoded as a number". The concept of number is a very particular concept! It's pretty absurd to say "a screwdriver is a number" or "a word is a number". That is true for the peano axiomatization of numbers; but to me in particular, I believe numbers are a generalization (and formalization) of the idea or concept of quantity. There's a particular idea that refers to say 'two' apples, the quantity of apples. A word is not a quantity, it's a different concept. Even though each of them could be encoded as a number somehow!
Well if we're using a more narrow view, then "BB(748)" isn't a number, it's an encoding of a partial algorithm. And it shouldn't be surprising that an algorithm might be unprovable in ZFC.
The actual number, the quantity, is quite easy to write down inside ZFC. And so is the beaver turing machine itself. The hard part is knowing which of the 748-state machines is the beaver.
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.
Let S be a statement. S is called semidecidible (also: Turing recognizable, most commonly "recursively enumerable", abbreviated as "r.e.", but I hate that one) if there is a Turing machine that halts if and only if S is true.
With this definition, we can say that "ZFC is inconsistent" is semidecidible: you run a program that searches for a contradiction.
The question BB(748) =/= 1000 is similarly semidecidable. You can run a program that will rule out 1000 if it is not BB(748).
So they are in the same "category", at least regarding their undecidability.
Also, if you turn "ZFC is consistent" into a number: {1 if ZFC is consistent; 0 if ZFC is inconsistent}, you will see, that BB(748) is not very much different, both are defined (well, equivalently) using the halting of Turing machines, or, the result of an infinite search.
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.
But that's the thing - each generation struggles with whether some new thing is a number. We're typically very inclusive, accepting imaginary numbers and even weirder things like surreal numbers, which we definitely can't count.
But as someone in this generation, I see a good argument for rejecting the big busy beaver numbers, which are provably outside of the realm of calculating with all the resources of our universe's runtime, from being fully accepted as numbers, any more than the first uninteresting number [0].
> For those tuning in from home, here BB(6) is the 6th Busy Beaver number, i.e. the maximum number of steps that a 6-state Turing machine with a {0,1} alphanet can take before halting, when run on an initially all-0 input tape.
Oh! Of course! That sure clears things up for this non-expert. This is clearly a hardcore blog for people who have been doing this kind of research for decades. Kind of awesome to stumble upon something so unapologetically dense and jargony and written for a very specific audience!
That should be enough for someone with an undergrad CS education to at least get a sense of what's going on if they haven't encountered the busy beaver problem before.
Is it niche jargon, absolutely, but to say it's only accessible to people who have put in decades is selling yourself short.
Hmm, interesting. It’s been 30 years since my engineering degree (not CS) and I’d have to look up what a Turing machine is. I think I remember one professor briefly mentioned it as “This is something the CS majors care deeply about but nobody else in the industry does.” Where I was, the CS degree was essentially a math degree dressed up in a hoodie.
It's known that BB(14) is bigger than Graham's number, but this new finding leads me to believe that BB(7) is probably bigger than Graham's number. Intuitively, the technology required to go from pentation to Graham's number feels simpler than the technology required to go from `47,176,870` to `2 <pentate> 5`.
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 forever, that's called Hyperoperation. And yes, we did (probably) skip one, it's known as Successor-of and you were probably not explicitly shown this operator but it's the near end of that infinite succession.
When arithmetic is introduced just as a way to, for example, count money, it's more directly practical in the moment, but you're not seeing the larger pattern.
> 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 comparison.
Yes, that's right, dividing by that ratio essentially barely affects the number in a sense that 'adjacent' numbers in that notation give a much bigger change.
10↑↑10,000,000 / (sand grains per universe) is vastly larger than, say, 10↑↑9,999,999
So on system we're using to write these numbers, there's really no better way to write (very big)/ (only universally big) than by writing exactly that, and then in the notation for very big, it pretty much rounds to just (very big).
Exactly. This number is so so much bigger than 10^100000 or however many grains of sand would fit, that dividing by that amount doesn’t really change it, certainly not enough to bring it down closer to 9,999,999sub10
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.
However many universes in question, there is a qualitative difference between that many empty universes (with 1 grain), and that many completely packed with grain.
Any time I see such results from computation complexity theory, I realize that any current zeitgeist of "super-intelligent AI are gods" is complete bullshit.
You can convert every atom of observable Universe into a substrate for supercomputer, you can harness energies of supermassive black holes to power it, but running a humble BB(6) to halting state would be forever out of its reach.
If you treat the observable universe as a closed system, you could try to apply the Bekenstein bound using
- R ≈ 46.5 billion light-years (radius of the observable universe)
- E ≈ total mass-energy content of the observable universe
The mass-energy includes ordinary matter, dark matter, and dark energy. Current estimates suggest the observable universe contains roughly 10^53 kg of mass-energy equivalent.
Plugging these into S ≤ 2πER/ℏc gives someting on the order of 10^120 bits of maximum information content.
You’re probably referring to a state where all parts of the complete representation exist at the same time. Because if they don’t have to exist at the same time, then it might be possible to “write it down” if the universe has unbounded duration (“might” because I don’t know how the heat death plays into that). However, “at the same” time isn’t well-defined in relativistic spacetime. The sibling comments are definitely right with respect to the reference frame implied by the CMB. But I’m wondering if it wouldn’t be possible to slice spacetime in a way that actually makes a representation possible “at the same time” in some reference frame?
It definitely isn't. The amount of information you can store in the universe is something like 10^120 bits. Even if I'm off by a trillion orders of magnitude it doesn't matter.
I want some easier to comprehend number for BB(6), in decimal notation. But it's such a massive number I would need to invent a new notation to express that. I love this new (to me) concept of tetration number representation. 10-million sub 10, what is the number?
Look at 3 sub 10 = which is (10^(10^10)). So that is 10 to the power of 10 billion. In regular decimal notation, that is a "1" with 10 billion "0"s following it. It takes 10 gigabytes of ram to represent the number in decimal notation, naively.
The number of atoms in the universe is only 10^80, or 1,000...000 (80 zeroes). 10-million sub 10 is so huge, how much ram to represent it.
>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.
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.)
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?
The "about" does a lot of heavy lifting in this example. Dividing 10,000,000_10 by the number of grains that fit into one universe doesn't change it much. The 10,000,000 would get smaller somewhere in the deep depths of the decimal fraction.
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)
The "first" link (after the home button) on bbchallenge is the header bar link to https://bbchallenge.org/story which cites Aaronson in the first sentence (double first!). I would not describe it like OP for someone trying to find the actual link ;)
"One Collatz Coincidence", the 2nd story on the blog, also mentions Aaronson
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.
The wording implies that Aaronson does not know what he's talking about.
>If you want to learn about actual Busy Beaver results [...]
This is saying there is no discussion of the results in the article, which is not true.
>Unlike Aaronson, he actually is on the forefront of Busy Beaver research [...]
This implies Aaronson has no (or lesser) authority on the subject and suggests we should listen to somebody else who purportedly has more.
Nowhere in @NooneAtAll3's comment is there an argument made against/for the contents of the article, an example of that would be:
"Aaronson mentions X but this is not correct because Y" or something along those lines.
Instead, the comment, in it's full extent, is either discrediting (perhaps unintentionally) and/or appealing to the authority of people involved. That's ad hominem.
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)
People 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?
[1] https://oeis.org/A333479
[2] https://oeis.org/A114852
[3] https://oeis.org/A107668
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-arrow^n, and up-arrow^f(n) for any computable f).
My gut feeling is that the growth between 47 million and 2^^2^^2^^9 is qualitatively larger than the growth between 2^^2^^2^^9 and graham's number in terms of how strong the operator we need is (with gramah's number being g_64 and g here being roughly one step "above" up_arrow^n). So probably we should have BB(7)>Graham's number.
Apologies if this feels adversarial, but I think your informal proof has an error, and I think I can explain it!
Your proof rests primarily on this assertion:
> BB has to grow faster than any computable sequence.
This is almost true! BB(n) has to grow faster than any computable sequence _defined by an n-state Turing machine_. That last part is really important. (Note that my restatement is probably incorrect too, it is just correct enough to point out the important flaw I saw in your statement). This means that up-arrow^f(n) _can_ be larger than BB(n) — up-arrow^f(n) is not restricted by a Turing machine at all. As an easy example, consider f(n) = BB(n)^2.
You may still be right about BB(7) being bigger than Graham’s number, even if your proof is not bulletproof
one of the things that does come out of BB is that BB(n)^2>>BB(n+c) for some very small constant c (I would be surprised if c>2)
Sure, but the example I'm providing is just meant to illustrate that BB(n) is not greater than arbitrary f(n). I'm not trying to provide the biggest number, I'm trying to illustrate that the sketched-out proof is incorrect. If you want me to provide a bigger number, I suppose another easy example is to define f(n) = BB(BB(n)).
Edit: Oh sorry, I see I misread the direction of your greater than signs. Leaving comments as-is though, hopefully that results in the least confusion
oops, my greater than signs are in the wrong direction. specifically, for any computable function f, there exists some constant c such that f(BB(n))<<BB(n+c)
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.
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 not based on whether it terminated.
The execution of the turing machine can be encoded in ZFC, so it really is the value of BB(748) that is the magic ingredient. Somehow even knowledge of the value of this finite number is a more potent axiomatic system than any we've developed.
You’d know the value in a more powerful system than ZFC (as it includes such an oracle) — but you can already reason about ZFC in a more powerful system.
We already have more powerful systems, but what causes the inability to self-reason is exactly that power: only first order logic can prove its own consistency. Once you get powerful enough to model arithmetic, you can build statements with self-referential weirdness.
I don’t see it as a paradox, but as growth: a sufficiently rich system can pose questions which suggest a richer system — and thereby scaffold up the universe hierarchy.
Does the fact that BB(k)=N is provable up to some k < 748 mean that all halting problems for machines with k states are answered by a proof in ZFC?
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.
If we assume ZFC to be consistent, then Gödel's 2nd incompleteness theorem tells us that it cannot prove its own consistency. So in particular it cannot prove than TM_ZFC_INC will never halt.
If you believe that ZF is consistent, then you believe that the machine cannot halt (assuming you trust its construction). But you cannot write a proof in ZF that the machine cannot halt. Such a proof must include a new axiom "ZF is consistent", or some stronger axiom.
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).
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.
Yeah, I’m quite familiar with Friedman’s work. I mentioned him and his Grand Conjecture in another comment.
> This ignores the fact that it is not so easy to find natural interesting statements that are independent of ZFC.
I’m not ignoring this fact—just observing that the sheer difficulty of the task seems to have encouraged mathematicians to pursue other areas of work beside foundational topics, which is a bit unfortunate in my opinion.
I agree most working mathematicians have limited interest in foundational topics. To me, that seems harmless enough.
> approximate those aspects of physical reality that are primarily relevant to the endeavors of humanity.
This is the comment that made me think that you were saying we needed more work on foundations for math as it is used in the sciences, and that doesn't match my understanding. Did I read it differently than you meant it?
> 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.
But why? Gödel's theorem does not depend on number of axioms but on them being recursively enumerable.
Right, Hilbert’s goal was (loosely speaking) to “find a finitely describable formal system” sufficient to “capture all truths”. When Gödel showed that can’t be done, that shouldn’t imply we just stop with the best theory we have so far and call it a day—it means there are an infinite number of more powerful theories (with necessarily longer minimal descriptions) waiting to be discovered.
In fact, both Gödel and Turing worked on this problem quite a bit. Gödel thought we might be able to find some sort of “meta-principle” that could guide us toward discovering an ever increasing hierarchy of more powerful axioms, and Turing’s work on ordinal progressions followed exactly this line of thinking as well. Feferman’s completeness theorem even showed that all arithmetical truths could be discovered via an infinite process. (Now of course this process is not finitely axiomatizable, but one can certainly extract some useful finite axioms out of it — the strength of PA after all is equivalent to the recursive iteration up to ε_0 of ‘Q_{n+1} = Q_n + Q_n is consistent’ where Q_0 is Robinson arithmetic).
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.
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.
Unfortunately no, ZFC isn't good enough to capture arithmetical truth. The problem is that there are nonstandard models of ZFC where every single model of second-order PA within is itself nonstandard. There are even models of ZFC where a certain specific computer program, known as the "universal algorithm" [1], solves the halting problem for all standard Turing machines.
https://jdh.hamkins.org/the-universal-algorithm-a-new-simple...
ZFC allows models of second order PA and proves that those models are all isomorphic. Within each model of ZFC there is no such thing as a nonstandard model of second order PA. One can only think it is nonstandard by looking from outside the model, no? What theorem of second order PA is ZFC unable to prove?
This is similar to how there are countable models of ZFC but those models think of themselves as uncountable. They are countable externally and not internally.
> It boggles my mind that a number (an uncomputable number, granted) like BB(748) can be "independent of ZFC".
It's BB(n) that is incomputable (that is there's no algorithm that outputs the value of BB(n) for arbitrary n).
BB(748) is computable. It's, by definition, a number of ones written by some Turing machine with 748 states. That is this machine computes BB(748).
> It feels like a category error or something.
The number itself is just a literally unimaginably large number. Independence of ZFC comes in when we try to prove that this number is the number we seek. And to do that you need theory more powerful than ZFC to capture properties of a Turing machine with 748 states.
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).
I think the more correct statement is that there are different models of ZFC in which BB(748) are different numbers. People find that weird because they don't think about non-standard models, as arguably they shouldn't.
Isn't that incompatible with the models being consistent?
Suppose model A proves BB(748) = X and model B proves BB(748) = Y > X. But presumably the models can interpret running all size 748 Turing machines for Y steps. Either one of the machines halts at step Y (forming a proof within A that BB(748) >= Y contradicting the assumed proof within A that BB(748) = X < Y) or none of the machines halts at step Y (forming a proof within B that BB(748) != Y contradicting the assumed proof within B that BB(748) = Y).
I'm guessing the only way this could ever work would be some kind of nastiness like X and Y aren't nailed down integers, so you can't tell if you've reached them or not, and somehow also there's a proof they aren't equal.
The issue is that X and Y are not actual natural numbers. They are mathematical objects that satisfy all the ZFC axioms and Peano arithmetic but are infinitely large. The issue is that ZFC underspecifies natural numbers.
How is that possible? That implies there’s at least one specific program whose execution changes based on the ZFC model. The rules of program execution are so simple, it doesn’t make sense that they’d change based on anything like that.
Because what it means to "halt in finite time" has different meanings in different models, because time is measured with different numbers.
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 halts from one that just hasn't halted yet (since it has an infinite number of states, you can't just wait for a loop).
So presumably the independence of a number from ZFC is like that also: you can't prove it's the value of BB(745) because you won't know if you've proved it; the only way to prove it is essentially to run those Turing machines until they stop and you'll never know if you're done.
I'm guessing that for the very small Turing machines there is not enough structure possible to encode whatever infinitely complex states end up being impossible to deduce halting from, so they end up being Collatz-like and then you can go prove things about them using math. As you add states the possible iteration steps go wild and eventually do stuff that is beyond ZFC to analyze.
So the finite value 745 isn't really where the infinity/uncomputability comes from-it comes from the infinite tape that can produce arbitrarily complex functions. (I wonder if over a certain number of states it becomes possible to encoding a larger Turing machine in the tape somehow, causing a sort of divergence to infinite complexity?)
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.
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
> What happens at whatever number it starts true at?
Usually, "what happens" is that the machines become large enough to represent a form of induction too strong for the axioms to 'reason' about. It's a function of the axioms of your theory, and you can add more axioms to stave it off, but of course you can't prove that your new axioms are consistent without even more axioms.
> 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.
Only insofar as you can put faith into the Church–Turing thesis to sort out all the technicalities of enumerating and verifying proofs. There still must be an encoding, just not the usual Gödel numbering.
> 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
Those are two very different ideas. Your second sentence says that Gödel's theorem is easy to prove if you have results about the halting problem. Your first one says that in order to prove Gödel's theorem, you need to establish results about the halting problem.
I'm saying that if you want to understand why Gödel's theorem is true, look at the one-paragraph proof based on the halting problem, not the like 20-page one with Gödel numbers.
Independence from ZFC means we can't prove that any given number is BB(643) using ZFC. It doesn't mean we can't prove it at all, e.g. one could use a stronger set theory like NBG which can prove the consistency of ZFC to verify the value of BB(643). But there would be some n for which BB(n) is independent of that set theory, requiring a yet-stronger theory, and so on ad infinitum.
ZF & ZFC are as important as they are because they're the weakest set theories capable of working as the foundations of mathematics that we've found. We can always add axioms, but taking axioms away & still having a usable theory on which to base mathematics is much more difficult.
> 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 for a loop).
> So presumably the independence of a number from ZFC is like that also: you can't prove it's the value of BB(745) because you won't know if you've proved it; the only way to prove it is essentially to run those Turing machines until they stop and you'll never know if you're done.
These aren't similar ideas. You can't know if a machine that hasn't halted yet will ever halt. But you can easily know if a machine that has already halted was going to halt.
Independence is the second case. For the value of BB(x) to be independent of ZFC, one of two things must hold:
(1) ZFC is inconsistent, and therefore all statements are independent of it.
(2) ZFC is consistent with two different statements, "BB(x) = a" and "BB(x) = b" for two different a, b. This means that a disproof of either statement cannot exist.
This, in turn, means that there is no observation you could ever make that would distinguish between the values a and b (for the identity of BB(x)). No matter what you believe the value of BB(x) might secretly be, there are no consequences; nothing anywhere could ever change if the value turned out to be different. Because, if there were an observable consequence of the value being different, the hypothetical observation of that consequence would be a disproof of the value that didn't cause it, and no such disproof can exist.
Neither value, a or b, can be more true than the other as the answer to the question "what is BB(x)?". It doesn't make sense to consider that question to have an answer at all.
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.
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".
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)!
To try and help people digging into this, the following helped me.
Two lenses for trying to understand this are potentially Chastain's limits on output of a lisp program being more complex than the program itself [1] or Markov's proof that you can't classify manifolds in d>= 4.
If you try the latter and need/want to figure out how the Russian school is so different this is helpful [2]
IMHO the former gives an intuition why, and the latter explains why IMHO.
In ZFC, C actually ends up implying PEM, which is why using constructionism as a form of reverse math helped it click for me .
This is because in the presence of excluded middle, every sequentially complete metric space is a complete space, and we tend to care about useful things, but for me just how huge the search space grows was hidden due to the typical (and useful) a priori assumption of PEM.
If you have a (in my view) dislike for the constrictive approach or don't want/have to invest in learning an obscure school of it, This recent paper[3] on the limits for finding a quantum theory of everything is another lens.
Yet another path is through Type 2 TMs and the Borel hierarchy, where while you can have a uncomputable number on the input tape you algorithms themselves cannot use them, while you can produce uncomputable numbers by randomly selecting and/or changing an infinite sequence.
Really it is the difference between expressability and algorithms working within what you can express.
Hopefully someone else can provide more accessible resources. I think a partial understanding of the limits of algorithms and computation will become more important in this new era.
[1] https://arxiv.org/abs/chao-dyn/9407003 [2] https://arxiv.org/abs/1804.05495 [3] https://arxiv.org/abs/2505.11773
Looking at [3], they seem to argue that the system isn’t complete for the usual Gödel reasons, which, sure, it isn’t, but then they call the claim that the system fails to decide, which is a statement about probability, a “scientific fact”. This seems to me like a mistake?
Like, a TOE is not expected to decide all statements expressible in the theory, only to predict particular future states from past states, with as much specificity as such past states actually determine the future states. It should not be expected to answer “given a physical setup where a Turing machine has been built, is there a time at which it halts?” but rather to answer “after N seconds, what state is the machine (as part of the physical system) in?” (for any particular choice of N).
Whether a particular statement expressed in the language of the theory is provable in the theory, is not a claim about the finite-time behavior of a physical system, unless your model of physics involves like, oracle machines or something like that.
Edit: it later says: “ Chaitin’s theorem states that there exists a constant K_{ℱ_{QG}} , determined by the axioms of ℱ_{QG} , such that no statement S with Kolmogorov complexity K(S) > K_{ℱ_{QG}} can be proven within ℱ_{QG} .”
But this, unless I’m badly misinterpreting it, seems very wrong? Most formal systems of interest have infinitely many distinct theorems. Given an infinite set of strings, there is no finite universal upper bound on the Kolmogorov complexity of the strings in that set.
Maybe this was just a typo or something?
They do then mention something about the Bekenstein bound, which I haven’t considered carefully yet but seems somewhat more promising than the parts of the article that preceded it.
I will admit that I added that cite mostly because of the very real barriers to even learning RUSS.
By the typos etc.. you. can probably also tell I was doing this on mobile, unfortunately as a passenger in a car.
To quote Chaitin’s explanation here:
> In contrast I would like to measure the power of a set of axioms and rules of inference. I would like to be able to say that if one has ten pounds of axioms and a twenty-pound theorem, then that theorem cannot be derived from those axioms.
This paper's notation does seem to be confusing, but I still think it is essentially complete with the above.
"K_{ℱ_{QG}}" would probably most commonly be L in most descriptions, a natural number that is the upper bound of complexity for provable statements in a formal system S
L is not a limit on complexity, it means that there is no formal proof for S that its Kolmogorov complexity exceeds L, for any string.
You can still prove that there are strings far more complex than L with S, and in fact there will often be far more of those strings than the ones equal to or less than L.
It is a limit on what you can prove about those strings with a greaterKolmogorov complexity in S.
Or to rewrite the above:
"There exists a natural number L such that we can't prove the Kolmogorov complexity of any specific string of bits is more than L."
Does that help or did I miss the mark on your objection?
It looks like the authors of [3] misunderstood Chaitin. What Chaitin said about the limits of provability is that no statements of the form "K(x) > c_F" can be proven in formal system F where c_F is some constant depending on F.
Let X = "1 if ZF is consistent, 0 otherwise". Then the statements "X = 0" and "X = 1" are independent of ZF. Whether the definition of X is a satisfactory definition of a particular number is a question of mathematical philosophy.
BB(748) is very similar, in that I'd call it a 'definition' independent of ZF rather than a 'number' independent of ZF.
No individual number is uncomputable. There’s no pair of a number and proof in ZFC that [that number] is the value of BB(748). And, so, there’s no program which ZFC proves to output the value of BB(748). There is a program that outputs BB(748) though, just like for any other number.
I think your mistake is your claim that BB(748) is a natural number. For you to know that, you would necessarily have to know an upper bound for the number of steps it takes for the BB-748 machine (whichever machine it is) to halt. But you definitely don't know that.
Related: It's incorrect to claim that each machine either halts or doesn't halt. To know that that dichotomy holds would require having a halting problem algorithm.
Individual numbers can be uncomputable! For example, take your favorite enumeration of Turing machines, (T1, T2...) and write down a real number in binary where the first bit is 0 if T1 halts and 1 otherwise, second bit is 0 if T2 halts... clearly this number is real and between 0 and 1, but it cannot be computed in finite time.
Pardon, I meant natural number. I should have specified.
If it had a finite size it would be computable.
BB(748) is a natural number, and _all_ natural numbers are computable.
It’s not “an uncomputable number”.
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...
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, and therefore, 100% of integers are equally just "mathematical concepts". That one of them is identified by BB(748) isn't a particularly important aspect. But certainly, a very specific number is identified by that designation, though nothing in this universe is going to know what it is in any meaningful sense.
This integer only exists if you assume classical logic. Otherwise, there is no such integer a priori, and actually there is none in general.
I'm fairly certain that's wrong, and I see a couple of other people may be making that mistake elsewhere in this conversation too. A Turing Machine is a Turing Machine. The execution trace of a Turing Machine is fully determined by its ruleset and its initial input. It doesn't matter which axioms you "take", nor does it matter what the intent of the initial construction of the 748-state machine was, or indeed even if that proof is somehow flawed. The definition of a Turing Machine is effectively the axiom set for this particular case. There is a finite set of 748-state Turing machines, and it is absolutely the case that there is a set of them that loop infinitely, the complementary set that do not, and that there is a maximum length amoung the set that do not. There is no situation where "the next step" of the Turing Machine "depends on your axioms" and could thereby be affected by such a decision.
For that to be the case, there would have to be some symbol under the tape and some state the machine is in for which the action the machine takes and the next state it goes to would depend on the axioms taken somehow. There is no place where the Turing Machine has somehow been running for so long and just gotten so large that its behavior becomes non-deterministic somehow.
What this means is that even if we lived in a universe where we had the unfathomable resources to actually have this number somehow meaningfully "in hand", we would be unable to prove that it was the correct one with just ZFC. Maybe one of the really quite numerous other machines still spinning away would in fact terminate in the future and be the real BB winner, because even this staggeringly monstrously large universe is still piddling nothing next to infinity and the other machines still require infinite resources to run them to discover they never terminate. But that doesn't do anything to affect whether or not there in fact is a single concrete integer that corresponds to BB(748).
Although one imagines that any universe with the resources to "have" BB(748) in it might also have some much more powerful axiom systems to play with in the process. The amount of computational power this universe apparently possesses is beyond all comprehension and who knows what they could know. But even if they used a more powerful system, it wouldn't change what BB(748) is... it just might affect whether or not they were correct about it.
> There is no situation where "the next step" of the Turing Machine "depends on your axioms" and could thereby be affected by such a decision.
That's easy, you just have to be an ultrafinitist, and say, "The definition of a TM presupposes an infinite set of natural numbers for time steps and tape configurations. But there aren't actually infinitely many natural numbers, infinitely long executions, arbitrarily long proofs, etc., outside of the formalism. If a formal statement and its negation do not differ regarding any natural numbers small enough to actually exist (in whatever sense), then neither is more true than the other." In particular, consistency statements may have no definite truth value, if the hypothetical proof of an inconsistency would be too large.
Of course, metamathematics tells us "you can't do that, in principle you could tell the lie if you wrote out the whole proof!" But that principle also presupposes the existence of arbitrarily-long proofs.
(Personally, hearing some of the arguments people make about BB numbers, I've become attracted to agnosticism toward ultrafinitist ideas.)
To be honest I'm not even particularly impressed by that line of reasoning because even if you accept ultrafinitism, there's still a definite integer that it corresponds to. You can deny the "existence" of integers, and thus that the number "exists", but that's contingent on your definition of "existence". It doesn't change what it would be if it did exist.
Plus, ultafinitism is essentially relative to the universe you find yourself in. I hypothesized a universe in which BB(748) could actually exist, but you can equally hypothesize ones in which not only can it exist, it exists comfortably and is considered a small number by its denizens. We can't conceive of such a thing but there's no particular a priori reason to suppose it couldn't exist. If such a universe does actually "exist" does that mean our ultrafinitism is wrong? I'm actually a sort of a proponent of knowing whether your operating in a math space that corresponds to the universe (see also constructive mathematics), but concretely declaring that nothing could possibly exist that doesn't fit into our universe is a philosophical statement, not a mathematical one.
> there's still a definite integer that it corresponds to.
The formalism says that there's still a definite integer that it corresponds to. The ultrafinitist would deny that the formalism keeps capturing truth past where we've verified it to be true, or some unknown distance farther.
> I hypothesized a universe in which BB(748) could actually exist, but you can equally hypothesize ones in which not only can it exist, it exists comfortably and is considered a small number by its denizens.
Sure, but the ultrafinitist would argue, "All this is still just a shallow hypothesis: you've said the words, but that's not enough to breathe much 'life' into the concept. It is but the simplest of approximations that can fit into our heads, and such large things (if they could exist) would likely have an entirely different nature that is incomprehensible to us."
> We can't conceive of such a thing but there's no particular a priori reason to suppose it couldn't exist.
That's why I wouldn't call myself an ultrafinitist, but would prefer an agnostic approach. There may be no great a priori reason to suppose it cannot exist, but I similarly do not see any such reason it must necessarily exist. We empirically notice that our formalism works for numbers small enough to work with, and we pragmatically round it off to "this formalism is true", but one could argue that surprising claims about huge numbers need stronger support than mere pragmatism.
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.
> 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.
> 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.
I'd say that's a bit of a wrong or misleading statement. I think the correct version is "everything[1] can be encoded as a number". The concept of number is a very particular concept! It's pretty absurd to say "a screwdriver is a number" or "a word is a number". That is true for the peano axiomatization of numbers; but to me in particular, I believe numbers are a generalization (and formalization) of the idea or concept of quantity. There's a particular idea that refers to say 'two' apples, the quantity of apples. A word is not a quantity, it's a different concept. Even though each of them could be encoded as a number somehow!
[1]: Everything that we believe to be finite and of interest, that is. We don't know presently anything that could be used in reality (a music, picture, etc.) that can't in principle be encoded as a large enough number.
I think this is quite interesting, because this encoding is critical, and it completes the system. You essentially need a machine to turn things into numbers and numbers into things; and this is unavoidable. You can actually encode this machine itself with numbers! This number (which encodes this transcoding machine) can even be decoded by its own machine! But we cannot actually avoid the machine itself, some actual realization in the real world, because any number, in order to represent something, can only be translated by one "machine" (which can be essentially a computer, or a mind, etc.).
Instead of thinking of machines, you can also think of conventions. So you can have a convention that say the number '5' encodes the concept 'word', or maybe it simply encodes the string of letters "word" ("w"+"o"+"r"+"d"). But the convention interpretation isn't complete, because you still need someone, or something, to interpret this convention in practice and potentially turn concepts into reality, or simply manipulate those concepts in significant and useful ways.
Some more examples: (1) you can encode objects by describing a series of solid operations, essentially CAD modelling, so you have numbers that represent solids. The machine that interprets this number and is able to translate it for example into a picture, a series of instructions to be interpreted by a 3d printer, of performs operations (inferences) about the relevant solid model (for example, a structural analysis) is your "machine", i.e. your software, without which a number, or string of bits by itself doesn't mean anything (except the quantity associated with that binary number, perhaps), and again this encoding or number is essentially arbitrary, it could be very different. (2) a JPEG file for example encodes an image that is read by a software stack (jpeg decoder+picture viewer+operating system+display driver) and forwarded to your monitor to be viewed as a pixel array. Again the string of bits associated with any image could in principle represent anything else representable.
Information (Shannon information in particular) simply implies the encoding possible.
It's really interesting that a lot of the time we are performing essentially translations between different representations of a thing: a series of bits into states of pixels on a screen (a picture), [a series of bits] into a 3d printed object, into a visualization of an object on a screen, etc. (one way), or a reading of a camera sensor (photograph) into a series of bits, a conception of an object (3d modelling), a conception of a story (writing), etc. (the other way). We of course can (and must for them to be built of course) conceptualize those "machines" themselves (e.g. the software part), represent them in some way (our encoding), and then turn this representation into a realization of those machines (a software, a piece of hardware, or just a representation convention, etc.).
In other words, the mind or computer itself is always an integral part of the process, and information in a vacuum doesn't represent anything necessarily.
Finally, most of what we do is some kind of translation, inference, and construction -- everything to assist our lives. Of course some "machines" are capable of generating new concepts, those are very interesting "machines" :)
> I'd say that's a bit of a wrong or misleading statement. I think the correct version is "everything[1] can be encoded as a number". The concept of number is a very particular concept! It's pretty absurd to say "a screwdriver is a number" or "a word is a number". That is true for the peano axiomatization of numbers; but to me in particular, I believe numbers are a generalization (and formalization) of the idea or concept of quantity. There's a particular idea that refers to say 'two' apples, the quantity of apples. A word is not a quantity, it's a different concept. Even though each of them could be encoded as a number somehow!
Well if we're using a more narrow view, then "BB(748)" isn't a number, it's an encoding of a partial algorithm. And it shouldn't be surprising that an algorithm might be unprovable in ZFC.
The actual number, the quantity, is quite easy to write down inside ZFC. And so is the beaver turing machine itself. The hard part is knowing which of the 748-state machines is the beaver.
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.
Let S be a statement. S is called semidecidible (also: Turing recognizable, most commonly "recursively enumerable", abbreviated as "r.e.", but I hate that one) if there is a Turing machine that halts if and only if S is true.
With this definition, we can say that "ZFC is inconsistent" is semidecidible: you run a program that searches for a contradiction.
The question BB(748) =/= 1000 is similarly semidecidable. You can run a program that will rule out 1000 if it is not BB(748).
So they are in the same "category", at least regarding their undecidability.
Also, if you turn "ZFC is consistent" into a number: {1 if ZFC is consistent; 0 if ZFC is inconsistent}, you will see, that BB(748) is not very much different, both are defined (well, equivalently) using the halting of Turing machines, or, the result of an infinite search.
As if numbers weren't merely mathematical concepts
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.
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...
For sqrt(2) I can tell you the order of magnitude and output as many digits as you want. I think that's plenty specific for this use case.
For zero I can not only do that, I can also count to it if you let me count both up and down, which seems like a very simple ask.
But that's the thing - each generation struggles with whether some new thing is a number. We're typically very inclusive, accepting imaginary numbers and even weirder things like surreal numbers, which we definitely can't count.
But as someone in this generation, I see a good argument for rejecting the big busy beaver numbers, which are provably outside of the realm of calculating with all the resources of our universe's runtime, from being fully accepted as numbers, any more than the first uninteresting number [0].
[0] https://en.wikipedia.org/wiki/Interesting_number_paradox
> For those tuning in from home, here BB(6) is the 6th Busy Beaver number, i.e. the maximum number of steps that a 6-state Turing machine with a {0,1} alphanet can take before halting, when run on an initially all-0 input tape.
Oh! Of course! That sure clears things up for this non-expert. This is clearly a hardcore blog for people who have been doing this kind of research for decades. Kind of awesome to stumble upon something so unapologetically dense and jargony and written for a very specific audience!
That should be enough for someone with an undergrad CS education to at least get a sense of what's going on if they haven't encountered the busy beaver problem before.
Is it niche jargon, absolutely, but to say it's only accessible to people who have put in decades is selling yourself short.
Hmm, interesting. It’s been 30 years since my engineering degree (not CS) and I’d have to look up what a Turing machine is. I think I remember one professor briefly mentioned it as “This is something the CS majors care deeply about but nobody else in the industry does.” Where I was, the CS degree was essentially a math degree dressed up in a hoodie.
The definition there is standard undergraduate computer science theory. Maybe not standard for software engineering though.
It's known that BB(14) is bigger than Graham's number, but this new finding leads me to believe that BB(7) is probably bigger than Graham's number. Intuitively, the technology required to go from pentation to Graham's number feels simpler than the technology required to go from `47,176,870` to `2 <pentate> 5`.
Thanks for sharing; your post would fit well as an answer to mine about Graham's number...
> 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.
I've seen it before, but it was using Knuth's up-arrow notation [1], which I like because it generalizes easily.
[1] https://en.wikipedia.org/wiki/Knuth's_up-arrow_notation
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 forever, that's called Hyperoperation. And yes, we did (probably) skip one, it's known as Successor-of and you were probably not explicitly shown this operator but it's the near end of that infinite succession.
When arithmetic is introduced just as a way to, for example, count money, it's more directly practical in the moment, but you're not seeing the larger pattern.
Don't forget identity. Its range is small but important!
Fair!
> 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 comparison.
Yes, that's right, dividing by that ratio essentially barely affects the number in a sense that 'adjacent' numbers in that notation give a much bigger change.
10↑↑10,000,000 / (sand grains per universe) is vastly larger than, say, 10↑↑9,999,999
So on system we're using to write these numbers, there's really no better way to write (very big)/ (only universally big) than by writing exactly that, and then in the notation for very big, it pretty much rounds to just (very big).
With tetration you're not dealing with orders of magnitude anymore, but orders of magnitude of orders of magnitude.
Exactly. This number is so so much bigger than 10^100000 or however many grains of sand would fit, that dividing by that amount doesn’t really change it, certainly not enough to bring it down closer to 9,999,999sub10
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.
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.
True but this is a ratio.
However many universes in question, there is a qualitative difference between that many empty universes (with 1 grain), and that many completely packed with grain.
Ask anybody who lives in one!
So what is the richest logic whose proofs can be enumerated with only a five state TM?
That entirely depends on how you want to interpret a finite binary string as an enumeration of logic proofs?!
Any time I see such results from computation complexity theory, I realize that any current zeitgeist of "super-intelligent AI are gods" is complete bullshit.
You can convert every atom of observable Universe into a substrate for supercomputer, you can harness energies of supermassive black holes to power it, but running a humble BB(6) to halting state would be forever out of its reach.
That strawman never stood a chance.
I wonder if the visible universe is large enough to write down the exact value of BB(6).
If you treat the observable universe as a closed system, you could try to apply the Bekenstein bound using - R ≈ 46.5 billion light-years (radius of the observable universe) - E ≈ total mass-energy content of the observable universe
The mass-energy includes ordinary matter, dark matter, and dark energy. Current estimates suggest the observable universe contains roughly 10^53 kg of mass-energy equivalent.
Plugging these into S ≤ 2πER/ℏc gives someting on the order of 10^120 bits of maximum information content.
S ≤ 2πER/ℏc
S ≤ (2 × 3.141593 × 3.036e+71 × 4.399e+26)/(1.055e-34 × 299792458)
S ≤ 2.654135e+124
S ≤ 10^120
So, no.
You’re probably referring to a state where all parts of the complete representation exist at the same time. Because if they don’t have to exist at the same time, then it might be possible to “write it down” if the universe has unbounded duration (“might” because I don’t know how the heat death plays into that). However, “at the same” time isn’t well-defined in relativistic spacetime. The sibling comments are definitely right with respect to the reference frame implied by the CMB. But I’m wondering if it wouldn’t be possible to slice spacetime in a way that actually makes a representation possible “at the same time” in some reference frame?
It definitely isn't. The amount of information you can store in the universe is something like 10^120 bits. Even if I'm off by a trillion orders of magnitude it doesn't matter.
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.
It's not.
I want some easier to comprehend number for BB(6), in decimal notation. But it's such a massive number I would need to invent a new notation to express that. I love this new (to me) concept of tetration number representation. 10-million sub 10, what is the number?
Look at 3 sub 10 = which is (10^(10^10)). So that is 10 to the power of 10 billion. In regular decimal notation, that is a "1" with 10 billion "0"s following it. It takes 10 gigabytes of ram to represent the number in decimal notation, naively.
The number of atoms in the universe is only 10^80, or 1,000...000 (80 zeroes). 10-million sub 10 is so huge, how much ram to represent it.
This example is from https://www.statisticshowto.com/tetration-function-simple-de...
>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.
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.)
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.
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?
The "about" does a lot of heavy lifting in this example. Dividing 10,000,000_10 by the number of grains that fit into one universe doesn't change it much. The 10,000,000 would get smaller somewhere in the deep depths of the decimal fraction.
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?
I don’t get it. What’s wrong with the post? And https://arxiv.org/abs/1605.04343 is interesting, no?
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)
The "first" link (after the home button) on bbchallenge is the header bar link to https://bbchallenge.org/story which cites Aaronson in the first sentence (double first!). I would not describe it like OP for someone trying to find the actual link ;)
"One Collatz Coincidence", the 2nd story on the blog, also mentions Aaronson
>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.
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.
The wording implies that Aaronson does not know what he's talking about.
>If you want to learn about actual Busy Beaver results [...]
This is saying there is no discussion of the results in the article, which is not true.
>Unlike Aaronson, he actually is on the forefront of Busy Beaver research [...]
This implies Aaronson has no (or lesser) authority on the subject and suggests we should listen to somebody else who purportedly has more.
Nowhere in @NooneAtAll3's comment is there an argument made against/for the contents of the article, an example of that would be:
"Aaronson mentions X but this is not correct because Y" or something along those lines.
Instead, the comment, in it's full extent, is either discrediting (perhaps unintentionally) and/or appealing to the authority of people involved. That's ad hominem.
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)
>ex. "if you want the actual news, read Tucker, not Krugman" isn't an ad hominem towards Krugman.
But how you justify that could be one. If you are just attacking the person instead of their reporting I would call that ad hominem.