# Busy Beavers (was: God's Own Algorithms)

## Brent Kerby — 2002-04-07 06:24:43

    > And for a more practical and hands on approach on something

    > approaching the problem domain. The record busting 'Busy Beaver' program

     by

     > Heiner Marxen. The problem is literally leading you neck deep into the

     dirtiest pool

     > of the mathematical swamplands.

    >

    > MvH Dan Andersson

     This is fascinating. By the way, Heiner's page on Busy Beavers can be found

    at <http://www.drb.insel.de/~heiner/BB/index.html>. Also, if you're like me,

    and are a bit fuzzy on what precisely Turing Machine's are, see the link

    <http://wap03.informatik.fh-wiesbaden.de/weber1/turing/>, which has a nice

    explanation on Turing Machines and includes a Java simulator, which has

    helped make things seem more concrete to me.

    What's interesting is that this Busy Beaver problem has a direct analogue in

    a Joy combinator system. That is, try to find the program that takes the

    longest time to terminate (but nevertheless still terminates) and that

    leaves the largest amount of junk on the stack. After a quick and dirty

    modification to my searcher, I found that these programs (using base {i,

    cons, dip, dup}) are probably the ones that take the longest to terminate (a

    "substitution", below, refers to an execution of a primitive, like "dup" or

    "i"; execution of quotations are not counted):

      size 6: [dup] dup i i i                     (7 substitutions)

      size 7: [dup dup] dup i i i                 (10 substitutions)

      size 8: [] [cons dup i i] dup i             (18 substitutions)

      size 9: [] [cons dup i i i] dup i           (32 substitutions)

     size 10: [] [dup dip dup dip] dup cons dup i (240 substitutions)

    There were several ties, which I omitted above, and these results are not

    guaranteed to be the best (but if there is a better one of size 9 or less,

    it must take over 5000 substitutions).

    Also I only considered a program to be valid if it functions properly with

    an initially empty stack.

    Anyway, here the programs that leave the most trash on the stack (counting

    total size, not just number of items):

      size 6: [dup dup dup] dup i                (16 big)

      size 7: [dup cons dup dup] dup i           (30 big)

      size 8: [dup cons dup dup] dup i i         (50 big)

      size 9: [dup cons dup dup dup] dup i i     (84 big)

     size 10: [] [cons cons dup i dip] dup dup i (762 big)

    These also are not guaranteed to be the best (although they may well be).

    Also, for this search, I treated quotation as being opaque; this means that

    some of those above programs may actually be non-terminating if you treat

    quotation as transparent. To put it another way, some of the above programs

    may leave trash on the stack that is non-terminating (thus the above

    programs might be non-terminating, if you reach inside the resulting

    quotations and reduce them also).

    Anyhow, like before, there are several possible ways of formalizing this

    exactly, by varying how much size a quotation is worth (maybe 2 instead of

    1), or by treating quotation as transparent.

    Anyway, I thought you all might find that curious :-)

    By the way, a base that includes "rep2" (== dup dip i) turns out to be far

    more "busy" (; a base with "rep3" is even more so. This makes sense, of

    course; "rep" combinators are naturally very useful when you want to prolong

    a computation.

    - Brent