> 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