Quintuple Turing Machine Simulator

Introduction

The Quintuple Turing Machine Simulator (QTMS) is a simple, education-oriented Turing Machine simulator based on the quintuples (5-tuples) model. It is written primarily for Computer Science students learning Turing machines for the first time. It presents a graphic view of the tape including color coding symbols and states. Execution controls include single step, back step, and automatic run (timed stepping). Turing Machines are defined used XML. Because it uses 5-tuples (instead of the now more common 4-tuples) older Turing Machines definitions, such as Rado's original Busy Beaver can be used directly.

I originally wrote this to ensure my understanding of the Turing Machine computational model used in Prof. Olariu's Introduction to Algorithms and Data Structures class (CS 600). It includes two samples: the palendrome identifier from Prof. Olariu's textbook and a 2-state Busy Beaver (Wikipedia).

Downloads and Installation

QTMS runs on Microsoft Windows and requires version 2.0 of the .NET Framework. Both a Windows installer and C# source are available for download. QTMS is also on SourceForge.net.

Install QTMS by running the MSI installer. If all the defaults are accepted, QTMS will be installed in C:\Program Files\Ainsworth\Quintuple Turing Machine Simulator.

Using the Turning Machine Simulator

When QTMS was installed, Start Menu entries were created under All Programs/Ainsworth QTMS. Start QTMS by clicking the Quintuple Turing Machine Simulator entry.

Loading a Turning Machine definition

To load a Turing Machine definition, use the File/Open menu. For example, to load Dr. Olariu's palendrome identifier,

• Start QTMS.
• Select File/Open, navigate to C:\Program Files\Ainsworth\Quintuple Turing Machine Simulator\Samples, and open Palendrome.qtms. You should see the following window:

Quintuple Turing Machine Simulator Main Window

Execution and Controls

• The Run button starts execution.
• The Pause button suspends execution.
• The Run Speed slider changes the execution speed.
• The Step button executes the next step and pauses.
• The BackStep button reverses the effect of the previous step. A Turing Machine can be back stepped all the way to its initial state.
• The Reset button returns the Turing Machine to its initial state. In effect, the definition is reloaded.

Termination

When execution terminates, the background color of the current symbol is changed to green if the input string is a palendrome and red if it is not. (For those who are red-green color blind, these colors can be changed in the definition file.)

On-the-Fly Changes

Although there is not a nice graphical interface for editing Turing Machine definitions, when QTMS is paused symbols can be changed. To change a symbol, right-click on a tape cell and select a different symbol from the pop-up list.

QTMS Definition Files

QTMS definitions are written in XML. There are five sections:

Metadata

The Metadata element contains the title and author. These are simply documentation and have no effect on the Turing Machine's operation.

States (Q)

The States element is the collection of the Turing Machine's valid states. Each state must have a name; all other attributes are optional. The attributes are:

• The name attribute identifies the state. It must be unique.
• When “true”, isInitial identifies the Turing Machine's initial state. There can be only one initial state.
• When “true”, isFinal identifies the state as a final state. Final states cause the turing Machine to stop executing. There can be multiple final states.
• The color attribute allows the state's background color to be changed. This is primarily intended to identify accepting and rejecting final states.

Symbols (Γ)

The Symbols element is the collection of the Turing Machine's valid symbols. Each symbol must have a value; all other attributes are optional. The attributes are:

• The value attribute is the unicode character that is displayed on the Turing Machine's tape. It also server as the symbol's name and must be unique.
• The type attribute specifies the symbol's type. The “blank” symbol type represents a blank tape position. There can be only one “blank” symbol. A symbol of type “input” is allowed as an input on the Turing Machine's tape (note this is not currently enforced by the simulator code).

Transition Function

The TransitionFunction element a the collection of Tuple elements that define the Turing Machine's transition function. Each tuple must have all attributes. The attributes are:

• The state attribute is the state the tuple must match.
• The scan attribute is the symbol the tuple must match.
• The newState attribute is the state the Turing Machine will enter upon completion of the current step.
• The write attribute is the symbol that will be written to the tape during the current step. Note: this Turing Machine simulator does not have a write/don't write attribute. If the tape symbol should not be changed, just write the same symbol that was matched.
• The move attribute indicates whether the tape should be moved “left”, “right”, or not moved (“none”).

Input

The Input element is the ordered list of symbols used to initialize the Turing Machine's tape. Each Symbol element requires exactly one attribute, value, which must match the value of one of the symbols listed Symbols collection.

Notation and XML Elements

The XML Elements and notation in Prof. Olariu's book correspond as follows:

Building QTMS

QTMS comprises two basic Visual Studio 2008 projects. The TurningMachineSimulator project builds the simulator. The WindowsSetup project produces the MSI setup file.