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).
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.
When QTMS was installed, Start Menu entries were created under All Programs/Ainsworth QTMS. Start QTMS by clicking the Quintuple Turing Machine Simulator entry.
To load a Turing Machine definition, use the File/Open menu. For example, to load Dr. Olariu's palendrome identifier,
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.)
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 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.
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 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 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 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.
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. |
q_{0} | 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. |
QTMS comprises two basic Visual Studio 2008 projects. The TurningMachineSimulator project builds the simulator. The WindowsSetup project produces the MSI setup file.