5 ms·

The Busy Beaver Challenge

67 points by bmc7505 4y ago

SethTro 4y ago
Some discussion of remaining infinite BB(5) machines yesterday in [1][2] [1] https://www.sligocki.com//2023/02/02/skelet-34.html https://www.sligocki.com//2023/02/02/skelet-34.html [2] https://news.ycombinator.com/item?id=34689068 https://news.ycombinator.com/item?id=34689068 and
zabzonk 4y ago
i think the "Story" page might be a better link, i know about busy beavers, but those that don't might be a bit lost.
- BubbleRings 4y ago
  A bit? :)
Allezxandre 4y ago
Wikipedia [1] has a problem statement that I find explains the game quite simply: > the busy beaver game aims at finding a terminating program of a given size that produces the most output possible. The Busy Beaver Challenge website [2] also has an explainer page with interactive Turing Machines. [1] https://en.wikipedia.org/wiki/Busy_beaver https://en.wikipedia.org/wiki/Busy_beaver [2] https://bbchallenge.org/story https://bbchallenge.org/story
avmich 4y ago
So, about 88 millions of machines is left to test. We're interested in any, which runs longer than about 47 millions steps. Multiplying we get about 4.2e15 steps at worst. Can't we brute force the solution? It's like 5 million seconds - or less than two months - 1 billion steps a second, which looks doable for a modest system, and we don't even need much memory...
- lukevp 4y ago
  I think the problem is that some of the Turing machines are infinite, so getting 47 million steps in is the _entrypoint_ and you must then run until it halts (or you determine it’s not going to halt somehow). So the search space is unbounded, but it seems like you could snapshot the state of each machine at the 47 million steps and then incrementally search a couple thousand steps forward on each one looking for halting? I may be totally off though, I won’t pretend to fully grok this.
  - deleted 4y ago
    [deleted]
  - avmich 4y ago
    In "Story" website section: "This conjecture says that 47,176,870 is the maximum number of steps that a 5-state Turing machine can run before halting (starting from all-0 memory tape)." So, we can run up to this number and either the machine will stop - and we'll go to the next one until exhaust the whole set - or the machine won't stop, and we'll refute the conjecture.
    - teraflop 4y ago
      No, you seem to be misunderstanding the conjecture. It's about the maximum number of steps executed by a Turing machine that eventually halts. If you simulate a Turing machine up to that many steps, and find it hasn't halted yet, then the conjecture is refuted if you know the machine's execution will eventually terminate -- but famously, there's no algorithm that can reliably tell you whether or not a given TM halts. If it was just about the maximum number of steps that could be executed by a 5-state Turing machine, it would be trivially false, because it's easy to construct a Turing machine that runs forever.
      - avmich 4y ago
        Yeah, I was surprised the statement is constructed this way. Adding condition of eventual halting - which is what makes it the busy beaver - makes the difference :) .
ramraj07 4y ago
Scott Aaranson’s decades old “big numbers” write up which I think explains why this is useful and fun: https://www.scottaaronson.com/writings/bignumbers.html https://www.scottaaronson.com/writings/bignumbers.html
tromp 4y ago
For functional programming fans, there is an alternative definition of the busy beaver function as [1] the maximum normal form size of any closed lambda term of size n This has the advantage of having a higher "resolution" by measuring program size in bits rather than states. [1] https://oeis.org/draft/A333479 https://oeis.org/draft/A333479
- tromp 4y ago
  Oops; that link should be https://oeis.org/A333479 https://oeis.org/A333479

67 points by bmc7505 4y ago

Some discussion of remaining infinite BB(5) machines yesterday in [1][2] [1] https://www.sligocki.com//2023/02/02/skelet-34.html https://www.sligocki.com//2023/02/02/skelet-34.html [2] https://news.ycombinator.com/item?id=34689068 https://news.ycombinator.com/item?id=34689068 and

zabzonk 4y ago

i think the "Story" page might be a better link, i know about busy beavers, but those that don't might be a bit lost.

BubbleRings 4y ago
A bit? :)

Allezxandre 4y ago

Wikipedia [1] has a problem statement that I find explains the game quite simply: > the busy beaver game aims at finding a terminating program of a given size that produces the most output possible. The Busy Beaver Challenge website [2] also has an explainer page with interactive Turing Machines. [1] https://en.wikipedia.org/wiki/Busy_beaver https://en.wikipedia.org/wiki/Busy_beaver [2] https://bbchallenge.org/story https://bbchallenge.org/story

avmich 4y ago

So, about 88 millions of machines is left to test. We're interested in any, which runs longer than about 47 millions steps. Multiplying we get about 4.2e15 steps at worst. Can't we brute force the solution? It's like 5 million seconds - or less than two months - 1 billion steps a second, which looks doable for a modest system, and we don't even need much memory...

lukevp 4y ago
I think the problem is that some of the Turing machines are infinite, so getting 47 million steps in is the _entrypoint_ and you must then run until it halts (or you determine it’s not going to halt somehow). So the search space is unbounded, but it seems like you could snapshot the state of each machine at the 47 million steps and then incrementally search a couple thousand steps forward on each one looking for halting? I may be totally off though, I won’t pretend to fully grok this.
- deleted 4y ago
  [deleted]
- avmich 4y ago
  In "Story" website section: "This conjecture says that 47,176,870 is the maximum number of steps that a 5-state Turing machine can run before halting (starting from all-0 memory tape)." So, we can run up to this number and either the machine will stop - and we'll go to the next one until exhaust the whole set - or the machine won't stop, and we'll refute the conjecture.
  - teraflop 4y ago
    No, you seem to be misunderstanding the conjecture. It's about the maximum number of steps executed by a Turing machine that eventually halts. If you simulate a Turing machine up to that many steps, and find it hasn't halted yet, then the conjecture is refuted if you know the machine's execution will eventually terminate -- but famously, there's no algorithm that can reliably tell you whether or not a given TM halts. If it was just about the maximum number of steps that could be executed by a 5-state Turing machine, it would be trivially false, because it's easy to construct a Turing machine that runs forever.
    - avmich 4y ago
      Yeah, I was surprised the statement is constructed this way. Adding condition of eventual halting - which is what makes it the busy beaver - makes the difference :) .

ramraj07 4y ago

Scott Aaranson’s decades old “big numbers” write up which I think explains why this is useful and fun: https://www.scottaaronson.com/writings/bignumbers.html https://www.scottaaronson.com/writings/bignumbers.html

tromp 4y ago

For functional programming fans, there is an alternative definition of the busy beaver function as [1] the maximum normal form size of any closed lambda term of size n This has the advantage of having a higher "resolution" by measuring program size in bits rather than states. [1] https://oeis.org/draft/A333479 https://oeis.org/draft/A333479

tromp 4y ago
Oops; that link should be https://oeis.org/A333479 https://oeis.org/A333479