June 1997 Programmer's Challenge

Turing Machine

Mail solutions to: progchallenge@mactech.com

Due Date: MIDNIGHT, EDT, 1 June 1997

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:

This machine scans right in state 0 looking for a right parenthesis. When it finds one, it moves to state o 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 */
} TMRule;

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<gTapeLen))
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, (c) 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.