Sep 00 Challenge
Volume Number: 16
Issue Number: 9
Column Tag: Programmer's Challenge
Programmer's Challenge
by Bob Boonstra, Westford, MA
Busy Beavers
Before we get to this month's Challenge, I have to confess being a little distracted. No,
not because the annual holiday up at the lake is just a few days away, although I'll also
confess that the prospect of a couple of weeks away from the Real Job is most
appealing. No, the distraction is because UPS just delivered another addition to the
family of computers at the Boonstra household. The most recent additions have been
iMacs for the Junior members of the family, but this one is for Me. A new G4. No, not
one of the new dual-processor models introduced by Apple at JavitsWorld. (Those of us
in Boston cannot acknowledge use of the term MacWorld for anything on the Right Coast
that doesn't happen in Bean Town.) Dual processors might mean something to those
PhotoShop users among you, but they don't do much for the Rest of Us until Mac OS X
comes along. No, the new addition is one of those now-obsolete single-processor
G4-500 models that have (finally) dropped a little in price. As those of you who
participate in the Challenge contests know, I've been limping along with an old 8500,
enhanced over the years with a faster 604e, then a dual 604e upgrade (BeOS, oh BeOS,
wherefore art thou BeOS?), and finally with a G3 board. Several readers have asked in
the past about whether AltiVec technology could be used in the Challenge, but, sadly, I
didn't have a G4 to use in the evaluation. A problem now rectified, or at least it will be
once I complete the file transfers proceeding even as I write.
Now that you all know about my new toy, we can get on to the business at hand. This
month's problem was suggested by F. C Kuechmann, who earns two Challenge points for
the suggestion. Your Challenge this month is to create a Busy Beaver Turing Machine
and write a program that simulates its execution.
The Busy Beaver problem was invented in the early 1960s by Tibor Rado of Ohio State
University. He asked the following question about 2-symbol Turing machines: what is
the largest number of 1s that a Turing machine with n states could write to a tape
initially filled with 0s. That "busy beaver" number, or BB(n), has some interesting
properties. For example, by reasoning about the Halting Problem, one can show that
BB(n) grows faster than any computable sequence.
An internet search shows that the Busy Beaver problem continues to attract interest.
Until 1985, the largest value for a 5-state busy beaver produced 501 1s. Then George
Uhing found a 5-state machine that produced 1915 1s before halting. And in 1987,
Heiner Marxen (and Jürgen Buntrock showed that BB(5) is at least 4098.
For reference, you can start with the following URLs: Marxen's page at
<http://www.drb.insel.de/~heiner/BB/index.html>, and
<http://grail.cba.csuohio.edu/~somos/bb.html>
The prototype for the code you should write is:
typedef unsigned long ulong;
typedef enum {kMoveLeft=-1,kHalt=0, kMoveRight=1} MoveDir;
typedef struct TMRule { /* Turing Machine rule */
ulong oldState; /* this rule applies when the
machine state is oldState */
Boolean inputSymbol; /* and the current input symbol is inputSymbol
*/
ulong newState; /* set current state to newState
when this rule fires */
Boolean outputSymbol; /* write outputSymbol to tape when this
rule fires */
char moveDirection; /* kMoveLeft, kMoveRight, or kHalt */
ulong /* return number of rules */ BusyBeaver5(
TMRule theTMRules[],
/* preallocated storage, return the rules for your BB
machine */
);
Boolean /* return true for success */ RunTuringMachine(
TMRule theTMRules[],
/* preallocated storage, return the rules for your BB
machine */
ulong numberOfTMRules,
/* the number of rules in theTMRules */
ulong numBytesInHalfTape,
/* half-size of the "infinite" Turing Machine tape */
unsigned char *tmTape,
/* pointer to preallocated Turing Machine tape storage */
/* Each byte contains 8 tape symbols, each symbol is 0 or 1.
*/
/* The tape extends from tmTape[-numBytesInHalfTape] to
tmTape[numBytesInHalfTape -1] */
/* Tape position 0 is (tmTape[0] & 0x80),
tape position 1 is (tmTape[0] & 0x40)
tape position -1 is (tmTape[-1] & 0x01), etc. */
ulong *numberOf1sGenerated,
/* return the number of 1s placed on the tape */
ulong *numberOfRulesExecuted
/* return the number of rules executed when running BB, including
the halt rule */
);
The first thing you need to do is to select the 5-state Busy Beaver Turing Machine that
you will simulate in your RunTuringMachine routine. Since scoring is based on how
busy your beaver is, that is, on how many 1s it produces on the simulated Turing
Machine tape, you want to give some careful thought to this selection. This Turing
Machine should returned by your BusyBeaver5 using the TMRule data structure.
BusyBeaver5 may return a hard-coded Turing Machine; it does not need to identify the
busy beaver at run time.
My test code will then provide the output of BusyBeaver5 to your RunTuringMachine
routine, which should simulate the execution of the input Turing Machine.
RunTuringMachine will be provided with a blank (zero-filled) tape tmTape that is
2*numBytesInHalfTape in size. The "read head" of the Turing Machine is initially
positioned over position [0] of the tape. On exit, tmTape should contain the output of
the Turing Machine being simulated. In addition, you should return in the appropriate
output parameters the number of 1s on the output tape and the number of state
transitions that occurred during your execution of the Turing Machine.
RunTuringMachine should return TRUE if it was able to successfully execute the
Turing Machine, and FALSE if it failed for some reason, such as running out of
simulated tape. (It is not my intention to provide a simulated tape that is too short,
but your code should fail gracefully if that happens during testing.)
RunTuringMachine must provide a general Turing Machine simulation, not dependent
on the Busy Beaver problem or on the content of the initial input tape. I may choose to
verify correctness of your RunTuringMachine code against other input besides that
produced by BusyBeaver5.
The winner will be the solution that identifies the 5-state Busy Beaver generating the
most 1s on the output tape. Among solutions with equal numbers of 1s, the solution
that produces the output in the fewest number of Turing Machine steps will be the
winner. And, for solutions that produce the same output in the same number of steps,
the winner will be the solution that executes the Turing Machine in the least execution
time. While my hope is that one of you might break new ground in the field of busy
beaver research, my expectation is that the winning solution will be determined by the
execution time criterion.
This will be a native PowerPC Challenge, using the CodeWarrior Pro 5 environment.
Solutions may be coded in C, C++, or Pascal. As is our tradition for the September
Column, we'll also allow solutions that are completely or partially coded in assembly
language. And, yes, this time you can take advantage of the AltiVec features of the G4.
Three Months Ago Winner
Congratulations to Willeke Rieken (The Netherlands) for submitting the winning
solution to the June Rub*k Rotation Programmer's Challenge. Readers may recall that
the Rub*k Rotation Challenge required contestants to display an image of the famous
puzzle and respond to commands to rotate the entire cube or individual cube faces.
Scoring was based on correctness of the solution, in this case the smoothness of the
displayed rotations, and on execution time.
The fact that Willeke was the only person to submit an entry does not detract from his
solution in the slightest, although it did significantly increase his chances of winning.
(You can't win if you don't play!) Willeke elected to use QuickDraw3D to implement
his solution, motivated by a desire to gain some experience with the QD3D API. His
code creates 26 individual cubies (the center cubie is never visible) using the
AddCubie routine. Although it might look like a lot of work to set up the cube, the effort
pays off in the simplicity with which one can rotate the cube (RotateCube), turn a face
of the cube (QuarterTurn), and draw the entire cube (DrawCube), regardless of
orientation.
With only one entry, I'll omit the usual table describing the parameters of the
solution, and simply observe that this victory vaults Willeke into 4th place in the
overall Challenge standings. And remember, you can't win if you don't ...., oh, I'm
repeating myself.
Top Contestants
Listed here are the Top Contestants for the Programmer's Challenge, including
everyone who has accumulated 10 or more points during the past two years. The
numbers below include points awarded over the 24 most recent contests, including
points earned by this month's entrants.
Rank Name Points
1. Munter, Ernst 245
2. Saxton, Tom 126
3. Maurer, Sebastian 78
4. Rieken, Willeke 65
5. Boring, Randy 50
6. Shearer, Rob 47
7. Taylor, Jonathan 26
8. Brown, Pat 20
9. Heathcock, JG 16
10. Downs, Andrew 12
11. Jones, Dennis 12
12. Day, Mark 10
13. Duga, Brady 10
14. Fazekas, Miklos 10
15. Murphy, ACC 10
16. Selengut, Jared 10
17. Strout, Joe 10
There are three ways to earn points: (1) scoring in the top 5 of any Challenge, (2)
being the first person to find a bug in a published winning solution or, (3) being the
first person to suggest a Challenge that I use. The points you can win are:
1st place ›20 points
2nd place ›10 points
3rd place ›7 points
4th place ›4 points
5th place ›2 points
finding bug ›2 points
suggesting Challenge ›2 points
Here is Willeke's winning Rub*k Rotation solution:
RubikRotation.c
Copyright © 2000
Willeke Rieken
/*
draws (a simplified version of) Rubik's cube and animates
rotations of the cube and of the faces of the cube.
I'm using QD3D because I never used it and it seemed
more fun than a diy method and drowning in sin and cos