Jun 97 Challenge
Volume Number: 13
Issue Number: 6
Column Tag: Programmer's Challenge
June 1997 Programmer's Challenge
by Bob Boonstra, Westford, MA
Turing Machine
A Turing Machine is a finite state machine augmented with an infinite amount of
external storage, formatted as a sequence of squares on a linear tape. The behavior of
the Turing Machine is described by a set of rules, each of which contains a current
state, an input symbol, a next state, an output symbol, and a move direction. At any
given time, the Turing Machine is described by the current internal state, the position
of its read-write head on the tape, and the contents of the tape. Each clock cycle the
Turing Machine reads the square of the input tape on which the read-write head is
positioned, replaces the contents of that square by writing an output symbol based on
the input and the current state, and moves left or right one square on the tape (or
halts). Because they have access to an unbounded amount of storage, Turing Machines
can solve problems that finite state machines cannot. An example of such a problem is
parenthesis checking. Given an input of left and right parentheses, delimited by the
special symbol 'A', such as:
0000A(()((())(((A0000
...the following set of rules will determine whether the parentheses are will-formed,
meaning that they can be paired off so that each left parenthesis has a balancing right
parenthesis:
State Input NewState Output
0 ) 1 X Left
0 ( 0 ( Right
0 A 2 A Left
0 X 0 X Right
1 ) 1 ) Left
1 ( 0 X Right
1 A 1 0 Halt
1 X 1 X Left
2 ( 2 0 Halt
2 A 2 1 Halt
2 X 2 X Left
This machine scans right in state 0 looking for a right parenthesis. When it finds one,
it moves to state one, replaces the right parenthesis with an 'X', and moves to state 1 to
scan for a left parenthesis., which it also replaces with an 'X'. If it encounters the 'A'
delimiter when looking for a balancing parenthesis, it halts after writing a '0',
indicating that the parentheses are not well-formed. If all parentheses are paired off,
it writes a '1' indicating the input is well-formed.
Your Challenge this month is to implement a Turing Machine. 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 { /* rule in program for TM */
ulong oldState; /* this rule fires when currentState ==
oldState and */
ulong inputSymbol; /* currentSymbol == inputSymbol */
ulong newState; /* set currentState to newState when this rule
fires */
ulong outputSymbol; /* write outputSymbol to tape when this rule
fires */
MoveDir moveDirection; /* move left or right as indicated when this
rule fires */
typedef void (*TMMoveProc) (
ulong outputSymbol,
ulong newState,
MoveDir moveDirection
);
Boolean /* success */ TuringMachine(
const TMRule theRules[], /* pointer to program for TM */
ulong numRules, /* number of rules in TM program */
ulong *theTape, /* pointer to input tape for TM */
ulong tapeLen, /* theTape[0]..theTape[tapeLen-1] is
valid */
long rwHeadPos, /* TM read head is at theTape[rwHeadPos]
*/
TMMoveProc ReportMove /* callback proc to inform caller of each
move */
);
On input, your TuringMachine will be provided with numRules rules governing
the behavior of the Turing Machine. The rules are pointed to by theRules. You will
also be provided with a input tape pointed to by theTape, with a finite number of
contiguous squares preinitialized to the Turing Machine input. The read-write head
will be positioned on the input tape at theTape[rwHeadPos]. All other squares of the
input tape will be empty, indicated by a binary zero. Your TuringMachine should
begin in state 0, read the first input symbol, and find the appropriate rule. It should
invoke the callback ReportMove to inform my test code of what your machine is
doing, providing the outputSymbol that you will write to the tape, the newState of
your finite state machine, and the moveDirection for the new position of the
read-write head. You should then update theTape, move your read-write head, and
update the Turing Machine state.
When your TuringMachine encounters a rule with a moveDirection of kHalt, you
should make a final callback to ReportMove and then return TRUE. If your TuringMachine exceeds the tapeLen of theTape, or if you are unable to find a rule
that applies to your current machine state and the input symbol, you should return
FALSE. It is my intent to provide all necessary input rules and a sufficient length of tape, but your machine should fail gracefully if an input bug or an implementation bug
results in running out of tape or encountering a bad input symbol.
Your code will be timed with a sequence of rule/tape pairs, and the solution that
completes execution of the inputs correctly in the shortest total time will be the
winner. Half of the tests will use a "universal" Turing Machine, where the rules
describe a general Turing Machine interpreter, and the input tape contains another
Turing Machine program. The time executed by the ReportMove callback will be
included in your solution time. The callback will look something like the following.
static void ReportMove(long outputSymbol, long newState, MoveDir
moveDirection)
if ((gTapePos>=0) && (gTapePos
gTape[gTapePos] = outputSymbol;
gTapePos += moveDirection;
gState = newState;
}
You may not modify the input rules pointed to by theRules, but you may allocate
reasonable additional storage if you would like to preprocess the rules in some way,
provided you deallocate the storage before returning.
For those of you that would like additional information on Turing Machines, you can
refer to almost any textbook on automata theory or the theory of computation. My
personal favorite is Computation, Finite and Infinite Machines, by Marvin Minsky, ©
1976 by Prentice-Hall.
This will be a native PowerPC Challenge, using the latest CodeWarrior environment.
Solutions may be coded in C, C++, or Pascal.
Three Months Ago Winner
Congratulations to Gregory Cooper for narrowly defeating the second place entry by
Jeff Mallett in the March Hex Challenge. Hex is played on an NxN rhombus of
hexagons, with players alternately occupying hexagons, one playing vertically and the
other horizontally, each trying to complete an unbroken chain before the other does.
The Challenge awarded 10 points for each victory in a round-robin tournament, with
the score reduced based on the execution time of the winning solution.
The third-place solution by Eric Hangstefer used a purely offensive strategy, building
bridges in an attempt to force the opponent to play defense. The other two solutions
applied both offensive and defensive techniques, and between them won all of the games
in the tournament. Gregory's solution plays defense whenever it believes that its
opponent is closer to a solution than he is. To accomplish this, he maintains a Path data
structure for himself and for his opponent identifying what he believes to be the best
(shortest) path across the board for each player. A path score is maintained by
counting the number of hexagons along the path that still need to be occupied to