About the Turing Machine Simulation


The program TM.html implements a simulated Turing Machine. A Turing Machine is a very simple abstract model of computation. The machine has an infinite tape that is divided into cells (or squares). Each cell contains a symbol (or character) chosen from some small set of possible symbols. Most of the cells are blank, that is, they contain the blank symbol. The number of non-blank cells is finite. The machine is located on one of the cells, and it can only "see" the symbol in the cell where it is located. It can write a new value to that cell. It can move left or right on the tape, one cell at a time. The machine is in one of a fixed, finite number of possible states. One of the states is the halt state, which is shown in this simulation as "h". The other states are numbered 0, 1, 2, up to some maximum. Here is how the program shows a Turing Machine in state 5 on a tape containing the symbols "ba@ccaba ba" (but remember that the tape should be thought of as extending infinitely to the left and to the right):

Turing Machine on its Tape

A Turing Machine has a table of rules. The table of rules is the program for the machine. A rule tells the machine what action to take when it is in a given old state and the cell where it is located contains a given old symbol. The action specifies the new symbol to be placed in the cell (possibly the same as the old symbol), the new state that the machine should change to (possibly the same as the old state), and the direction in which it should move. The direction can be "L" to tell the machine to move left, "R" to tell the machine to move right, or "S" to tell the machine to stay in the same place. There are no rules for what the machine should do when it is in the halt state, since when it is in the halt state, it is done computing.

In the simulation program, a Turing Machine always starts in state number zero. It computes by following the applicable rule at each step, and it is done computing when it executes a rule that tells it to go into the halt state. The machine will also stop if it is in a situation for which there is no applicable rule, and you will see a message above the machine saying that no rule is available. A table of rules for the current Turing Machine is shown in the bottom right section of the web page.

See the Wikipedia article for more information about Turing Machines.


Using the Program

When TM.html is first loaded, it shows an example Turing Machine that can add one to a binary number. A binary number (that is, a sequence of zeros and ones) must be written on the tape, and the Turing Machine must be positioned on the right end of that number. Click the "Run" button, and the machine will add one to the binary number. It will then return to its original position and halt. To run it again, first click the button that says "Reset State to Zero" to return the machine to its initial state, then click "Run". There is a "Run Speed" pop-up menu that allows you to change the delay between steps in the program. As alternative to "Run" you can click the "Step" button, which executes just one rule in the machines's program. There is also a "Step Back" button that will undo one step in the execution; you can use it to "unwind" part of a computation so that you can replay it. "Step Back" can undo up to 100 steps.

You can use the mouse (or your finger on a touch screen) to drag the machine onto a different cell of the tape. You can also drag the tape back and forth, carrying the machine with it.

If you are using a mouse (but not a touch screen), you can change the machine's state by clicking the machine and then typing the new state. You will see a bright cyan-colored border around the state number when it is ready for input. Similarly, if you click one of the cells of the tape, a cyan box will be drawn around the cell, and you can type a new symbol for the cell. The cyan highlight will move one cell to the right, so you can type an entire string of symbols onto the tape. (There are also an input box and a button labeled "Set tape contents to:" that you can use to change the contents of the tape.)

The "Rule Editor" can be used to create or modify Turing Machine programs. The editor has five pop-up menus that contain the data for one rule. If a rule already exists for the "OldState" and "OldSymbol" in the first two pop-up menus, then the corresponding rule is highlighted with a magenta border in the table of rules, and the button to the right of the menu says "Change Rule". If no rule currently exists for the "OldState" and "OldSymbol", then the button says "Create Rule". As you step through the program, or as it runs at a slow enough speed, the Rule Editor is set to show the currently applicable rule. You can also click one of the rules in the table of rules to select it for editing.

Note that in the "OldSymbol" and "NewSymbol" menus, the blank character is shown as "#" to make it visible. The same is true in the "Old Symbol" and "New Symbol" columns in the table of rules.

The old symbol in a rule can also be a wildcard symbol, represented as "other" in the menu and in the table of rules. The wildcard matches any symbol that is not covered by another rule for the same state. The new symbol can also be a wildcard, represented as "same" in the menu and in the table of rules. When used for the new symbol, the wildcard means that the machine should not change the current symbol in the cell.

(If you are using a mouse (but not a touch screen), you can also edit an existing rule by clicking in the "New State", "New Symbol", or "Move" column in the table of rules and typing a new value. If you want to enter the wildcard symbol, you can enter it by typing a "*".)


The Sample Machines

Seven example machines are available in a pop-up menu under the button labeled "Install Example:". To load one, select it in the menu then click the button. The sample machines are as follows:


Saving Your Work

It is possible to save all the data for a Turing Machine program and tape, and you can load the saved data back into the program to use the machine again. Unfortunately, the method for doing that is kind of clunky...

Click the "Show Import/Export" button. This will pop up a dialog box that you can use for saving and loading Turing Machine descriptions. A Turing Machine and tape are described using a very strict data-representation format known as JSON. To see the JSON representation for the current machine, click the "Grab Current Example" button. You can then copy the machine description out of the dialog box and into a text editor window using copy-and-paste. Then, you can save the description from the text editor into a file. To load a saved machine description back into the program, you can open the file in a text editor, copy-and-paste the description into the Input/Export dialog box, and click the "Apply" button.

The same JSON format is used for the sample machines in the source code of the web page TM.html. See the source code of that page for more information about the format.

Advice about making new Turing machines: Start by clicking "New Turing Machine" and setting the contents of the tape and the initial position of the machine on the tape. If you then click "Step", the necessary rule won't exist, but the Rule Editor will be set up to create it. Set the pop-up menus for NewSymbol, NewState, and Direction to the appropriate values for the machine that you want to create, and click "Create Rule". Clicking the "Step" button will apply that rule — and will configure the Rule Editor for the next step. Continue in this way, clicking "Step" and creating rules when needed. If you get confused, use the "Step Back" button to back up a few steps in the computation. Eventually, you should have a machine that works for the input that you gave it. Then try it on a variety of different inputs, to make sure that you have all the cases covered.


David Eck