A Turing Machine Simulator Program

1. Introduction

The Turing Machine Simulator program simulates the execution of a Turing Machine by allowing the generation and execution of small Turing Machine programs consisting of quintuples of symbols (current state, current symbol, next symbol, next state, head movement).

The Turing Machine Simulator IDE (Integrated Development Environment) displays four windows:

  1. Turing Machine Window: Displays the Tape, the Read/Write head, and the Current State. As a Turing Machine program executes, the R/W head moves back and forth over the Tape while the display for the Current State changes.
  2. Status Window: Displays the position of the R/W head, the number of steps executed by the Turing Machine, the Quintuple to be executed next, and the "status" of the Turing Machine (running, halt, interrupt etc). This is useful for "single stepping" the execution of a Turing Machine program.
  3. Edit Window: A small built-in editor allows the user to create and edit files of Turing Machine quintuples which then can be executed.
  4. Menu Window: Menu to display current user options. Contents change depending on the current selection.
The entire IDE is highly interactive meaning a user can create a small Turing Machine program, set up a tape for the Turing Machine, run the program on that tape (a single step option is available), and if mistakes are found, go back to the editor and make changes. The final Turing Machine program can be saved to a file and later recalled.

The Turing Machine Simulator was written in Borland's Turbo Pascal for DOS (v6.0) to run under MS-DOS. I've also run it under Windows 3.1, Windows 95 and WindowsNT. The Turing Machine Simulator is provides "as is".

To down load a WinZip file containing the Emulator program plus some documentation (txt & pdf), Click Here.

Alternately you can find a short cut to the Turing Machine Emulator program at

Q:\Computer Science\Icons\Turing

2. Notes

The format of a Turing Machine quintuple must be strictly followed. Quintuples consist of fove fields separated by commas and enclosed by parentheses. The fields are 
     current state
     current tape symbol
     next symbol (written to tape)
     next state
     head movement (Left, Right, or Stay)
A quintuple causes a transition if the Turing Machine's current state and current tape symbol under the R/W head match the first two components of a quintuple. When a match occurs, the next symbol is written to the tape overwriting the current tape symbol, the next state becomes the new current state, and the R/W head moves left, right or stays in place depending on the value of the fifth component of the quintuple.

Example: The quintuple (A,1,x,B,R) will cause a transition if the current state is A and the current tape symbol under the R/W head is 1. It will overwrite the 1 with an "x", go to state B, and move the R/W head one position to the Right.

States are restricted to letters and digits and may be one or two characters long. States are case-sensitive.

A tape symbols can be any single character EXCEPT a comma and are case-sensitive. However, since the Turing Machine window displays a blank as a dot (making the tape easier to view) avoid using periods as tape symbols since you cannot distinguish periods from blanks. Blanks and periods are different tape symbols but are displayed the same.

Head movement symbols are R (or r) for Right, L (or l) for Left) and S (or s) for Stay. For clarity you should avoid using them as State or Tape symbols.

Avoid using the "?" as a tape or state symbol since it's used to indicate a quintuple whose current state/tape symbol was not found and the initial undefined machine state.

Quintuples must have the correct format (five fields separated by commas and enclosed in parentheses). If the syntax of a quintuple is incorrect, it will be ignored. This Turing Machine Simulator is deterministic so no two quintuples should have the same values for current state/current tape symbol. (The second will overwrite the first.)

Characters to the right of the closing parenthesis of a quintuple are ignored so comments may be "attached" to quintuples. See example.

Turing Machine configurations (current state/current tape symbol) which do not match the first two components of any quintuple will halt the machine. I use the convention that any state which does NOT appear as the first component of a quintuple (therefore halting the machine) is an Accept State.

The range of tape positions runs from -1000 to +1000. If the Turing Machine attempts to go beyond this range, a "tape error" will occur.

Hitting [F1] will display a Help Screen. Hitting (Esc) will interrupt a running Turing Machine program and generally exit any selected option thereby returning you to the Main Menu

3. A Sample Turing Machine Program

The following Turing Machine program detects palindromes made up of strings of 0's and 1's. Starting in state A it reads (and erases) either a 1 or a 0 changing its state to B or C to "record" that a 1 or 0 was read. It then moves right to locate the right end of the string where it backs up (moves left) and tries to match a corresponding 1 or 0. If successful, it move left to the beginning of the string and repeats. 
             - Palindrome Detector for strings of 0's and 1's
             - A is Start State; Z is Accept State
(A,1, ,B,R)  - detect 1 - store as state B
(A,0, ,C,R)  - detect 0 - store as state C
(A, , ,Z,R)  - empty string - done! (even number) 
(B,0,0,B,R)  - go right
(B,1,1,B,R)
(B, , ,D,L)  - end of string detected - go back
(C,0,0,C,R)  - go right
(C,1,1,C,R)
(C, , ,E,L)  - end of string detected - go back
(D,1, ,F,L)  - found 1, cancel it, & go back 
(D, , ,Z,L)  -   or found blank - done! (odd number)
(E,0, ,F,L)  - found 0, cancel it & go back
(E, , ,Z,L)  -   or found blank - done! (odd number)
(F,0,0,F,L)  - go back 
(F,1,1,F,L)
(F, , ,A,R)  - beginning of string detected
State Z is the Accept State since no quintuple begins with Z.

4. Executing a Turing Machine Program

  1. From the Main Menu select the Editor option and enter your program in the Edit Window. The Turing Machine uses the quintuples from the last edit session. To exit the Editor go to the Main Menu.
  2. From the Main Menu select Tape and create an input tape. The arrow keys will move the R/W head if you need to go back and make a correction (overwrite mode only). Position the R/W header back at the first character of the tape. When done hit (Enter) or (Esc). Ctrl/Y will erase the entire tape.
  3. From the Main Menu select State and enter the Starting State at the prompt. The current state appears as part of the R/W head.
  4. If you forgot to position the R/W head on the first character of the tape, select Move Head and position the R/W head.
  5. From the Main Menu select either Go or 1 Step to execute the program. Use (Esc) to halt a run-away program.