8 ms·

The 8000th Busy Beaver number eludes ZF set theory (2016)

114 points by jkubicek 3y ago

jkubicek 3y ago
Adam Yedidia had a claim to fame other than being SBF’s roommate.
vecter 3y ago
FTA this is an interesting tidbit about Busy Beavers: But the BB function has a second amazing property: namely, it’s a perfectly well-defined integer function, and yet once you fix the axioms of mathematics, only finitely many values of the function can ever be proved, even in principle. To see why, consider again a Turing machine M that halts if and only if there’s a contradiction in ZF set theory. Clearly such a machine could be built, with some finite number of states k. But then ZF set theory can’t possibly determine the value of BB(k) (or BB(k+1), BB(k+2), etc.), unless ZF is inconsistent! For to do so, ZF would need to prove that M ran forever, and therefore prove its own consistency, and therefore be inconsistent by Gödel’s Theorem.
- adverbly 3y ago
  > consider again a Turing machine M that halts if and only if there’s a contradiction in ZF set theory. Clearly such a machine could be built, with some finite number of states k. I am a small brain here. How is this so clear?
  - _a_a_a_ 3y ago
    Because it says 'clearly'. (but yeah, agree with you)
  - meithecatte 3y ago
    Checking whether a string of bits encodes a proof of False in ZF is decidable. Now enumerate the bitstrings and check each.
    - klyrs 3y ago
      > and check each. "Now, draw the rest of the owl." Not saying you're wrong, just, this jump is super non-obvious even to most mathematicians.
      - CaptainNegative 3y ago
        If you can check any given bitstring for whether it encodes a valid ZFC proof of the (in)consistency of ZFC in finite time, then you can write a program to enumerate over all possible bit strings in shortlex order and halt the first time you see a valid proof.
    - WindyLakeReturn 3y ago
      There are infinite many such strings, so that alone can't be used to prove the Turing machine of k states can check all strings. So that leaves open the original question, how do we know that a Turing machine of k states is able to have one of the stated outcomes for any possible bit string?
      - nyssos 3y ago
        > There are infinite many such strings And they can be enumerated by a finite program. For example, in lazily evaluated pseudocode: bits = ["0", "1"] bitstrings = bits + [(bit + suffix for bit in bits) for suffix in bitstrings]
  - tomstuart 3y ago
    I wouldn’t defend the idea that it’s “clear”, but the idea is to build a machine that combines the axioms of ZF set theory in all possible ways to generate all possible conclusions, checking each one for contradiction as it goes. If it never generates a contradictory conclusion from those axioms, it’ll run forever.
    - ijustlovemath 3y ago
      This sounds like it relies on the halting problem, or maybe the other way around? Really interesting stuff, been a while since I read about a higher level math topic and been able to sorta kinda understand the "quanta-level" summaries out there
      - jtolmar 3y ago
        The Nth Busy Beaver number lets you solve the halting problem for Turing Machines up to size N. Only a handful of them are known, for very small N, and they increase incredibly rapidly. For the most common version of the problem (S for 2-symbol machines), they go: 1, 6, 21, 107, some number greater than or equal to 47176870, and some number greater than 10⇈15 (that's up arrow notation on the last one).
        ijustlovemath 3y ago
        Ooh, are they basically the number of possible turing programs encodable in a state of N?
        readams 3y ago
        It's the maximum amount of time a Turing machine of size N can run. So if you want to know whether a Turning machine of size N or less will halt, just run it for BB(N) steps. If it hasn't halted by then, it never will.
    - stouset 3y ago
      I think the part that eludes me here is that it's not clear that such a Turing machine could be built from a finite number of states.
tromp 3y ago
Previously discussed at https://news.ycombinator.com/item?id=36658506 https://news.ycombinator.com/item?id=36658506 Quoting from https://scottaaronson.blog/?p=7388 https://scottaaronson.blog/?p=7388 : > Johannes Riebel, an undergraduate at the University of Augsburg in Germany, has produced a tour-de-force bachelor’s thesis that contains, among other things, the first careful writeup of Stefan O’Rear’s result from six years ago that the value of BB(748) is independent of the ZFC axioms of set theory. Regular readers might recall that O’Rear’s result substantially improved over the initial result by me and Adam Yedidia, which showed the value of BB(8000) independent of ZFC assuming the consistency of a stronger system. Along the way, Riebel even gets a tiny improvement, showing that BB(745) independent of ZFC.
- arethuza 3y ago
  BB(748) - BB(745) is probably the largest value that anyone has ever described as "tiny" :-)
  - danbruc 3y ago
    I would assume tiny refers to three.
    - TheRealNGenius 3y ago
      [dead]
  - sebzim4500 3y ago
    It's actually really hard to come up with an interesting lower bound that value. IIRC no one has proven that BB(n) + 1 < BB(n + 1) for large 2
    - kevinventullo 3y ago
      Hm, is there some way to “concatenate” Turing machines which would let you prove something like BB(n) + BB(m) <= BB(n+m+c) for some fixed c independent of n and m?
cyberax 3y ago
These theses are technically very complicated, but what they do is actually easy to explain: they construct a short "program" that basically enumerates all possible statements and checks their validity. And then terminates if it detects a contradiction. A program that checks the axioms of Peano arithmetic, or of ZF set theory is undecidable, we know that from Gödel's incompleteness theorems. So then it becomes a sort of competition: who can write the shortest Turing machine that encodes that program. Kinda like a demo-scene for mathematicians.
- henry2023 3y ago
  This is a great summary. BB is thought provoking because it shows that a simple computation completely destroys any possible conception of mathematics. Probably not very useful but still very interesting.
  - magicalhippo 3y ago
    But programming is math[1], so is the conclusion that math will eat itself? [1]: as many argue in the software patent cases
    - pas 3y ago
      Math is mostly about proofs, and many behaviors of computation are simply not provable, but are still useful. Of course it's possible to use models, formal systems, simulation, formulas, and other tools of mathematics, but arguably there's a clear symmetry breaking. (But it's not really surprising, as most numbers are unnameable and uncomputable. So many things in math are like Turing machines, just they are not that useful.)
  - andrewflnr 3y ago
    > completely destroys any possible conception of mathematics Hyperbolic, to put it gently. It changes our conception of mathematics to a different conception.
- Dylan16807 3y ago
NoMoreNicksLeft 3y ago
I'm always delighted by how the real content is always in the comments. I wish I understood the principle of sociology/psychology that caused this to be true.
- karmakurtisaani 3y ago
  It's probably pretty simple: someone writes a thought-provoking article, and then the experts cone together to discuss it. Among the experts there are people with interesting views or ability explain complicated things simply.
SonOfLilit 3y ago
Be sure to also read the referenced essay "Who Can Name The Biggest Number?", it's loads of fun and a great explanation of the BB function: https://www.scottaaronson.com/writings/bignumbers.html https://www.scottaaronson.com/writings/bignumbers.html
mcherm 3y ago
See also this article (shared on Hacker News 2 weeks ago): https://www.sligocki.com//2023/10/16/bb-3-3-is-hard.html https://www.sligocki.com//2023/10/16/bb-3-3-is-hard.html Basically, they showed that a VERY small Turing Machine -- of a size many had hoped we would be able to exhaustively solve -- turns out to depend on whether something similar to the Collatz sequence ever haults. In other words, research published just 2 weeks ago shows that we don't need a Turing machine with a couple thousand states to be beyond the reach of modern human mathematics -- even one with just a few states can stimy us.
- raincole 3y ago
  What does "exhaustively solve a Turing Machine" mean is this context?
  - pxeger1 3y ago
    “Solve” means “solve the halting problem for” (i.e. prove whether it will halt or not), and “exhaustively” means “for all possible Turing machines with a given number of states”
    - raincole 3y ago
      But intuitively a Turning machine, no matter how small number of states, can't be exhaustively solved, since there are infinite number of possilbe strings on the tape?
      - denotational 3y ago
        Proving properties hold over sets of infinite cardinality is fairly routine in mathematics. We know that not every Turing Machine can be “solved”, because this would give us an oracle for HALT, but there are machines that can be. A trivial example is a TM that halts immediately, regardless of the input; a less trivial example is one that reads an arbitrarily large integer input on the tape and outputs its factorisation (or, if we don’t want to consider output, decides whether an input pair is formed of an integer and it’s factorisation). Given that the set of Turing Machines with a certain number of states (or less) is finite for a given alphabet, it’s “just” a case of solving that finite set. EDIT: Note that as the sibling comment points out, BB is usually considered to start with an empty tape, but fundamentally, proving that a machine always halts regardless of their starting tape is not intrinsically impossible as you suggest.
thriftwy 3y ago
I wonder if we could switch to "ation scale" where every number is notated as fractional N-ation required to make it. Then we can fit any natural number we use betwern 3 and 4, and even BB numbers will not be very scary. We get them back to the realm of writedownity. Is there a function to convert fractional numbers between natural and ation scale? A(2) = 4, A(3) = 27, A(4) = 10 ^ (10 ^ 154), but what's A(3.5)?
- UncombedCoconut 3y ago
  This program is at least related to what you want: https://googology.fandom.com/wiki/Hypercalc https://googology.fandom.com/wiki/Hypercalc -- and the community there has devised other systems for representing huge numbers with compact notations.
- srcreigh 3y ago
  What is "fractional N-ation"?
  - lifthrasiir 3y ago
    You can regard multiplication as repeated additions, exponentiation as repeated multiplications, tetration as repeated exponentiation and so on. Of course they are not just repeated operations; you've got to define them for negative, fractional and complex operands in a justifiable way as well. Note that those operations also form a sequence, so let's rename addition to 1-ation, ..., tetration to 4-ation (in fact tetra- prefix exactly means this) and so on. Now, what could be 2.5-ation or pi-ation?
    - thriftwy 3y ago
      The point being, what's the pi-ation of pi.
cryptonector 3y ago
https://hn.algolia.com/?query=The%208000th%20Busy%20Beaver%20number%20eludes%20ZF%20set%20theory&type=story&dateRange=all&sort=byDate&storyText=false&prefix&page=0 https://hn.algolia.com/?query=The%208000th%20Busy%20Beaver%2...
anonymouskimmer 3y ago
> In more detail, we know that it’s possible with our laws of physics to build a self-replicating machine: say, DNA or RNA and their associated paraphernalia. We also know that tiny molecules like H2O and CO2 are not self-replicating. But we don’t know how small the smallest self-replicating molecule can be—and that’s an issue that influences whether we should expect to find ourselves alone in the universe or find it teeming with life. DNA and RNA typically isn't self-replicating. As indicated in this very quote is takes a machine to do so. In a world with 'volcanoes' that emit pure hydrogen gas and pure oxygen gas (not from the same 'volcano', H2O could indeed be self-replicating by generating a greenhouse effect raising the temperature to the autoignition point of hydrogen gas (535°C according to Wikipedia). These are nitpicks, though. I get the general point.

114 points by jkubicek 3y ago

Adam Yedidia had a claim to fame other than being SBF’s roommate.

FTA this is an interesting tidbit about Busy Beavers: But the BB function has a second amazing property: namely, it’s a perfectly well-defined integer function, and yet once you fix the axioms of mathematics, only finitely many values of the function can ever be proved, even in principle. To see why, consider again a Turing machine M that halts if and only if there’s a contradiction in ZF set theory. Clearly such a machine could be built, with some finite number of states k. But then ZF set theory can’t possibly determine the value of BB(k) (or BB(k+1), BB(k+2), etc.), unless ZF is inconsistent! For to do so, ZF would need to prove that M ran forever, and therefore prove its own consistency, and therefore be inconsistent by Gödel’s Theorem.

adverbly 3y ago
> consider again a Turing machine M that halts if and only if there’s a contradiction in ZF set theory. Clearly such a machine could be built, with some finite number of states k. I am a small brain here. How is this so clear?
- _a_a_a_ 3y ago
  Because it says 'clearly'. (but yeah, agree with you)
- meithecatte 3y ago
  Checking whether a string of bits encodes a proof of False in ZF is decidable. Now enumerate the bitstrings and check each.
  - klyrs 3y ago
    > and check each. "Now, draw the rest of the owl." Not saying you're wrong, just, this jump is super non-obvious even to most mathematicians.
    - CaptainNegative 3y ago
      If you can check any given bitstring for whether it encodes a valid ZFC proof of the (in)consistency of ZFC in finite time, then you can write a program to enumerate over all possible bit strings in shortlex order and halt the first time you see a valid proof.
  - WindyLakeReturn 3y ago
    There are infinite many such strings, so that alone can't be used to prove the Turing machine of k states can check all strings. So that leaves open the original question, how do we know that a Turing machine of k states is able to have one of the stated outcomes for any possible bit string?
    - nyssos 3y ago
      > There are infinite many such strings And they can be enumerated by a finite program. For example, in lazily evaluated pseudocode: bits = ["0", "1"] bitstrings = bits + [(bit + suffix for bit in bits) for suffix in bitstrings]
- tomstuart 3y ago
  I wouldn’t defend the idea that it’s “clear”, but the idea is to build a machine that combines the axioms of ZF set theory in all possible ways to generate all possible conclusions, checking each one for contradiction as it goes. If it never generates a contradictory conclusion from those axioms, it’ll run forever.
  - ijustlovemath 3y ago
    This sounds like it relies on the halting problem, or maybe the other way around? Really interesting stuff, been a while since I read about a higher level math topic and been able to sorta kinda understand the "quanta-level" summaries out there
    - jtolmar 3y ago
      The Nth Busy Beaver number lets you solve the halting problem for Turing Machines up to size N. Only a handful of them are known, for very small N, and they increase incredibly rapidly. For the most common version of the problem (S for 2-symbol machines), they go: 1, 6, 21, 107, some number greater than or equal to 47176870, and some number greater than 10⇈15 (that's up arrow notation on the last one).
      - ijustlovemath 3y ago
        Ooh, are they basically the number of possible turing programs encodable in a state of N?
        readams 3y ago
        It's the maximum amount of time a Turing machine of size N can run. So if you want to know whether a Turning machine of size N or less will halt, just run it for BB(N) steps. If it hasn't halted by then, it never will.
  - stouset 3y ago
    I think the part that eludes me here is that it's not clear that such a Turing machine could be built from a finite number of states.

tromp 3y ago

Previously discussed at https://news.ycombinator.com/item?id=36658506 https://news.ycombinator.com/item?id=36658506 Quoting from https://scottaaronson.blog/?p=7388 https://scottaaronson.blog/?p=7388 : > Johannes Riebel, an undergraduate at the University of Augsburg in Germany, has produced a tour-de-force bachelor’s thesis that contains, among other things, the first careful writeup of Stefan O’Rear’s result from six years ago that the value of BB(748) is independent of the ZFC axioms of set theory. Regular readers might recall that O’Rear’s result substantially improved over the initial result by me and Adam Yedidia, which showed the value of BB(8000) independent of ZFC assuming the consistency of a stronger system. Along the way, Riebel even gets a tiny improvement, showing that BB(745) independent of ZFC.

arethuza 3y ago
BB(748) - BB(745) is probably the largest value that anyone has ever described as "tiny" :-)
- danbruc 3y ago
  I would assume tiny refers to three.
  - TheRealNGenius 3y ago
    [dead]
- sebzim4500 3y ago
  It's actually really hard to come up with an interesting lower bound that value. IIRC no one has proven that BB(n) + 1 < BB(n + 1) for large 2
  - kevinventullo 3y ago
    Hm, is there some way to “concatenate” Turing machines which would let you prove something like BB(n) + BB(m) <= BB(n+m+c) for some fixed c independent of n and m?

cyberax 3y ago

These theses are technically very complicated, but what they do is actually easy to explain: they construct a short "program" that basically enumerates all possible statements and checks their validity. And then terminates if it detects a contradiction. A program that checks the axioms of Peano arithmetic, or of ZF set theory is undecidable, we know that from Gödel's incompleteness theorems. So then it becomes a sort of competition: who can write the shortest Turing machine that encodes that program. Kinda like a demo-scene for mathematicians.

henry2023 3y ago
This is a great summary. BB is thought provoking because it shows that a simple computation completely destroys any possible conception of mathematics. Probably not very useful but still very interesting.
- magicalhippo 3y ago
  But programming is math[1], so is the conclusion that math will eat itself? [1]: as many argue in the software patent cases
  - pas 3y ago
    Math is mostly about proofs, and many behaviors of computation are simply not provable, but are still useful. Of course it's possible to use models, formal systems, simulation, formulas, and other tools of mathematics, but arguably there's a clear symmetry breaking. (But it's not really surprising, as most numbers are unnameable and uncomputable. So many things in math are like Turing machines, just they are not that useful.)
- andrewflnr 3y ago
  > completely destroys any possible conception of mathematics Hyperbolic, to put it gently. It changes our conception of mathematics to a different conception.
Dylan16807 3y ago

NoMoreNicksLeft 3y ago

I'm always delighted by how the real content is always in the comments. I wish I understood the principle of sociology/psychology that caused this to be true.

karmakurtisaani 3y ago
It's probably pretty simple: someone writes a thought-provoking article, and then the experts cone together to discuss it. Among the experts there are people with interesting views or ability explain complicated things simply.

SonOfLilit 3y ago

Be sure to also read the referenced essay "Who Can Name The Biggest Number?", it's loads of fun and a great explanation of the BB function: https://www.scottaaronson.com/writings/bignumbers.html https://www.scottaaronson.com/writings/bignumbers.html

mcherm 3y ago

See also this article (shared on Hacker News 2 weeks ago): https://www.sligocki.com//2023/10/16/bb-3-3-is-hard.html https://www.sligocki.com//2023/10/16/bb-3-3-is-hard.html Basically, they showed that a VERY small Turing Machine -- of a size many had hoped we would be able to exhaustively solve -- turns out to depend on whether something similar to the Collatz sequence ever haults. In other words, research published just 2 weeks ago shows that we don't need a Turing machine with a couple thousand states to be beyond the reach of modern human mathematics -- even one with just a few states can stimy us.

raincole 3y ago
What does "exhaustively solve a Turing Machine" mean is this context?
- pxeger1 3y ago
  “Solve” means “solve the halting problem for” (i.e. prove whether it will halt or not), and “exhaustively” means “for all possible Turing machines with a given number of states”
  - raincole 3y ago
    But intuitively a Turning machine, no matter how small number of states, can't be exhaustively solved, since there are infinite number of possilbe strings on the tape?
    - denotational 3y ago
      Proving properties hold over sets of infinite cardinality is fairly routine in mathematics. We know that not every Turing Machine can be “solved”, because this would give us an oracle for HALT, but there are machines that can be. A trivial example is a TM that halts immediately, regardless of the input; a less trivial example is one that reads an arbitrarily large integer input on the tape and outputs its factorisation (or, if we don’t want to consider output, decides whether an input pair is formed of an integer and it’s factorisation). Given that the set of Turing Machines with a certain number of states (or less) is finite for a given alphabet, it’s “just” a case of solving that finite set. EDIT: Note that as the sibling comment points out, BB is usually considered to start with an empty tape, but fundamentally, proving that a machine always halts regardless of their starting tape is not intrinsically impossible as you suggest.

thriftwy 3y ago

I wonder if we could switch to "ation scale" where every number is notated as fractional N-ation required to make it. Then we can fit any natural number we use betwern 3 and 4, and even BB numbers will not be very scary. We get them back to the realm of writedownity. Is there a function to convert fractional numbers between natural and ation scale? A(2) = 4, A(3) = 27, A(4) = 10 ^ (10 ^ 154), but what's A(3.5)?

UncombedCoconut 3y ago
This program is at least related to what you want: https://googology.fandom.com/wiki/Hypercalc https://googology.fandom.com/wiki/Hypercalc -- and the community there has devised other systems for representing huge numbers with compact notations.
srcreigh 3y ago
What is "fractional N-ation"?
- lifthrasiir 3y ago
  You can regard multiplication as repeated additions, exponentiation as repeated multiplications, tetration as repeated exponentiation and so on. Of course they are not just repeated operations; you've got to define them for negative, fractional and complex operands in a justifiable way as well. Note that those operations also form a sequence, so let's rename addition to 1-ation, ..., tetration to 4-ation (in fact tetra- prefix exactly means this) and so on. Now, what could be 2.5-ation or pi-ation?
  - thriftwy 3y ago
    The point being, what's the pi-ation of pi.

cryptonector 3y ago

https://hn.algolia.com/?query=The%208000th%20Busy%20Beaver%20number%20eludes%20ZF%20set%20theory&type=story&dateRange=all&sort=byDate&storyText=false&prefix&page=0 https://hn.algolia.com/?query=The%208000th%20Busy%20Beaver%2...

anonymouskimmer 3y ago

> In more detail, we know that it’s possible with our laws of physics to build a self-replicating machine: say, DNA or RNA and their associated paraphernalia. We also know that tiny molecules like H2O and CO2 are not self-replicating. But we don’t know how small the smallest self-replicating molecule can be—and that’s an issue that influences whether we should expect to find ourselves alone in the universe or find it teeming with life. DNA and RNA typically isn't self-replicating. As indicated in this very quote is takes a machine to do so. In a world with 'volcanoes' that emit pure hydrogen gas and pure oxygen gas (not from the same 'volcano', H2O could indeed be self-replicating by generating a greenhouse effect raising the temperature to the autoignition point of hydrogen gas (535°C according to Wikipedia). These are nitpicks, though. I get the general point.