6 ms·

Busy Beaver Updates: Now Even Busier

135 points by nsoonhui 4y ago

vanderZwan 4y ago
> Kropitz and Michel’s discovery doesn’t settle the question—titanic though it is, the new lower bound on BB(6) is still less than A(6) (!!) Doesn't the Ackermann function take two arguments? Anyway, what I'm actually more curious about than the result (impressive though it is) is the maths behind verifying these numbers. Does anyone know a gentle introduction to the relevant maths?
- H8crilA 4y ago
  It's A(6,6)
  - vanderZwan 4y ago
    Thank you for clearing that up
- tromp 4y ago
  As Scott says in his blog comment section [1] > by a combination of automated methods and case-by-case cleverness, people managed to find proofs of non-termination for all the non-halting ... machines So it's very ad-hoc. You study a particular machines's behaviour and formulate hypotheses about how it can keep going on forever and then try to prove them. [1] https://scottaaronson.blog/?p=6673#comment-1942654 https://scottaaronson.blog/?p=6673#comment-1942654
  - tialaramex 4y ago
    Down here at BB(6) you can feel fairly sure the machine doesn't express anything inherently problematic because it's just too simple. But as the parameter goes up, the machines get sophisticated and very quickly the machines express ideas like "Look at all the positive multiples of seven in turn, halt when Fermat's conjecture is wrong for this value of n" and in that particular case we know the answer is "This never halts" but even thirty years ago the best we can say is "Probably not?". You only need one "Probably?" or "Probably not?" to be screwed, now you can't even figure out if this machine is a candidate or not.
    - ElCheapo 4y ago
      This is really mind boggingly, meaning that there is an actual discrete valicable limit of what can be determined and what can't. Turing machine with 4 states? Cool. Turing machine with 5 states? Sorry, it goes beyond ZFC maths!
    - nickdrozd 4y ago
      > Down here at BB(6) you can feel fairly sure the machine doesn't express anything inherently problematic because it's just too simple. One of the shocking results of Busy Beaver research is that this is actually false. Even with as few as four states there are machines that are complicated and difficult to understand. Turing machine "states" are really GOTO targets, and with six states it's possible to create control flow that is beyond incomprehensible. I wrote up some rambly notes about this: https://nickdrozd.github.io/2021/09/25/spaghetti-code-conjecture-false.html https://nickdrozd.github.io/2021/09/25/spaghetti-code-conjec...
      - nullc 4y ago
        Perhaps it means that there is some kind of new and useful (or, interesting at least) generic control flow primitive waiting to be discovered there-- and with it the control flow is again 'simple'. :)
      - tialaramex 4y ago
        Wow. The BBB(4) example was impressive in particular. I stand corrected.
    - a_shovel 4y ago
      The big numbers don't impress me, but the fact that such tiny machines can correspond to complex and even meaningful theorems is fascinating. I wonder what the smallest number of states you need to encode a pre-existing well-known mathematical conjecture is.
      - lmkg 4y ago
        They've found a 43-state machine that encodes the Goldbach Conjecture, and proposed but not verified that it can be compressed 27 states. I would consider the Goldbach Conjecture to be "well-known" as far as math theorems go, since it was referenced on Futurama. https://en.wikipedia.org/wiki/Busy_beaver#Notable_instances https://en.wikipedia.org/wiki/Busy_beaver#Notable_instances
tromp 4y ago
BB(n) involves the class of all n-state 2-symbol Turing machines. Encoding such a machine in binary amounts to encoding each of its n*2 transitions that depend on the current state and symbol read. A transition specifies a new symbol to write, a direction to move in (left or right) and a new state to move to, or halt. That takes 1 + 1 + ceil (log (n+1)) bits per transition. So BB(6) machines are described by 12*(2+3) = 60 bits. Instead of Turing machines, one can also take the lambda calculus as model of computation. Sequence A333479 in the Online Encyclopedia of Integer Sequences [1] shows the Busy Beaver for binary lambda calculus as the maximum normal form size of any closed lambda term of size n bits. Using bits instead of states gives a more fine-grained scale of un-computability. The latest BB(6) result suggests a challenge for functional programmers: what's the smallest n for which A333479(n) can be shown at least 10^10^10^10^10^10^10^10^10^10^10^10^10^10^10 ? I'm hoping it can be under 60 bits... [1] https://oeis.org/A333479 https://oeis.org/A333479
- codeflo 4y ago
  I'm interested in that as well. On the other hand, all of that can only account for constant factors (in the limit, I can use some extra states to encode a lambda calculus interpreter in my Turing machine). Even for Turing machines, two symbols tapes might not be the most efficient in terms of BB steps per encoded machine bit. Having said all that, your encoding is a bit wasteful, so let's optimize. ;) First, there's really no need for the encoded states to end on bit boundaries. To give an example, to encode 9 numbers between 0 and 9 (inclusive), you don't need 9*ceil(log2(10))=36 bits, you only need ceil(9*log2(10))=30 bits by treating the digits as a large decimal number and converting that to binary. Second, if you're going to halt anyway, there's no need (at least for the BB problem) to write a symbol and move the tape on the last transition, so we can simply treat that as an alternative to encoding a transition. Armed with both of those, the size of an encoded machine goes down to ceil(2 * 6 * log2(2 * 2 * 6 + 1)) = 56 bits. (In general for n states and k symbols, ceil(k * n * log2(2 * k * n + 1)). The 2 is for the directions, the + 1 is the halting transition.)
  - tromp 4y ago
    Yes, it's a bit wasteful. But importantly, it's straightforward, and it's what efficient universal Turing Machines would use in their input, so it makes sense for a comparison. Even the binary lambda coding allows for some optimization, like coding for variable 2 at depth 2 as 111 rather than 1110 since an occurrence of variable >= 3 would not make the term closed. > so we can simply treat that as an alternative to encoding a transition That's fine for the shift number but a lot of BB research concerns the number of 1s written rather than the number of steps taken, and there it matters. They prefer to use a single model for all variants.
codeflo 4y ago
The Busy Beaver function is fascinating. Seemingly so easy to define: Of all possible turing machines with N states that eventually halt, what's the number of steps that the longest-running one takes? It's not "just" that this is uncomputable, given the halting problem. Lots of things in mathematics are uncomputable. What's special about this function is that it will eventually blast through the limits of what any given formalization of mathematics can prove at all, no matter how powerful -- like ZFC + CH + whatever other axioms you come up with.[1] To be honest, I can't fully wrap my head around what this means. Given that some of these powerful set theoretic axioms are independent from each other, I'm not sure whether ZFC+CH could have a different idea about BB(8000) than ZFC+notCH would. That wouldn't make much sense to me at least, because a Turing machine halting or not halting feels like a concrete fact that shouldn't depend on assumptions about weird infinite sets. But I don't know. [1] Also from Scott Aaronson's blog, BB(8000) and above are independent from ZFC: https://scottaaronson.blog/?p=2725 https://scottaaronson.blog/?p=2725
- Sharlin 4y ago
  So there exists a Turing machine (with some finite number of states N, naturally) that is just complex enough to encode ZF(C) and first-order logic such that it can enumerate all theorems of ZF(C). But because of Gödel, at some point it must necessarily either get stuck in a loop or return "can’t prove or disprove this" for some candidate theorem. As I understand it, the result relayed by Scott proves that N=7198 – as in a state space of merely 13 bits – is sufficient to construct a Gödel-territory TM (but this is just an upper bound)! Having an unbounded tape as a scratch space helps, of course.
- karatinversion 4y ago
  > because a Turing machine halting or not halting feels like a concrete fact that shouldn't depend on assumptions about weird infinite sets Think about it this way. If a particular Turing machine halts, that’s a finitary fact: you can prove it by exhibiting a finite sequence of valid states for the Turing machine which ends in a halt. But if it doesn’t halt, that’s an infinitary statement: it doesn’t halt after N steps, for any N. And no finite enumeration of steps can prove that it doesn’t halt eventually. Since the statement is infinitary, it’s liable to avoid being probable if our axioms don’t capture it - and so computable set of axioms captures all true statements. And if we can’t prove that a particular Turing machine of N states doesn’t halt, we can’t prove any value for BB(N), as otherwise we could just staple the first BB(N) states of the Turing machine to show it doesn’t halt, which we can’t prove.
deleted 4y ago
[deleted]
lisper 4y ago
Here is the proof of the result: https://www.sligocki.com/2022/06/21/bb-6-2-t15.html https://www.sligocki.com/2022/06/21/bb-6-2-t15.html It is very accessible and makes fascinating (by geek standards) reading.
- MauranKilom 4y ago
  Host not found :(
  - lisper 4y ago
    Works for me. Check your DNS settings.
    - MauranKilom 4y ago
      Works for me too now. :)
avmich 4y ago
> In my 2020 survey, I’d relayed an open problem posed by my then 7-year-old daughter Lily: namely, what’s the first n such that BB(n) exceeds A(n), the nth value of the Ackermann function? Time for some pedagogical articles?
- lukasb 4y ago
  yeah I had the same o_O reaction
avmich 4y ago
> ...longstanding conjecture that BB(5)=47,176,870... Tristan and Damien still count 1.5 million (!) holdout machines... I assume that if one tries all 1.5 million machines, they either (1) stop before 47,176,870 or (2) run longer, and don't stop for some observable time?
benlivengood 4y ago
The most mind-bending thing to me about the Busy Beaver problem is that once N gets big enough (probably into the low hundreds of states) the machines can start to examine all of mathematics itself, and so likely are posing extremely interesting questions like whether a particular set of finite axioms is complete and consistent, and checking all possible proofs until finally discovering a gigantic theory smaller than PA or ZFC but still far larger than any finite systems we can ever imagine, and halting once all the possible proofs are enumerated. Depending on how our universe turns out to work on a fundamental level, busy beavers may contain a record of the evolution of our universe (and all the alternatives from different initial conditions) from the big bang until the heat death as a trivial lemma in a larger proof. They'll be full of proofs or disproofs of mathematical conjectures in fancy formal systems we'll never have time to discover even with the infinite axiom schemas available to us. At least that's the most complex, longest-lasting and most bits-written-to-tape task I can imagine specifying in a few hundred bits. The neat thing is that BB(N) considers all the interesting and answerable questions anyone could ever think to ask with N states worth of bits. Sure, maybe there's some trivial rote task that is truly the biggest for a given N (which I doubt; it seems like rote tasks would fall out of an exploration of a larger conceptual space) but some of its neighbors will be absolutely amazing.

135 points by nsoonhui 4y ago

> Kropitz and Michel’s discovery doesn’t settle the question—titanic though it is, the new lower bound on BB(6) is still less than A(6) (!!) Doesn't the Ackermann function take two arguments? Anyway, what I'm actually more curious about than the result (impressive though it is) is the maths behind verifying these numbers. Does anyone know a gentle introduction to the relevant maths?

H8crilA 4y ago
It's A(6,6)
- vanderZwan 4y ago
  Thank you for clearing that up
tromp 4y ago
As Scott says in his blog comment section [1] > by a combination of automated methods and case-by-case cleverness, people managed to find proofs of non-termination for all the non-halting ... machines So it's very ad-hoc. You study a particular machines's behaviour and formulate hypotheses about how it can keep going on forever and then try to prove them. [1] https://scottaaronson.blog/?p=6673#comment-1942654 https://scottaaronson.blog/?p=6673#comment-1942654
- tialaramex 4y ago
  Down here at BB(6) you can feel fairly sure the machine doesn't express anything inherently problematic because it's just too simple. But as the parameter goes up, the machines get sophisticated and very quickly the machines express ideas like "Look at all the positive multiples of seven in turn, halt when Fermat's conjecture is wrong for this value of n" and in that particular case we know the answer is "This never halts" but even thirty years ago the best we can say is "Probably not?". You only need one "Probably?" or "Probably not?" to be screwed, now you can't even figure out if this machine is a candidate or not.
  - ElCheapo 4y ago
    This is really mind boggingly, meaning that there is an actual discrete valicable limit of what can be determined and what can't. Turing machine with 4 states? Cool. Turing machine with 5 states? Sorry, it goes beyond ZFC maths!
  - nickdrozd 4y ago
    > Down here at BB(6) you can feel fairly sure the machine doesn't express anything inherently problematic because it's just too simple. One of the shocking results of Busy Beaver research is that this is actually false. Even with as few as four states there are machines that are complicated and difficult to understand. Turing machine "states" are really GOTO targets, and with six states it's possible to create control flow that is beyond incomprehensible. I wrote up some rambly notes about this: https://nickdrozd.github.io/2021/09/25/spaghetti-code-conjecture-false.html https://nickdrozd.github.io/2021/09/25/spaghetti-code-conjec...
    - nullc 4y ago
      Perhaps it means that there is some kind of new and useful (or, interesting at least) generic control flow primitive waiting to be discovered there-- and with it the control flow is again 'simple'. :)
    - tialaramex 4y ago
      Wow. The BBB(4) example was impressive in particular. I stand corrected.
  - a_shovel 4y ago
    The big numbers don't impress me, but the fact that such tiny machines can correspond to complex and even meaningful theorems is fascinating. I wonder what the smallest number of states you need to encode a pre-existing well-known mathematical conjecture is.
    - lmkg 4y ago
      They've found a 43-state machine that encodes the Goldbach Conjecture, and proposed but not verified that it can be compressed 27 states. I would consider the Goldbach Conjecture to be "well-known" as far as math theorems go, since it was referenced on Futurama. https://en.wikipedia.org/wiki/Busy_beaver#Notable_instances https://en.wikipedia.org/wiki/Busy_beaver#Notable_instances

tromp 4y ago

BB(n) involves the class of all n-state 2-symbol Turing machines. Encoding such a machine in binary amounts to encoding each of its n*2 transitions that depend on the current state and symbol read. A transition specifies a new symbol to write, a direction to move in (left or right) and a new state to move to, or halt. That takes 1 + 1 + ceil (log (n+1)) bits per transition. So BB(6) machines are described by 12*(2+3) = 60 bits. Instead of Turing machines, one can also take the lambda calculus as model of computation. Sequence A333479 in the Online Encyclopedia of Integer Sequences [1] shows the Busy Beaver for binary lambda calculus as the maximum normal form size of any closed lambda term of size n bits. Using bits instead of states gives a more fine-grained scale of un-computability. The latest BB(6) result suggests a challenge for functional programmers: what's the smallest n for which A333479(n) can be shown at least 10^10^10^10^10^10^10^10^10^10^10^10^10^10^10 ? I'm hoping it can be under 60 bits... [1] https://oeis.org/A333479 https://oeis.org/A333479

codeflo 4y ago
I'm interested in that as well. On the other hand, all of that can only account for constant factors (in the limit, I can use some extra states to encode a lambda calculus interpreter in my Turing machine). Even for Turing machines, two symbols tapes might not be the most efficient in terms of BB steps per encoded machine bit. Having said all that, your encoding is a bit wasteful, so let's optimize. ;) First, there's really no need for the encoded states to end on bit boundaries. To give an example, to encode 9 numbers between 0 and 9 (inclusive), you don't need 9*ceil(log2(10))=36 bits, you only need ceil(9*log2(10))=30 bits by treating the digits as a large decimal number and converting that to binary. Second, if you're going to halt anyway, there's no need (at least for the BB problem) to write a symbol and move the tape on the last transition, so we can simply treat that as an alternative to encoding a transition. Armed with both of those, the size of an encoded machine goes down to ceil(2 * 6 * log2(2 * 2 * 6 + 1)) = 56 bits. (In general for n states and k symbols, ceil(k * n * log2(2 * k * n + 1)). The 2 is for the directions, the + 1 is the halting transition.)
- tromp 4y ago
  Yes, it's a bit wasteful. But importantly, it's straightforward, and it's what efficient universal Turing Machines would use in their input, so it makes sense for a comparison. Even the binary lambda coding allows for some optimization, like coding for variable 2 at depth 2 as 111 rather than 1110 since an occurrence of variable >= 3 would not make the term closed. > so we can simply treat that as an alternative to encoding a transition That's fine for the shift number but a lot of BB research concerns the number of 1s written rather than the number of steps taken, and there it matters. They prefer to use a single model for all variants.

codeflo 4y ago

The Busy Beaver function is fascinating. Seemingly so easy to define: Of all possible turing machines with N states that eventually halt, what's the number of steps that the longest-running one takes? It's not "just" that this is uncomputable, given the halting problem. Lots of things in mathematics are uncomputable. What's special about this function is that it will eventually blast through the limits of what any given formalization of mathematics can prove at all, no matter how powerful -- like ZFC + CH + whatever other axioms you come up with.[1] To be honest, I can't fully wrap my head around what this means. Given that some of these powerful set theoretic axioms are independent from each other, I'm not sure whether ZFC+CH could have a different idea about BB(8000) than ZFC+notCH would. That wouldn't make much sense to me at least, because a Turing machine halting or not halting feels like a concrete fact that shouldn't depend on assumptions about weird infinite sets. But I don't know. [1] Also from Scott Aaronson's blog, BB(8000) and above are independent from ZFC: https://scottaaronson.blog/?p=2725 https://scottaaronson.blog/?p=2725

Sharlin 4y ago
So there exists a Turing machine (with some finite number of states N, naturally) that is just complex enough to encode ZF(C) and first-order logic such that it can enumerate all theorems of ZF(C). But because of Gödel, at some point it must necessarily either get stuck in a loop or return "can’t prove or disprove this" for some candidate theorem. As I understand it, the result relayed by Scott proves that N=7198 – as in a state space of merely 13 bits – is sufficient to construct a Gödel-territory TM (but this is just an upper bound)! Having an unbounded tape as a scratch space helps, of course.
karatinversion 4y ago
> because a Turing machine halting or not halting feels like a concrete fact that shouldn't depend on assumptions about weird infinite sets Think about it this way. If a particular Turing machine halts, that’s a finitary fact: you can prove it by exhibiting a finite sequence of valid states for the Turing machine which ends in a halt. But if it doesn’t halt, that’s an infinitary statement: it doesn’t halt after N steps, for any N. And no finite enumeration of steps can prove that it doesn’t halt eventually. Since the statement is infinitary, it’s liable to avoid being probable if our axioms don’t capture it - and so computable set of axioms captures all true statements. And if we can’t prove that a particular Turing machine of N states doesn’t halt, we can’t prove any value for BB(N), as otherwise we could just staple the first BB(N) states of the Turing machine to show it doesn’t halt, which we can’t prove.

deleted 4y ago

[deleted]

lisper 4y ago

Here is the proof of the result: https://www.sligocki.com/2022/06/21/bb-6-2-t15.html https://www.sligocki.com/2022/06/21/bb-6-2-t15.html It is very accessible and makes fascinating (by geek standards) reading.

MauranKilom 4y ago
Host not found :(
- lisper 4y ago
  Works for me. Check your DNS settings.
  - MauranKilom 4y ago
    Works for me too now. :)

avmich 4y ago

> In my 2020 survey, I’d relayed an open problem posed by my then 7-year-old daughter Lily: namely, what’s the first n such that BB(n) exceeds A(n), the nth value of the Ackermann function? Time for some pedagogical articles?

lukasb 4y ago
yeah I had the same o_O reaction

avmich 4y ago

> ...longstanding conjecture that BB(5)=47,176,870... Tristan and Damien still count 1.5 million (!) holdout machines... I assume that if one tries all 1.5 million machines, they either (1) stop before 47,176,870 or (2) run longer, and don't stop for some observable time?

benlivengood 4y ago

The most mind-bending thing to me about the Busy Beaver problem is that once N gets big enough (probably into the low hundreds of states) the machines can start to examine all of mathematics itself, and so likely are posing extremely interesting questions like whether a particular set of finite axioms is complete and consistent, and checking all possible proofs until finally discovering a gigantic theory smaller than PA or ZFC but still far larger than any finite systems we can ever imagine, and halting once all the possible proofs are enumerated. Depending on how our universe turns out to work on a fundamental level, busy beavers may contain a record of the evolution of our universe (and all the alternatives from different initial conditions) from the big bang until the heat death as a trivial lemma in a larger proof. They'll be full of proofs or disproofs of mathematical conjectures in fancy formal systems we'll never have time to discover even with the infinite axiom schemas available to us. At least that's the most complex, longest-lasting and most bits-written-to-tape task I can imagine specifying in a few hundred bits. The neat thing is that BB(N) considers all the interesting and answerable questions anyone could ever think to ask with N states worth of bits. Sure, maybe there's some trivial rote task that is truly the biggest for a given N (which I doubt; it seems like rote tasks would fall out of an exploration of a larger conceptual space) but some of its neighbors will be absolutely amazing.