The xTuringMachine Applet

TURING MACHINES are very simple computational devices. A Turing machine has an infinitely long tape, divided into cells. Each cell can be blank or can contain a symbol chosen from some fixed finite list. The Turing machine moves along the tape reading and writing symbols. It has an internal state, which can be either the halt state or an integer between zero and some specified maximum value. When a Turing machine enters the halt state, it stops computing. Although Turing machines are very simple, any computation that can be done by any computer can also be done by some Turing machine.

The action that a Turing machine takes depends only on its state and on the symbol displayed in the cell where the machine is currently located. Given this information, the Turing machine takes three actions: It writes a symbol to the cell (possibly the same one that is already there); it moves one cell to the left or one cell to the right; and it sets its internal state (possibly to the same state that it is currently in). The Turing machine has a table of rules that tells it what to do for various combinations of its current state and the symbol it reads from the current cell.

The xTuringMachine applet is designed to show Turing machines in action. The Turing machines that it works with have a maximum of 25 states, and they can only use the symbols 0, 1, x, y, z, and $. Nevertheless, they can do some non-trivial computations. The applet is set up to load several sample machines. More information about the applet can be found below.

This applet was originally written by David Eck for use with his introductory computer science textbook The Most Complex Machine. However, it can also be used on its own.

For a list of other applets and for lab worksheets that use the applets, see the index page.

Sorry! Your browser doesn't do Java!

About the Applet

A pop-up menu at the very top of the applet can be used to select machines that were loaded by the applet at start-up or that have been created by the user. Selecting "[New]", the first item in the menu, will create a new, empty machine.

Just below the applet is the machine itself, sitting on an infinite tape. The tape is divided into cells, and each cell either contains a symbol or is blank. The machine itself sits over one of the cells and displays its current state. By convention, the machine starts out in state zero. When it is in the halt state, it displays an "h". (This area of the screen is also used to display messages; the machine will be there when you dismiss the message.)

On the left side of the applet below the machine is a set of controls. The first control is a pop-up menu that controls the speed of the applet when it computes. The "Run" button makes the machine start computing; when you click it, it changes into a "Stop" button. The "Step" button makes the machine perform one step in its computation. The "Clear Tape" button does just that. The "Delete Rule" button can be used to delete one rule from the rule table. (It is only active when a rule has been selected. The selected rule is shown in red; you can select a rule by clicking on it.) The "Load File" and "Save" buttons are used to work with files. Your browser might not permit you to use them.

The table of rules is in the lower right section of the applet. Each rule tells the machine what to do if it is in a certain state and if it reads a certain symbol. The "Move" column tells the machine which direction to move: "L" for left and "R" for right. You can edit the "Write," "Move," and "New State" columns.

The columns labeled "Reading" and "Write" can contain the symbols $, 0, 1, x, y, and z. They can also contain the character "#", which is used to represent a blank cell. The "Reading" column might also contain "other", which represents a default value that means "any other symbol for which no explicit rule is given." If the "Reading" column contains "other", then the "Write" column can contain "same", which tells the machine to write the same character that it read.

Just above the rule table is a "rule maker" with a "Make Rule" button that can be used to add new rules to the table. The blue rectangle between the machine and the rule maker is a "palette" that is used in making and editing rules, changing the contents of the tape, and changing the current state of the machine. This is explained in the next two sections.

When the machine is running at "Moderate" speed or slower, after each step the applet displays the next applicable rule in the rule maker box -- so you can see why the machine takes the action it does. If there is no applicable rule in a give situation, the machine will stop and will display the message "No Rule Defined!" You could then use the rule maker to make the missing rule.

If the machine moves outside the applet as it is computing, the machine along with its tape will jerk back about 1/4 of the width of the applet. (By the way, if you somehow lose the machine off the edge of the applet, clicking the "Run" or "Step" button will make it reappear.)

Using the Mouse

It is possible to work with the xTuringMachine applet using only the mouse (and completely avoiding the keyboard). Here's how.

Before you can edit any item, it must be "hilited." The currently hilited item, if any, is surrounded by a bright blue-green outline. You can always hilite an editable item by clicking on it. Whenever an item is hilted, the palette will display a list of legal values for that item. (The palette is the blue rectangle just below the machine.) You can choose one of these values by clicking on it. You can also type the value you want.

As long as the Turing machine is not running, you can edit the current state of the machine and the contents of the tape. Click on the machine or on one of the tape's cells, then select a value from the palette. When you enter a symbol for the tape, the hilite moves one cell to the right.

You can edit the "Write", "Move", and "New State" columns of the rule table at any time, even while the machine is running. Click on the item you want to change, then select a value from the palette.

The rule maker is somewhat more complicated. The rule maker lets you set up one rule by editing any of the five values for that rule. To set up the rule, click on any of the values in the rule maker and edit it by selecting one of the values in the palette. When the rule is complete, click on the "Make Rule" button to add it to the rules table. (However, if the "In State" and "Reading" items in the rule maker are the same as those for an existing rule, the "Make Rule" button becomes a "Replace" button. When you click it, the rule in the rule maker will replace the rule in the table.) Everytime you make or replace a rule, the rule maker is automatically updated to show the next consecutive rule, since it is at least fairly likely that that is the rule you want to work on next.

You can use the mouse to drag the Turing machine into a new position on its tape or to drag the tape to a new position under the machine. If you want to drag them both together, use the right mouse button or hold down the Control key as you click.

Using the Keyboard

You can use the keyboard to perform any editing task in the xTuringMachine applet. Here's how.

Pressing the tab key will move the hilite among the three major areas: the machine, the rule maker, and the rule table. (If there is no hilited item, pressing the tab key might create a hilite in the rule maker; if not, you have to use the mouse.) Within one these three major areas, the up, down, left, and right arrow keys can be used to move the hilite from one item to another. When the hilite is in the tape or in the rule table, the "home" and "end" keys can also be used. Play around to see how they work.

You can always type one of the values displayed in the palette, instead of clicking on it. Note that a blank can be entered either by pressing the space bar or by typing a #. The default symbol ("other" in the "Reading" column or "same" in the "Write" column) is entered by typing a *.

When working in the rule maker, hitting the return key is the same as clicking on the "Make Rule" (or "Replace") button.

The Sample Machines

The applet on this page is set up to load four sample Turing machines. Here are brief descriptions:

David Eck (eck@hws.edu), August 1997