4 ms·

Note that this bound has since been improved to 748 [1] and you can actually view and run this 748 state turing machine here [2]. This comment on reddit [3] is

by v64 5y ago

Note that this bound has since been improved to 748 [1] and you can actually view and run this 748 state turing machine here [2]. This comment on reddit [3] is a good attempt at condensing all the information down and explaining why this means proving the value of BB(748) is independent from ZFC. [1] https://scottaaronson.blog/?p=4916 https://scottaaronson.blog/?p=4916 [2] https://turingmachinesimulator.com/shared/vgimygpuwi https://turingmachinesimulator.com/shared/vgimygpuwi [3] https://www.reddit.com/r/math/comments/gdfes1/a_turing_machine_that_halts_iff_zfc_is/fpi0sjs/ https://www.reddit.com/r/math/comments/gdfes1/a_turing_machi...

H8crilA 5y ago
Sorry for a low quality/content comment, but this area has always seemed to me the most beautiful part of mathematics (not just theoretical computer science). The joke about robot overlords still pondering on BB(<low double digit number>) billions of years into the future is a good summary of this feeling :)
- v64 5y ago
  Even calculating BB(30) exhaustively would require more energy than we have in the observable universe. The fact that functions like BB() have actual, finite values, but that they're unknowable both due to our physical and logical limitations, is humbling in an ineffable way.
  - stouset 5y ago
    By physical limitations, we also include space. If you could represent each digit of Graham’s number (G_64) in a Planck volume, you couldn’t fit even an incomprehensibly tiny fraction of it in the observable universe. No only that, but the number of digits in G_64 (~log10(G_64)) exceeds the number of Planck volumes (V_p) in our universe too. As does the number of digits in that number (~log10^2(G_64)). And so on and so on, for a number of times itself exceeding the number of Planck volumes in the universe. P_v ~ 4.65e185 P_v < G_64 P_v < log10(G_64) P_v < log10^(2)(G_64) … P_v < log10^(P_v)(G_64) And yet G_64 < BB(18) We don’t yet know if it exceeds BB(17). That said, we can grow bigger still. Scott Aaron defined a closely-related concept called a Beeping Busy Beaver that grows uncomputably even if we had an oracle for BB(n). That is, even if we had access to a magic genie that could tell us any BB(n), this function BBB(n) even still grows uncomputably. It’s almost as if there’s “sizes” of uncomputability much the same as there are distinct sizes of infinity.
    - tromp 5y ago
      > We don’t yet know if it exceeds BB(17). We don't know if it exceeds BB(5) either, do we? In the functional realm [1], we know: BB_λ(36) < 5 * G_64 + 6 <= BB_λ(114) Note that these are measured in bits, and that it would take 18 * 2 * (2 + ceil(log(18))) = 252 bits to represent the 18-state TM computing G_64. The 847 state TM whose halting is known to be unprovable in ZFC takes 847 * 2 * (2 + ceil(log(847)) = 20328 bits to describe. Meanwhile, in a mere 215 bits, we can encode a Laver table program [2] whose halting is not known to be provable in ZFC [3]. I.e. it may or may not be unprovable, we don't know yet. [1] https://oeis.org/A333479 https://oeis.org/A333479 [2] https://github.com/tromp/AIT/blob/master/laver.lam https://github.com/tromp/AIT/blob/master/laver.lam [3] https://codegolf.stackexchange.com/questions/79620/laver-tab https://codegolf.stackexchange.com/questions/79620/laver-tab...
      - deleted 5y ago
        [deleted]
    - Sharlin 5y ago
      > It’s almost as if there’s “sizes” of uncomputability much the same as there are distinct sizes of infinity. There is, isn't there? A TM plus an oracle can solve the halting problem for the original TM but is just as susceptible to a halting problem of its own, and this goes on ad infinitum.
- actually_a_dog 5y ago
  This very much reminds me of the following story told by Joel Spencer regarding Ramsey numbers[0]: > Erdős asks us to imagine an alien force, vastly more powerful than us, landing on Earth and demanding the value of R(5, 5) or they will destroy our planet. In that case, he claims, we should marshal all our computers and all our mathematicians and attempt to find the value. But suppose, instead, that they ask for R(6, 6). In that case, he believes, we should attempt to destroy the aliens. [1] Although Ramsey numbers are computable, they are really, really hard to compute exactly, and we don't have great upper or lower bounds for them, either. Edit: I found the version of the story that I was more familiar with that had a 1 year time limit on it[2]: > Suppose aliens invade the earth and threaten to obliterate it in a year's time unless human beings can find the Ramsey number for red five and blue five. We could marshal the world's best minds and fastest computers, and within a year we could probably calculate the value. If the aliens demanded the Ramsey number for red six and blue six, however, we would have no choice but to launch a preemptive attack. --- [0]: https://en.wikipedia.org/wiki/Ramsey%27s_theorem https://en.wikipedia.org/wiki/Ramsey%27s_theorem [1]: https://en.wikipedia.org/wiki/Ramsey%27s_theorem#Computational_complexity https://en.wikipedia.org/wiki/Ramsey%27s_theorem#Computation... [2]: https://blogs.scientificamerican.com/roots-of-unity/moores-law-and-ramsey-numbers/ https://blogs.scientificamerican.com/roots-of-unity/moores-l...
- galaxyLogic 5y ago
  > The joke about robot overlords still pondering on BB This starts to sound like Hitchhiker's Guide to Galaxy. I always thought the answer 42 was just an absurd joke but now I'm starting to think that Douglas Adams must have known about Busy Beaver.
  - perl4ever 5y ago
    The word on this, I believe, is: 'The first strong law of small numbers (Gardner 1980, Guy 1988, 1990) states "There aren't enough small numbers to meet the many demands made of them." The second strong law of small numbers (Guy 1990) states that "When two numbers look equal, it ain't necessarily so."' '...the first few values of the interpolating polynomial (n^4-6n^3+23n^2-18n+24)/24 (erroneously given in Guy (1990) with a coefficient 24 instead of 23) for n=1, 2, ... are 1, 2, 4, 8, 16, .... Thus, the polynomial appears to give the powers of 2, but then continues 31, 57, 99, ... (OEIS A000127). In fact, this sequence gives the maximal number of regions obtained by joining n points around a circle by chords' https://mathworld.wolfram.com/StrongLawofSmallNumbers.html https://mathworld.wolfram.com/StrongLawofSmallNumbers.html
dandanua 5y ago
That reddit comment is very nice, though a little bit misleading at the end. > I can define this finite integer with only 7 characters, BB(748), but it can't be computed at all! is not true. The correct value of BB(748) can't be proved in ZFC, that's true. But we can use a stronger theory. For example, we can take the statement that ZFC is consistent, denoted by Con(ZFC), and add it to ZFC. The new theory ZFC+Con(ZFC) is stronger. So, it could be that ZFC+Con(ZFC) can prove BB(748). If necessary, we can consider even stronger theory, e.g. ZFC+Con(ZFC)+Con(ZFC+Con(ZFC)).
- danielheath 5y ago
  Computability is not the same thing as proof. “Not computable” means “no program which is known to halt can answer this”.
  - dandanua 5y ago
    No, "not computable" is a property of functions that can accept infinite number of inputs. We can't say that a particular function value is uncomputable, there is no such definition. BB is uncomputable as a function. Yet, we can prove some of its values, because we can prove that some small Turing machines are not halting. To show that something runs forever you have to prove it.
    - singularity2001 5y ago
      The reddit edit is a bit misleading, your answer clarified the situation, thanks. But wouldn't the program BB(n){ if(n==748) return bb_748 else ... } be a computable emulation?
      - codeflo 5y ago
        First, programs are defined to be finite in length. Second, for a program to be said to compute a function, it must do so for all possible inputs. That’s by definition, but there are good reasons why these definitions are useful: if we accept infinite or incomplete programs, everything would be considered computable. Anyway, your program can only compute BB for a finite number of inputs (depending on how far you bother to expand the “else …” part).
SilasX 5y ago
If you already know the background knowledge, the Reddit comment’s key point is: There’s a 748-state Turing machine that (is isomorphic to a program that) grinds out all the provable theorems of ZFC and halts if it proves contradictory theorems. Calculating BB(748) under ZFC requires proving that this program never halts, which would double as a proof of ZFC’s — and therefore its own — consistency. By Gödel’s Incompleteness, you can’t do that (as a system can’t prove it’s own consistency).

by v64 5y ago

H8crilA 5y ago

Sorry for a low quality/content comment, but this area has always seemed to me the most beautiful part of mathematics (not just theoretical computer science). The joke about robot overlords still pondering on BB(<low double digit number>) billions of years into the future is a good summary of this feeling :)

v64 5y ago
Even calculating BB(30) exhaustively would require more energy than we have in the observable universe. The fact that functions like BB() have actual, finite values, but that they're unknowable both due to our physical and logical limitations, is humbling in an ineffable way.
- stouset 5y ago
  By physical limitations, we also include space. If you could represent each digit of Graham’s number (G_64) in a Planck volume, you couldn’t fit even an incomprehensibly tiny fraction of it in the observable universe. No only that, but the number of digits in G_64 (~log10(G_64)) exceeds the number of Planck volumes (V_p) in our universe too. As does the number of digits in that number (~log10^2(G_64)). And so on and so on, for a number of times itself exceeding the number of Planck volumes in the universe. P_v ~ 4.65e185 P_v < G_64 P_v < log10(G_64) P_v < log10^(2)(G_64) … P_v < log10^(P_v)(G_64) And yet G_64 < BB(18) We don’t yet know if it exceeds BB(17). That said, we can grow bigger still. Scott Aaron defined a closely-related concept called a Beeping Busy Beaver that grows uncomputably even if we had an oracle for BB(n). That is, even if we had access to a magic genie that could tell us any BB(n), this function BBB(n) even still grows uncomputably. It’s almost as if there’s “sizes” of uncomputability much the same as there are distinct sizes of infinity.
  - tromp 5y ago
    > We don’t yet know if it exceeds BB(17). We don't know if it exceeds BB(5) either, do we? In the functional realm [1], we know: BB_λ(36) < 5 * G_64 + 6 <= BB_λ(114) Note that these are measured in bits, and that it would take 18 * 2 * (2 + ceil(log(18))) = 252 bits to represent the 18-state TM computing G_64. The 847 state TM whose halting is known to be unprovable in ZFC takes 847 * 2 * (2 + ceil(log(847)) = 20328 bits to describe. Meanwhile, in a mere 215 bits, we can encode a Laver table program [2] whose halting is not known to be provable in ZFC [3]. I.e. it may or may not be unprovable, we don't know yet. [1] https://oeis.org/A333479 https://oeis.org/A333479 [2] https://github.com/tromp/AIT/blob/master/laver.lam https://github.com/tromp/AIT/blob/master/laver.lam [3] https://codegolf.stackexchange.com/questions/79620/laver-tab https://codegolf.stackexchange.com/questions/79620/laver-tab...
    - deleted 5y ago
      [deleted]
  - Sharlin 5y ago
    > It’s almost as if there’s “sizes” of uncomputability much the same as there are distinct sizes of infinity. There is, isn't there? A TM plus an oracle can solve the halting problem for the original TM but is just as susceptible to a halting problem of its own, and this goes on ad infinitum.
actually_a_dog 5y ago
This very much reminds me of the following story told by Joel Spencer regarding Ramsey numbers[0]: > Erdős asks us to imagine an alien force, vastly more powerful than us, landing on Earth and demanding the value of R(5, 5) or they will destroy our planet. In that case, he claims, we should marshal all our computers and all our mathematicians and attempt to find the value. But suppose, instead, that they ask for R(6, 6). In that case, he believes, we should attempt to destroy the aliens. [1] Although Ramsey numbers are computable, they are really, really hard to compute exactly, and we don't have great upper or lower bounds for them, either. Edit: I found the version of the story that I was more familiar with that had a 1 year time limit on it[2]: > Suppose aliens invade the earth and threaten to obliterate it in a year's time unless human beings can find the Ramsey number for red five and blue five. We could marshal the world's best minds and fastest computers, and within a year we could probably calculate the value. If the aliens demanded the Ramsey number for red six and blue six, however, we would have no choice but to launch a preemptive attack. --- [0]: https://en.wikipedia.org/wiki/Ramsey%27s_theorem https://en.wikipedia.org/wiki/Ramsey%27s_theorem [1]: https://en.wikipedia.org/wiki/Ramsey%27s_theorem#Computational_complexity https://en.wikipedia.org/wiki/Ramsey%27s_theorem#Computation... [2]: https://blogs.scientificamerican.com/roots-of-unity/moores-law-and-ramsey-numbers/ https://blogs.scientificamerican.com/roots-of-unity/moores-l...
galaxyLogic 5y ago
> The joke about robot overlords still pondering on BB This starts to sound like Hitchhiker's Guide to Galaxy. I always thought the answer 42 was just an absurd joke but now I'm starting to think that Douglas Adams must have known about Busy Beaver.
- perl4ever 5y ago
  The word on this, I believe, is: 'The first strong law of small numbers (Gardner 1980, Guy 1988, 1990) states "There aren't enough small numbers to meet the many demands made of them." The second strong law of small numbers (Guy 1990) states that "When two numbers look equal, it ain't necessarily so."' '...the first few values of the interpolating polynomial (n^4-6n^3+23n^2-18n+24)/24 (erroneously given in Guy (1990) with a coefficient 24 instead of 23) for n=1, 2, ... are 1, 2, 4, 8, 16, .... Thus, the polynomial appears to give the powers of 2, but then continues 31, 57, 99, ... (OEIS A000127). In fact, this sequence gives the maximal number of regions obtained by joining n points around a circle by chords' https://mathworld.wolfram.com/StrongLawofSmallNumbers.html https://mathworld.wolfram.com/StrongLawofSmallNumbers.html

dandanua 5y ago

That reddit comment is very nice, though a little bit misleading at the end. > I can define this finite integer with only 7 characters, BB(748), but it can't be computed at all! is not true. The correct value of BB(748) can't be proved in ZFC, that's true. But we can use a stronger theory. For example, we can take the statement that ZFC is consistent, denoted by Con(ZFC), and add it to ZFC. The new theory ZFC+Con(ZFC) is stronger. So, it could be that ZFC+Con(ZFC) can prove BB(748). If necessary, we can consider even stronger theory, e.g. ZFC+Con(ZFC)+Con(ZFC+Con(ZFC)).

danielheath 5y ago
Computability is not the same thing as proof. “Not computable” means “no program which is known to halt can answer this”.
- dandanua 5y ago
  No, "not computable" is a property of functions that can accept infinite number of inputs. We can't say that a particular function value is uncomputable, there is no such definition. BB is uncomputable as a function. Yet, we can prove some of its values, because we can prove that some small Turing machines are not halting. To show that something runs forever you have to prove it.
  - singularity2001 5y ago
    The reddit edit is a bit misleading, your answer clarified the situation, thanks. But wouldn't the program BB(n){ if(n==748) return bb_748 else ... } be a computable emulation?
    - codeflo 5y ago
      First, programs are defined to be finite in length. Second, for a program to be said to compute a function, it must do so for all possible inputs. That’s by definition, but there are good reasons why these definitions are useful: if we accept infinite or incomplete programs, everything would be considered computable. Anyway, your program can only compute BB for a finite number of inputs (depending on how far you bother to expand the “else …” part).

SilasX 5y ago

If you already know the background knowledge, the Reddit comment’s key point is: There’s a 748-state Turing machine that (is isomorphic to a program that) grinds out all the provable theorems of ZFC and halts if it proves contradictory theorems. Calculating BB(748) under ZFC requires proving that this program never halts, which would double as a proof of ZFC’s — and therefore its own — consistency. By Gödel’s Incompleteness, you can’t do that (as a system can’t prove it’s own consistency).