Quintuple Turing Machine Simulator


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

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
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.


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:


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.
Note: The inner content of the State elements is ignored and can be used for comments.

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).
Note: The inner content of the Symbol elements is ignored and can be used for comments.

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”).
Note: The inner content of the Tuple elements is ignored and can be used for comments.


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.

Note: The inner content of the Symbol elements is ignored and can be used for comments.

Notation and XML Elements

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

Symbol XML Description
Q States Finite set of states
Σ Symbols with type = “input” The finite set of input symbols that does not contain B
Γ Symbols The finite set of tape symbols, a superset of Σ.
δ TransitionFunction δ : Q × Γ → Q × Γ × {l, r}, where l and r are special symbols that specify the direction of movement of the head on the tape. The map δ, called the transition function, is at the heart of the Turning Machine.
q0 The State with type = “initial” The initial state.
B The State with type = “blank” The blank symbol, B ∈ Γ
F The States with type = “final” A subset of Q, the set of final states.

Building QTMS

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

History Print Recent Changes Search

Page last modified on May 02, 2011, at 12:55 PM