Search:

Research?

Teaching

Downloads

Classes

Quintuple Turing Machine Simulator

Projects.QTMS History

Hide minor edits - Show changes to output

May 02, 2011, at 12:55 PM by Scott - Moved attachments into PmWiki
Changed line 11 from:
QTMS runs on Microsoft Windows and requires version 2.0 of the .NET Framework.  Both a [[http://webspace.cs.odu.edu/~sainswor/projects/qtms/QtmsWindows-1.0.1.msi|Windows installer]] and [[http://webspace.cs.odu.edu/~sainswor/projects/qtms/QtmsWindows-1.0.1-src.zip|C# source]] are available for download.
to:
QTMS runs on Microsoft Windows and requires version 2.0 of the .NET Framework.  Both a [[Attach:QtmsWindows-1.0.1.msi|Windows installer]] and [[Attach:QtmsWindows-1.0.1-src.zip|C# source]] are available for download.  QTMS is also on [[http://qtms.sourceforge.net/|SourceForge.net]].
April 30, 2011, at 12:08 AM by scott - First complete version.
Changed line 54 from:
''
to:
Changed lines 58-59 from:
* 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.
to:
* 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.
Changed line 62 from:
'''Note''': The inner content of the State elements is ignored and can be used for comments.
to:
->'''Note''': The inner content of the State elements is ignored and can be used for comments.
Changed lines 69-72 from:
* 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.
to:
* 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.
Changed lines 83-86 from:
* 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.
to:
* 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.
Changed lines 91-92 from:
''Note'': The inner content of the Symbol elements is ignored and can be used for comments.
to:
->'''Note''': The inner content of the Symbol elements is ignored and can be used for comments.
Changed line 97 from:
(:table class=plain:)
to:
(:table class=plain width=80%:)
Changed line 102 from:
(:row:)
to:
(:row width=15%:)
Changed line 106 from:
(:row:)
to:
(:row width=50%:)
Changed lines 110-134 from:
(:tableend:)
to:
(:row width=50%:)
(:cell align=center:) Γ
(:cell:) ''Symbols''
(:cell:) The finite set of tape symbols, a superset of Σ.
(:row width=50%:)
(:cell align=center:) δ
(:cell:) ''TransitionFunction''
(:cell:) δ : 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.
(:row width=50%:)
(:cell align=center:) q'_0_'
(:cell:) The ''State'' with ''type'' = “initial”
(:cell:) The initial state.
(:row width=50%:)
(:cell align=center:) B
(:cell:) The ''State'' with ''type'' = “blank”
(:cell:) The blank symbol, B ∈ Γ
(:row width=50%:)
(:cell align=center:) F
(:cell:) The ''States'' with ''type'' = “final”
(:cell:) A subset of Q, the set of final states.
(:tableend:)

!! Building QTMS

QTMS comprises two basic Visual Studio 2008 projects. The ''TurningMachineSimulator'' project builds the simulator.  The ''WindowsSetup'' project produces the MSI setup file.
Added lines 72-110:

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

!! 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:

(:table class=plain:)
(:row:)
(:head width=5%:) Symbol
(:head:) XML
(:head:) Description
(:row:)
(:cell align=center:) Q
(:cell:) ''States''
(:cell:) Finite set of states
(:row:)
(:cell align=center:) Σ
(:cell:) ''Symbols'' with ''type'' = “input”
(:cell:) The finite set of input symbols that does not contain B
(:tableend:)
Changed lines 26-28 from:
%center% http://www.cs.odu.edu/~sainswor/projects/qtms/Palendrome1.png"Quintuple Turing Machine Simulator Main Window" | Quintuple Turing Machine Simulator Main Window%%

to:
%center% Attach:QTMS_Palendrome1.png"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.

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

'''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.
Changed lines 13-27 from:
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\.
to:
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:

%center% http://www.cs.odu.edu/~sainswor/projects/qtms/Palendrome1.png"Quintuple Turing Machine Simulator Main Window" | Quintuple Turing Machine Simulator Main Window%%

Changed line 11 from:
QTMS runs on Microsoft Windows and requires version 2.0 of the .NET Framework.  Both a [[/~sainswor/projects/qtms/QtmsWindows-1.0.1.msi|Windows installer]] and [[~sainswor/projects/qtms/QtmsWindows-1.0.1-src.zip|C# source]] are available for download.  QTMS is also available on [[http://qtms.sourceforge.net/|Sourceforge]].
to:
QTMS runs on Microsoft Windows and requires version 2.0 of the .NET Framework.  Both a [[http://webspace.cs.odu.edu/~sainswor/projects/qtms/QtmsWindows-1.0.1.msi|Windows installer]] and [[http://webspace.cs.odu.edu/~sainswor/projects/qtms/QtmsWindows-1.0.1-src.zip|C# source]] are available for download.
Added lines 1-14:
(:title 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 [[http://www.cs.odu.edu/faculty_show.shtml?p=11|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 [[http://en.wikipedia.org/wiki/Busy_beaver_function|2-state Busy Beaver]] (Wikipedia).

!! Downloads and Installation

QTMS runs on Microsoft Windows and requires version 2.0 of the .NET Framework.  Both a [[/~sainswor/projects/qtms/QtmsWindows-1.0.1.msi|Windows installer]] and [[~sainswor/projects/qtms/QtmsWindows-1.0.1-src.zip|C# source]] are available for download.  QTMS is also available on [[http://qtms.sourceforge.net/|Sourceforge]].

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

History Print Recent Changes Search

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