About the Turing Machine Simulation


The web app TM.html implements simulated Turing Machines. 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 machine'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.) If you are using a mouse (but not a touch screen), you can also edit an existing rule by clicking a value in the "New State", "New Symbol", or "Move" column in the table of rules and then typing a new value.

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.

The "New Turing Machine" button lets you start creating a Turing machine from scratch. It will pop up a dialog where you can enter a name and description of the machine. You can also specify the maximum state number that can be used in the machine and the set of symbols that can occur on its tape. The only way to change all of this information after creating the machine is with the "Show Edit/Import/Export" button.

Advice about making new Turing machines: Start by clicking "New Turing Machine" to create a new machine with an empty table of rules. Add some symbols to the tape, and set the initial position of the machine on the tape. If you then click "Step", no applicable rule will exist, but the Rule Editor will be set up to create the required rule. Set the pop-up menus in the Rule Editor 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. That might require creating more rules.

Saving your work: The "Save file" button lets you save the current Turing machine and its tape to a local file on your computer. Files saved in this way can be reloaded into the app using the "Load file" button. The mechanism used for working with local files will depend on what web browser you are using. In many browsers, it will look like saving and opening files in other applications. But in some browsers, when you save a file, it will look like you are downloading a file from the Internet, and loading a file can look like uploading a file.

The "Show Edit/Import/Export" button lets you edit the specification of the current machine. It also provides an alternative way to work with local files. The machine's specification is in a data format called "JSON." Clicking the button will pop up a dialog where you can view and edit Turing machine specifications in JSON format. To see the JSON representation for the current machine, click the "Grab Current Example" button in the dialog. You can edit the description and click the "Apply" button to apply your changes to the current machine. To save the machine to a file, you can 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 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:


David Eck