Feedback by Nicholas Drozd
Posted: Jan. 4, 2022
Hello DZ! In your Opinion 155 you make some skeptical remarks about
the "Busy Beaver" problem. Specifically, you say that it is either
meaningless (when interpreted incorrectly) or boring (when interpreted
correctly). The interpretation problem has to do with philosophical
commitments to the existence of infinite sets, which in your view make
no sense.
I would like to attempt to convince you of two things:
1. The Busy Beaver problem requires no commitments to infinite
anything; on the contrary, it is quite finite and well within the
range of what a computer can "understand".
2. It is a fabulously interesting case of experimental mathematics.
Every single concrete value that is known was discovered by
computer, and nothing at all can yield more new values except for
more computer searching.
If things go well, perhaps I can even convince you to take a crack at
an open problem. This problem is described at the end. (Feel free to
skip ahead.)
Now, the Busy Beaver question asks: what is the longest that a Turing
machine program of N states and K colors can run before halting when
started on the blank tape? We can think of "the" Busy Beaver problem
as a sequence of problem instances parameterized by N and K. Although
that sequence might go on "infinitely", no particular instance deals
with anything infinite. There are only finitely many programs of N
states and K colors.
In fact, there are approximately (NK)^(NK) of them. This value gets
out of hand quickly even for small values of N and K. There are
normalization techniques that can be applied to reduce this number
somewhat, and the fact that all programs are to be started on the
blank tape can also be exploited to reduce the program space under
consideration. But even these approaches become inadequate when N or K
gets too big.
Suppose we've pared the finite set of all N-state K-color TM programs
down to a reasonably small set of candidate programs. The next step is
to find which one among them runs the longest before halting. More
specifically, we're looking for a natural number S and an NK-program P
such that P halts after S steps and no NK-program halts after S steps.
There is no general method to upper-bound S in terms of N and K; for
if there were, it could be used to solve the halting problem.
Solving the Busy Beaver problem for NK-programs requires identifying
the "champion" program and also proving that it really is the champion
(that is, proving any other NK-program halts within S steps or doesn't
halt at all).
The proof part is tricky even in simple cases, and it isn't the kind
of "proof" that illuminates anything. A skeptic such as yourself might
describe it as meaningless or needlessly formalistic. Then again, the
1963 "proof" of the 3-state 2-color Busy Beaver problem was one of the
earliest cases of a computer-assisted proof. So maybe you will have
some sympathy for it. Keep in mind that there are only finitely many
cases to consider.
But finding the champion program is something that should in principle
be possible. It's a perfectly finitistic and constructive pursuit!
Once found, a champion program can be verified. For example, a 5-state
2-color program was discovered in 1989 that runs for 47,176,870 steps
before halting. Nobody had any clue that such a program existed until
it was discovered. Of course, it was turned up by computer search.
So we have our list of candidate programs, and we want to find the
champion. How would you go about doing this? It would be nice to be
able to run the programs forever and see which ones ultimately halt,
but obviously it's nonsensical to talk about running a program
"forever". We can only ever run programs for a finite number of steps.
Okay, so run all of them for T steps and see which ones halt. Great,
but how many steps is T? There doesn't seem to be any principled way
to decide on a good T; in practice it's determined by 1) how powerful
my computer is, 2) how long I'm willing to wait, and 3) my
out-of-thin-air estimate on the upper bound of S. The history of Busy
Beaver research is littered with estimates of S that turned out to be
comically wrong. I've even made a few stupid estimates myself!
I claim that there is no theory at all that can give a clue as to the
value of S. This makes the Busy Beaver search maximally experimental:
every single known value was a new empirical discovery.
You've said that computers will eventually make human mathematicians
obsolete. A practical way to understand the "undecidability" of the
Busy Beaver problem is that even computers will not be able to figure
it out in general. Nor, for that matter, could hyper-dimensional
pure-energy beings. Nobody can! Perhaps a few more values can be
figured out than humans can find, but anyone who tries will hit a wall
(and sooner rather than later). There will always be more to do.
Hopefully I've succeeded in showing that the Busy Beaver problem is
interesting to computer mathematicians. Is it interesting to
traditional mathematicians? I think so. Consider the function L on the
natural numbers:
* If n is divisble by 3, then L(n) = 0.
* Otherwise, n = 3k + r with r in {1, 2},
and L(3k + r) = L(5k + r + 3).
Is L total? That is, do we have L(n) = 0 for all n? It seems that way,
but nobody knows how to prove it.
The function L, which is closely related to the Collatz function, is
implemented by the 4-state 2-color Blanking Beaver champion program
mentioned above. Keep in mind that 4 states and 2 colors is a pretty
short program! But still it is long enough to implement a function
with a whiff of undecidability. (I don't think traditional
mathematicians have the right vocabulary for dealing with functions
like these, but that's a discussion for another day.)
OPEN PROBLEM
The classic Busy Beaver problem asks how long an NK-program can run
before halting when started on the blank tape. Here's a variation
called the Blanking Beaver problem: how long can an NK-program run
when started on the blank tape before the tape becomes blank again?
Call the classic Busy Beaver function BB and call the Blanking Beaver
function BLB. How would you estimate the rate of growth of BLB in
terms of BB? Do the values stay close together, or does one grow a lot
faster than the other?
It's been known for a few decades that BB(4, 2) = 107. That is, every
4-state 2-color program when started on the blank tape either halts
within 107 steps or doesn't halt at all. It's also known that BB(5, 2)
≥ 47,176,870 (by a program discovered in 1989) and that BB(2, 4) ≥
3,932,964 (by a program discovered in 2005).
Just in July 2021 I found a witnessing program that shows BLB(4, 2) ≥
32,779,477. So BLB seems to grow a lot faster than BB.
Okay, here's the OPEN PROBLEM: what is the value of BLB(2, 4)?
The best that I've been able to find is that BLB(2, 4) ≥ 190,524. That
isn't a very impressive value, but my feeling is that it isn't the
true value. We know that BB(2, 4) > BB(4, 2) and we know that BLB(4,
2) > BB(4, 2), so a reasonable hypothesis is that BLB(2, 4) > BLB(4,
2). Is that hypothesis true? I've argued that no theory can answer
this question, and that it's strictly a matter of experimental
computer-based mathematics.
Gee, if only there were someone who could help out in that domain!
Nick Drozd