CIT 596 Turing Machine simulator
Spring 2012, David Matuszek

I wrote a little Turing Machine simulator over the weekend. It's no real competition for JFLAP, but it does take input in a different form. JFLAP uses diagrams, but a TM can also be described textually. The transition function δ can be specified as a set of 5-tuples of the form:(current state, symbol read, symbol written, direction, next state), and reasonable defaults can be used for the other characteristics.

Here are the details:

• The simulator is available online:
  • turing-machine.py uses Python 2.7 and text input (no GUI)
  • turing-machine-with-wx.py uses Python 2.7 with wxPython for the dialog boxes.
• The simulator asks for two input files:
  1. A description of the TM as a set of 5-tuples, one per line, space-separated. A "blank" is represented by the character '#' For example, the 5-tuple ("S", "a", " ", "L", "foo") would be represented as
     S a # L foo
     meaning: In state S, if the TM reads an "a", it writes a blank, moves Left, and enters state foo.
     This representation has been chosen because it's easy to type and easy for the program to read. State names can be any length.
  2. The tape contents as a single line of a file.
• The simulator starts in a state named start, and is positioned on the first (leftmost) non-blank symbol on the tape.
• The simulator will halt if it enters a state named halt, accept, or reject (all lowercase). The first of these is intended for transducers, the second and third for recognizers, but they are all halting states.
• If the simulator has no legal transition, it will enter the reject state and halt.

I would be happy to have students rewrite the program in their favorite language--it would be a nice thing to contribute to the class. I may do some additional languages myself.