Turing Machine Submissions

A Turing Machine is a Finite State Machine with the addition of an infinite one-dimensional tape for storage. If you do not know how to use finite state machines, you should read this before continuing.

For problems designated TM only (problem numbers in the 9500 range), programs written in normal programming langauges will be rejected. All submissions must be specifications of Turing machines that perform the required task. TM specifications are interpreted, not compiled in the normal way. The source code for the TM interpreter used may be down-loaded here. This is not standard software; the only way to test TM specifications before submitting them is by running this interpreter. The remainder of this file explains the use of the interpreter and the format of an TM specification.

Using the Interpreter

The interpreter is designed to be used from the command line. In the following, it is assumed that it has been compiled using "CC tm.cpp -o tm", so the executable is called tm.

The TM specification should be stored in a perfectly normal human-readable text file. If your TM specification is in a file called p9501.tm, then the simple way to run it is "tm p9001". (if the filename ends with .tm the .tm may be elided). The interpreter first checks that the TM specification is valid and deterministic, then executes it. The test input is written onto the tape before the program starts, and the results are read from the tape when it halts. If the option -list is specified (e.g. "tm -list p9501") the TM rules are printed as they are read (but in a different format) for checking that it is understood correctly. If the option -trace is specified (e.g. "tm -trace p9001") the current state of the TM, followed by the portion of the tape closest to the read/write head (the character directly under the head is displayed inside [ and ] for clarity) is printed before each transition occurs. Execution stops as soon as the machine enters a designated halting state.

Input to a Running TM

Once the TM is accepted as syntactically correct and deterministic, the test input is transferred to the tape. Unless otherwise specified in the problem statement, the test input will be preceded by a < character and followed by a > character to provide a clear indication of where it begins and where it ends (i.e. the input is enclosed in pointy-brackets). The read/write head is positioned directly over the initial < before the machine starts running.

When running, the machine selects a transition matching the current state and the character directly under the read/write head. It is a run-time error if no transition matches that pair of values. The matching transition must specify the new state of the machine, the character to be written to the tape (overwriting the input character) and the direction in which the read/write head is to move after overwriting the input (L for left, R for right, and N for no movement).

The machine will continue to run until it enters a halting state, at which point it will unconditionally stop. When the machine stops, the correct output must have been written to the tape. Anything directly under the read/write head or to the left of it, is completely ignored. The output must appear immediately to the right of the read/write head. The output should not include a newline \n character unless the problem statement explicitly demands one. The output is considered to end at the first ASCII zero character \0 or at the first unused tape position.

TM Specifications

The general rules are:

Blank lines are permitted and are ignored.
The two character sequence // introduces a comment; the rest of the line is ignored.
States may be given any names that consist of a squence of letters, digits, dollar-signs, underlines, and dots. Case is not relevant in distinguishing states.
A TM specification may contain one line saying START=state. If such a line is present, the TM begins execution in the indicated state. Otherwise the start state is the first state mentioned in the specification.
The transitions for each state are started with the name of that state followed by a colon. This sequence may be alone on a line, or it may appear at the beginning of one of the transitions.
The transitions for each state do not need to be grouped together, there may be more than one name: entry for each state. All transitions following name: are taken as transitions for the named state and added to any others already provided.
Between the name of a state and its colon, the word HALT in parentheses may appear (e.g. LAST(HALT):). This designates the named state as a halting state. There may be any number (except zero) of halting states. Transitions for a halting state may be specified, but there is no point, as they will never be used.
There may be any number (including zero) of transitions following name:.
A transition consists of the input character that triggers it, followed by an arrow ->, followed by exactly three items: (1) the name of the resulting state; (2) the output character that is to overwrite the input character on the tape; (3) either L, R, or N, indicating the direction in which the read/write head is to move after writing the output character (N=no movement).
Any number of input characters may used to trigger a transition. If there is more than one, each should be separated from the others by spaces or tabs. For example, the one transition
a b x -> S2 z R
is equivalent to this sequence of three transitions a -> S2 z R b -> S2 z R x -> S2 z R
A contiguous range of characters (for example c d e f g h) may be represented by writing the first and last separated by a dash (for example c-h). This notation may only be used when both given characters are visible (ascii 33 to 126) and in the right order (e.g. not h-c).
Ranges and individual characters may be combined in a single transition, for example
a-z A-Z 0-9 -> S2 - L
defines a transition that is triggered by any letter or digit.
When used as an input character, the star * means "any character not explicitly listed in any other transition from this state".
Transitions must be deterministically selectable, so no two transitions from the same state may include the same input character, and no two transitions from the same state may include a star.
When used as an input character
- \s represents a space,
- \t represents a tab,
- \n represents a newline,
- \* represents a star (i.e. Not "any other character"),
- \\ represents the character \,
- \abc (where abc are octal digits) represents the character with ascii code abc₈.
After the -> and the new state name, the single output character must follow. Whenever the transition occurs, that character overwrites the input character on the tape. The same special \x character sequences are used for output as for input.
The character * when used to specify output, represents whatever input character caused the transition (and therefore has the effect of not overwriting the input character). For example
a-z A-Z -> S2 * L
means that any letter causes a transition to state S2, leaving that letter on the tape, before moving the read.write head one position to the Left.

Example Program

This Turing Machine verifies that the input is exactly the string CAT. The job of the start move right from the <. The chkC state checks that the next character is C, if it is, it moves on the chkA, otherwise it moves into the error state bad. chkA and chkT are almost identical; chkn makes a similar check for the > immediately following the last letter. The bad state simply searches for the closing >, after which the no state writes an N on the tape. The ok state is only used if chkn is successful, so no search is required, it just writes they Y to the tape. Both ok and no move the head left before entering a halting state, so that the correct output will appear immediately to the right of it.

// id=1111 code=CODE lang=TM prob=9501
start: < -> chkC  * R
chkC:  C -> chkA  * R
       * -> bad   * R
chkA:  A -> chkT  * R
       * -> bad   * R
chkT:  T -> chkn  * R
       * -> bad   * R
chkn:  > -> ok    * R
       * -> bad   * R
bad:   > -> no    * R
       * -> bad   * R
ok:    * -> stop  Y L
no:    * -> stop  N L
stop(HALT):

When running, the interpreter expects the user to provide a single line of text, newline-terminated. That text (without the newline) is written onto the tape, surrounded by < and >, and the read/write head is positioned immediately over the initial < before the machine starts running.

If you use the -multi option to the tm command, the system will accept multiple lines of input. The first line is read and prepared as described above, and the machine is run until it terminates, and the output (between the read/write head and the first \0 exclusive) is displayed. Then the machine is completely reset to its initial condition, the tape is erased, and the second line of input is processed in exactly the same way. This continues until there is no more input.

Sample Run: (assuming the above example is in the file vercat.tm)

$ tm vercat
CAT
Y

Sample Debugging Run:

$ tm -trace vercat
CAT
          start: [<]CAT>
           chkc: <[C]AT>
           chka: <C[A]T>
           chkt: <CA[T]>
           chkn: <CAT[>]
             ok: <CAT>[\0]
           stop: <CAT[>]Y

OUTPUT FOLLOWS
Y

Sample Multiple Run:

$ tm vercat
CAT    
Y
Cat    
N
abraCATabra    
N
^D