Index of /teaching/cs332/TM/simulator

[ICO]NameLast modifiedSizeDescription

[DIR]Parent Directory  -  
[TXT]components.cpp24-Jun-1999 10:43 3.6K 
[TXT]components.h25-Jun-1999 17:04 2.9K 
[   ]ikeno.description23-Jun-1999 10:29 747  
[   ]tape.contents23-Jun-1999 10:29 95  
[TXT]tm.cpp24-Jun-1999 10:43 4.1K 

Turing Machine Simulator The first two parts below explain how to represent a Turing Machine and its input as text files, and how to use a simulator that reads these files and displays successive configurations of the machine.

The third part describes a particular universal TM invented by Ikeno in 1958.

The directory in which this file (README) resides also has:


The text file describing a TM consists of three parts.

The first part is a list of symbols in the TM alphabet. The elements of the list are separated by whitespace. Each symbol may contain up to 10 non-whitespace characters, although single-character symbols will make the output look nicer.

An ellipsis (three dots with no spaces between) indicates the end of the list of symbols.

The second part is a list of states. Each state in the list has a name, specified in the same way as symbols, and a direction, specified as "right" or "left". (Actually, only the first letter, case-insensitive, matters.) The purpose of the "direction" component is explained in the next paragraph.

A TM as conceived here is an array of left- or right-pointing cellular automata. The right-pointing automata precede the left-pointing ones, and the two at the boundary are viewed as the TM head and the symbol it sees. This convention simplifies the model -- the head is now just one of the cells, and the distinction between state and symbol is gone. It is equivalent to the standard TM model provided that a standard machine's state determines the direction that the head moves. Any TM is easily modified (by adding states) to have this property.

Note: Do not confuse this interpretation of a TM with its C++ implementation. In order to facilitate modification, the implementation distinguishes states and symbols, and maintains the head as a separate component (namely, as an index into the array of symbols on the tape).

An ellipsis indicates the end of the list of states.

The third part is the list of transitions. Each is a string with four elements separated by whitespace. The format of a transition is:


Here is how to compile the simulator with the g++ compiler in Unix, assuming that you have copied all of the files. First type--

This creates an object file, components.o, for the classes that are used by the simulator. The simulator is compiled with-- This creates an executable file called tm.

Now suppose that a TM description is contained in a file called "m1.description" and its input in a file called "m1.input".

To begin the simulation, type--

Name the files whatever you like, but the description file must precede the input file on the command line.

The simulator will display the symbols of each cell from left to right, with a left-pointing head followed by (and right-pointing head preceded by) a space. For example, the configuration--

means that the head is in state s and scanning the 4, whereas the configuration-- means that the head is in state t and is scanning the 5.

Hit ENTER to see the next configuration. The simulation halts if there is no transition defined for the current state and symbol, or if you hit the end-of-file key (CTRL-C in Unix).


The Ikeno machine U is a 6-symbol, 11-state universal TM with quadratic-time simulation overhead. Its transition table is given below (and is encoded in the file ikeno.description).

           o    i    x    O    I    X   
          -----------------------------  
       f | xa | xb | xC | of | if | xc |
       C | xa | xb | xC | oC | iC | xc |
         |----+----+----+----+----+----|
       A | of | if | oe | oA | iA | xA |
       B | oC | iC | ie | oB | iB | xB |
         |----+----+----+----+----+----|
       c | Oc | Ic | xc | oC |    | XE |
       a | Oa | Ia | Xa | oC | Ib | XE |
         |----+----+----+----+----+----|
       b | Ob | Ib | Xb | Oa | ib | xD |
       d | Od | Id | xd | Od | Id | xD |
         |----+----+----+----+----+----|
       D |    | Id | xD | oD | iD | Xe |
       E |    |    | XE | OE | IE | Xe |
         |----+----+----+----+----+----|
       e | Oe | Ie | Xe | oA | oB |    |
          ----+----+----+----+----+----  
The entry in row [current-state] and column [symbol-scanned] is [symbol-to-write, next-state]. If no transition is defined, the machine halts.

An upper-case state indicates a right-looking head; lower-case means left-looking. The starting state is either f or C.

U's tape is divided into two parts: at the left is a description (details below) of the machine M that it is simulating, and at the right is M's tape.

The alphabet of M is {o,i}. (For any TM with a larger alphabet there exists one computing the same function with a binary alphabet, at the cost of extra states and a constant factor slowdown.)

Here is a typical configuration of U:

M's tape is the portion following the last x. The head f is looking left at the o. Each x- or X-separated segment preceding M's tape describes one of M's transitions. The current state is indicated by the rightmost segment having big letters, in this example XIIoi. The big letters following the X will be a sequence of k O's or I's indicating the location of the next state:

     Symbol scanned by M   In current state segment   Location of next state
     -------------------   ------------------------   -------------------------
            o                       k O's             k segments to the right
 
            i                       k O's             k-1 segments to the right

            o                       k I's             k segments to the left
             
            i                       k I's             k+1 segments to the left
In the above example, U changes the o that M is scanning to an x and enters state a (or state b if an i had been scanned), then continues moving left until scanning O or I, changing all small symbols to their big counterparts as it goes: Now U will find the new state (2 segments to the left) by alternating in states d and D (or c and C if the next segment is to the right), switching the case of symbols in each pass: The second segment is now marked as the new state of M. Its last symbol indicates the new symbol to write on M's tape, and its second-to-last symbol indicates the direction to move M's head (O = left). So U fetches the new symbol: and changes state to A (or B if I had been scanned), then moves right to the first small x: U then replaces the x with o and moves left to the first O or I to get the direction: Now U changes the O to o and enters state A (B if I had been scanned) and returns to M's head (at the first small symbol to the right), changing as it goes each big symbol to its small counterpart: Finally, U moves the head to the left and re-enters the start state:


Simulator by Drue Coles <dcoles@cs.bu.edu>