From Scott G. Ainsworth

Projects: 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,

Quintuple Turing Machine Simulator Main Window
Quintuple Turing Machine Simulator Main Window

Execution and Controls

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:

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:

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:

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

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.

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.

Retrieved from https://www.cs.odu.edu/~sainswor/Projects/QTMS
Page last modified on May 02, 2011, at 12:55 PM