12 ms·

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.

eapriv 1y ago
It’s not “an uncomputable number”.
ChadNauseam 1y ago
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).
- Straw 1y ago
  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.
  - ajkjk 1y ago
    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?)
    - lupire 1y ago
      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 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.
      - ajkjk 1y ago
        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 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".
    - dtech 1y ago
  - thechao 1y ago
    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)!
  - vhcr 1y ago
    Nobody can give you that number, because it's way bigger than what can be represented in the universe.
- bo1024 1y ago
  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.
  - deleted 1y ago
    [deleted]
  - Strilanc 1y ago
    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.
    - Kranar 1y ago
      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.
  - wat10000 1y ago
    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.
    - bo1024 1y ago
      Because what it means to "halt in finite time" has different meanings in different models, because time is measured with different numbers.
- nyrikki 1y ago
  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 https://arxiv.org/abs/chao-dyn/9407003 [2] https://arxiv.org/abs/1804.05495 https://arxiv.org/abs/1804.05495 [3] https://arxiv.org/abs/2505.11773 https://arxiv.org/abs/2505.11773
  - drdeca 1y ago
    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.
Straw 1y ago
The category error is in thinking that BB(748) is in fact, a number. It's merely a mathematical concept.
- Almondsetat 1y ago
  As if numbers weren't merely mathematical concepts
- jerf 1y ago
  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.
  - perthmad 1y ago
    This integer only exists if you assume classical logic. Otherwise, there is no such integer a priori, and actually there is none in general.
    - nyssos 1y ago
      Classical logic is the presumed default for mathematics, if someone is working in a different system they will say so explicitly.
      - gylterud 1y ago
        Pondering mathematical objects such as BB(n) is exactly the kind of stuff which rooks one’s faith in classical logic.
    - 1y ago
Xcelerate 1y ago
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).
- azan_ 1y ago
  > 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.
  - tliltocatl 1y ago
    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.
    - azan_ 1y ago
      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?
      - 1y ago
tromp 1y ago
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.
- Scarblac 1y ago
  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.
  - tromp 1y ago
    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.
  - LegionMammal978 1y ago
    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.
- Diggsey 1y ago
  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.
LegionMammal978 1y ago
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.
drdeca 1y ago
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.
- boothby 1y ago
  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.
  - Vecr 1y ago
    If it had a finite size it would be computable.
  - drdeca 1y ago
    Pardon, I meant natural number. I should have specified.
  - Scarblac 1y ago
    That's a number in R, obviously most of them are uncomputable (there is a countable number of Turing machines). But for every natural number n there is a trivial Turing machine that just prints n and then halts.
- cvoss 1y ago
  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.
  - 1y ago
bo1024 1y ago
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_arithmetic https://en.wikipedia.org/wiki/Non-standard_model_of_arithmet...
- bo1024 1y ago
  I would edit my last line to say: weird models of numbers that don't match how we think "halts in finite steps" usually works.
red75prime 1y ago
> 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.
LPisGood 1y ago
BB(748) is a natural number, and _all_ natural numbers are computable.
- ted_dunning 1y ago
  There is definitely a function f such that f() = n for all n ∈ ℕ. But there is also a function g that you cannot prove whether g() = n. Important distinction. This means that somebody could claim that the value of BB(748) = n but you cannot be sure if they are correct (but you might be able to show they are wrong).
throwaway81523 1y ago
The truth value of the continuum hypothesis is either 1 or 0 (at least from a platonistic perspective). But, it is proven to be independent of ZFC. No huge numbers involved, just a single bit whose value ZFC doesn't tell you.
deleted 1y ago
[deleted]

eapriv 1y ago

It’s not “an uncomputable number”.

ChadNauseam 1y ago

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).

Straw 1y ago
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.
- ajkjk 1y ago
  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?)
  - lupire 1y ago
    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 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.
    - ajkjk 1y ago
      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 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".
  - dtech 1y ago
- thechao 1y ago
  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)!
- vhcr 1y ago
  Nobody can give you that number, because it's way bigger than what can be represented in the universe.
bo1024 1y ago
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.
- deleted 1y ago
  [deleted]
- Strilanc 1y ago
  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.
  - Kranar 1y ago
    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.
- wat10000 1y ago
  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.
  - bo1024 1y ago
    Because what it means to "halt in finite time" has different meanings in different models, because time is measured with different numbers.
nyrikki 1y ago
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 https://arxiv.org/abs/chao-dyn/9407003 [2] https://arxiv.org/abs/1804.05495 https://arxiv.org/abs/1804.05495 [3] https://arxiv.org/abs/2505.11773 https://arxiv.org/abs/2505.11773
- drdeca 1y ago
  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.

Straw 1y ago

The category error is in thinking that BB(748) is in fact, a number. It's merely a mathematical concept.

Almondsetat 1y ago
As if numbers weren't merely mathematical concepts
jerf 1y ago
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.
- perthmad 1y ago
  This integer only exists if you assume classical logic. Otherwise, there is no such integer a priori, and actually there is none in general.
  - nyssos 1y ago
    Classical logic is the presumed default for mathematics, if someone is working in a different system they will say so explicitly.
    - gylterud 1y ago
      Pondering mathematical objects such as BB(n) is exactly the kind of stuff which rooks one’s faith in classical logic.
  - 1y ago

Xcelerate 1y ago

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).

azan_ 1y ago
> 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.
- tliltocatl 1y ago
  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.
  - azan_ 1y ago
    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?
    - 1y ago

tromp 1y ago

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.

Scarblac 1y ago
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.
- tromp 1y ago
  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.
- LegionMammal978 1y ago
  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.
Diggsey 1y ago
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.

LegionMammal978 1y ago

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.

drdeca 1y ago

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.

boothby 1y ago
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.
- Vecr 1y ago
  If it had a finite size it would be computable.
- drdeca 1y ago
  Pardon, I meant natural number. I should have specified.
- Scarblac 1y ago
  That's a number in R, obviously most of them are uncomputable (there is a countable number of Turing machines). But for every natural number n there is a trivial Turing machine that just prints n and then halts.
cvoss 1y ago
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.
- 1y ago

bo1024 1y ago

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_arithmetic https://en.wikipedia.org/wiki/Non-standard_model_of_arithmet...

bo1024 1y ago
I would edit my last line to say: weird models of numbers that don't match how we think "halts in finite steps" usually works.

red75prime 1y ago

> 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.

LPisGood 1y ago

BB(748) is a natural number, and _all_ natural numbers are computable.

ted_dunning 1y ago
There is definitely a function f such that f() = n for all n ∈ ℕ. But there is also a function g that you cannot prove whether g() = n. Important distinction. This means that somebody could claim that the value of BB(748) = n but you cannot be sure if they are correct (but you might be able to show they are wrong).

throwaway81523 1y ago

The truth value of the continuum hypothesis is either 1 or 0 (at least from a platonistic perspective). But, it is proven to be independent of ZFC. No huge numbers involved, just a single bit whose value ZFC doesn't tell you.

deleted 1y ago

[deleted]