Introduction
This article describes the implementation and testing of a simulator of a universal Turing machine. The code is a conversion into unmanaged C++ under Visual Studio 2010 of an old Borland C++ version that I implemented when I was teaching Automata Theory at Washington State University, Department of Electrical Engineering and Computer Science, from January 2000 to December 2002..
NOTE: This article is from sections of Chapter 13 "Applications in Automata Theory, Part III" of my unpublished textbook "Appplied Algorithms and Data Structures."
Hilbert, David
(23 Jan. 1862 - 14 Feb. 1943) German mathematician who in 1900 enunciated a list of 23 research problems at the International Mathematical Congress in Paris. In his address, "The Problems of Mathematics," he surveyed nearly all the mathematics of his day and endeavoured to set forth the problems he thought would be significant for mathematicians in the 20th century. Many of the problems have since been solved, and each solution was a noted event. (The New Encyclopaedia Britannica, 1991, Vol 5, pp. 922-923.)
Turing, Alan Mathison
(23 Jun. 1912 - 7 Jun. 1954) British mathematician who solved Hilbert’s Entscheidungsproblem. During WWII, he was instrumental in cracking the German Enigma cipher. (Photo credit: Barendregt, H.P. The Lambda Calculus, Its Syntax and Semantics. Amsterdam: North-Holland, 1981.)
Turing Machines
Turing defined a class of computing machines, and used them in an influential paper in which he showed that Hilbert’s Entscheidungsproblem (Decision Problem or Halting Problem) was unsolvable. (Turing, A.M. "On Computable Numbers, With an Application to the Entscheidungsproblem." Proceedings of the London Mathematical Society, Vol 42, 1937, pp. 230-265; and "On Computable Numbers, With an Application to the Entscheidungsproblem. A Correction" Proceedings of the London Mathematical Society, Vol 43, 1937, pp. 544-546.)
NOTE: Most of the theoretical material in this chapter is from Hopcroft, J.E., and J.D. Ullman. Introduction to Automata Theory, Languages, and Computation. Reading, Massachusetts: Addison-Wesley, 1979, Chapter 7.
The original Turing machine (TM) described by Alan Turing consists of an infinite tape, a finite control, and a read/write (RW) head positioned over the tape. For simulation purposes, a (basic) TM, illustrated below, consists of a semi-infinite tape (to store symbols), and a finite control with a RW head that can move to the right or to the left. A string of symbols to be processed is left-justified on the tape (after the special symbol ‘#’ which marks the beginning of the tape) and is followed by an indeterminate string of "blank" symbols.
Descriptions of Turing Machines
In the labels for state transitions, a denotes the symbol on the input tape at the current position of the RW head, b denotes the symbol that will replace a on the tape, while the arrows indicate the direction in which the RW head must be moved one position after the replacement has taken place.
For simulation purposes a description of a TM can be provided in a text file. For the example state diagram above, we could have the following description.
Observe that in the description, the input alphabet includes the blank-space character, which is written between "01" and "XY" so that it can be recognized.
After the lines containing the number of states and the TM’s alphabet, a series of lines describe the allowable transitions from each state. Each line begins with the name of a state, and then it contains specifications of transitions of the form
InputSymbol ( NextState ReplacementSymbol DirectionOfMotion ) .
Observe also that in the actual specifications of transitions, commas are optional separators.
Comments in TM Descriptions
The simulator, to be discussed shortly, allows comments in the descriptions of TMs. Any line beginning with a ";" is treated as a comment. In addition, when specifying state transitions, comments can be added by enclosing them between the "{" and "}" characters. In addition, blank lines are ignored and just echoed to the output.
As an example, I illustrate the design of a basic TM to accept the language consisting of even-length palindromes over the alphabet { 0, 1 }, that is the set defined as
The Simulator of a Universal Turing Machine
The simulator, written in unmanaged C++ under Visual Studio 2010, will be described in a top-down fashion, that is, from high-level functions to low-level auxiliary functions.
Include Files, Structures and Global Variables
Before going through the simulator’s functionality, it is imperative to provide the include files, the data structures and the global variables to be used. They are defined as follows. (Comments should make them self-explanatory.)
#include "stdafx.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <malloc.h>
#include <dos.h>
#include <time.h>
#define nFile 30 // file-name characters
#define nLine 350 // input-line characters
#define nDigits 2 // maximum digits in a decimal number
#define nBdigits 7 // maximum binary digits for decimal numbers
#define nStates 100 // maximum number of states
#define nAlpha 20 // maximum number of alphabet symbols
typedef struct {
int q;
char s,
d;
} TMstruct, *TMstrPtr;
TMstrPtr TMrule[ nStates ][ nAlpha ];
char binary[ nStates ][ nBdigits + 1 ];
time_t tStart, tEnd;
typedef enum
{ number, lparen, rparen, comma,
dash, _q, _b, _l, _r, _char, eol } SymbolType;
int pos,
len,
numVal,
mStates,
mSymbols,
state,
nSimSteps;
FILE *fp;
SymbolType symbol;
char fileName[ nFile ],
line[ nLine ],
alphabet[ nLine ],
aChar;
char *errorMsg[ 6 ]
= { "'q'", "number", "'b' or non-special character",
"'('", "'l', 'r' or '-'", "')'" };
Main Function
int _tmain(int argc, _TCHAR* argv[])
{
printf( "input file? " );
gets( fileName );
if ( ( fp = fopen( fileName, "r" ) ) == NULL )
{
printf( "\nunable to open file '%s'\n", fileName );
}
else
{
printf( "%s\n", fileName );
printf( "number of simulation steps [0 = indefinite]? " );
scanf( "%d", &nSimSteps );
printf( "%d\n", nSimSteps );
InputTM();
ReportTM();
SimulateTM();
DescribeTM();
FreeMemory();
}
return 0;
}
The main function of Turing.cpp requires two inputs: the name of the input file and the number of simulation steps. (The number of simulation steps is necessary because some TMs can run indefinitely. So this number, when not 0, can be used to stop the simulation.) Turing.exe is defined to be a console application. If run interactively, the two inputs must be typed in. However, it is possible (and convenient) to use I/O redirection to provide the inputs. Assuming that we want to simulate a TM with the name sampleTM, we can create two text files: sampleTM.txt and sampleTM_in.txt. File sampleTM.txt should contain the following two lines:
sampleTM_in.txt
0
while fille sampleTM_in.txt should contain the description of the TM. Then the simulation would be started with the following call from the command-line prompt (observe the redirection character "<"):
Turing.exe <sampleTM.txt
After obtaining (and echoing) valid inputs, the main function reads the description of the TM (InputTM), reports the description for verification (ReportTM), initiates the simulation (SimulateTM), generates a character string to describe the TM (DescribeTM) so that the TM can be simulated by another TM [more on this later], and frees all the dynamic memory used (FreeMemory).
InputTM
Essentially, function InputTM is an ordinary parser of the description of the TM. It gets the number of states and the alphabet of the TM. After initializing the array that will contain the transition rules of the TM, the function parses each line (obtained via function GetLine) containing the transitions for each state of the TM by calling the auxiliary functions NextSymbol and TM_P for each line..
void InputTM()
{
int i, j;
GetLine( line );
mStates = atoi( line );
mSymbols = GetLine( alphabet );
for ( i = 0; i < nStates; ++i )
{
for ( j = 0; j < nAlpha; ++j )
{
TMrule[ i ][ j ] = NULL;
}
}
printf( "\n" );
while ( ( len = GetLine( line ) ) != 0 )
{
printf( "%s\n", line );
if ( line[ 0 ] == '*' )
{
break;
}
pos = 0;
if ( pos < len )
{
NextSymbol();
TM_P();
}
}
}
GetLine
Function GetLine is used both to skip comments and to file a line array to be parsed for transition rules.
int GetLine( char line[] )
{
int commentLine = 1;
while ( commentLine && ( fgets( line, nLine, fp ) != NULL) )
{
len = strlen( line ) - 1;
line[ len ] = '\0';
if ( BlankLine( line, len ) )
{
printf( "" );
continue;
}
if ( line[ 0 ] != ';' )
{
commentLine = 0;
}
else printf( "%s\n", line );
}
return len;
}
NextSymbol
This function takes care of processing the contents of an input line. It skips blanks and comments. It converts numeric strings into numbers, and processes special characters in transition rules. Functions SkipBlanks and SkipComment are self-explanatory and will not be described here. (They are defined in the complete source code.) The argument to NextSymbol controls whether or not the function parses numeric strings. By default, the function does parse them.
void NextSymbol( int scanForNumOK = 1 )
{
char ch;
int i;
SkipBlanks();
SkipComment();
SkipBlanks();
if ( pos < len )
{
ch = line[ pos++ ];
if ( scanForNumOK && isdigit( (int)ch ) )
{
numVal = 0; i = 1;
do {
if ( i < nDigits )
{
numVal = numVal * 10 + ch - '0';
}
ch = line[ pos++ ];
} while ( isdigit( (int)ch ) && pos < len );
symbol = number;
}
else
{
switch ( tolower( ch ) )
{
case '(': symbol = lparen; break;
case ')': symbol = rparen; break;
case ',': symbol = comma; break;
case '-': symbol = dash; break;
case 'q': symbol = _q; break;
case 'b': symbol = _b; ch = ' '; break;
case 'l': symbol = _l; break;
case 'r': symbol = _r; break;
default: symbol = _char; break;
}
aChar = ch;
}
}
else
{
symbol = eol;
}
}
TM_P
Function TM_P acquires the starting state (via function TM_S) from a row in the TM description and initiates the parsing of the transition rules for that state by calling function TM_T.
void TM_P()
{
TM_S( &state );
TM_T();
}
TM_S
Function TM_S parses the start state for a row in the TM description. The expected format is qN, where N denotes a number. If the parsing is successful, then function NextSymbol is called with the indication of not to parse a number; otherwise, function Error is called to signal an incorrect syntax.
void TM_S( int *var )
{
if ( symbol == _q )
{
NextSymbol();
if ( symbol == number )
{
*var = numVal;
NextSymbol( 0 );
}
else Error( 1 );
}
else Error( 0 );
}
TM_T
Function TM_T recursively parses the transition rules for the start state obtained by function TM_S. From the examples given before, the transition rules have the format S(NS RS D), where S stands for the current symbol on the RW head, NS stands for the next state, RS stands for the symbol to replace S, and D stands for the direction in which to move the RW head (L for left, R for write, or – for no movement).
void TM_T()
{
char inC, repC, dir;
int nxtQ;
TMstrPtr p;
if ( symbol != eol )
{
if ( symbol == _b || symbol == _char )
{
inC = aChar;
NextSymbol();
if ( symbol == lparen )
{
NextSymbol();
TM_S( &nxtQ );
SkipComma();
if ( symbol == _b || symbol == _char )
{
repC = aChar;
NextSymbol();
SkipComma();
if ( symbol == _l || symbol == _r || symbol == dash )
{
dir = aChar;
p = (TMstrPtr)malloc( sizeof( TMstruct ) );
p->q = nxtQ;
p->s = repC;
p->d = dir;
TMrule[ state ][ CharIndex( inC ) ] = p;
NextSymbol();
if ( symbol == rparen )
{
NextSymbol( 0 );
TM_T();
}
else Error( 5 );
}
else Error( 4 );
}
else Error( 2 );
}
else Error( 3 );
}
else Error( 2 );
}
}
ReportTM
Once the TM description has been processed, function ReportTM is called by the main function to print in matrix form the description in order for the user to verify that the description was processed correctly.
void ReportTM()
{
int i, j;
printf( "\nTuring machine: %s\n", fileName );
printf( "%d states; \nalphabet: '%s', %d symbols\n",
mStates, alphabet, mSymbols );
printf( "\ntransition/action matrix:\n\n " );
for ( j = 0; j < mSymbols; ++j )
{
printf( " %c ", EquivalentChar( alphabet[ j ] ) );
}
printf( "\n\n" );
for ( i = 0; i < mStates; ++i )
{
printf( "q%2d ", i );
for ( j = 0; j < mSymbols; ++j )
{
PrintTMstring( TMrule[ i ][ j ] );
}
printf( "\n" );
}
}
Function EquivalentChar simply converts spaces to character ‘b’. Function PrintTMstring prints a transition rule, or "/" if there is no transition. These functions will not be shown here. (Again, the complete source code is provided.)
SimulateTM
At the heart of the simulator is function SimulateTM. This function literally executes the program encoded by the TM description by processing one by one the inputs following the ‘*’ character after the description. Each input is loaded onto the tape and the TM rules are applied to the characters on the tape. Each time a rule is applied, function PrintConfiguration is called to display the contents of the tape.
void SimulateTM()
{
char tape[ nLine ];
int h, q, n, i, t;
TMstrPtr p;
Dword steps;
time( &tStart );
printf( "\nSimulating turing machine\n" );
while ( ( n = GetLine( tape ) ) > 0 )
{
if ( tape[ 0 ] == '!' )
{
break;
}
printf( "\n" );
for ( i = n; i < nLine - 1; ++i )
{
tape[ i ] = ' ';
}
tape[ nLine - 1 ] = '\0';
t = h = q = 0;
steps = 0L;
while ( q >= 0 )
{
PrintConfiguration( q, tape, h );
p = TMrule[ q ][ CharIndex( tape[ h ] ) ];
if ( p != NULL )
{
++steps;
q = p->q;
tape[ h ] = p->s;
if ( p->d == '-' )
{
break;
}
h += ( tolower( p->d ) == 'r' ) ? 1 : -1;
if ( h < 0 || h == nLine )
{
printf( "illegal head position: %d\n", h );
q = -1;
}
if ( nSimSteps > 0 )
{
++t;
if ( t > nSimSteps )
{
break;
}
}
}
else
{
break;
}
}
PrintConfiguration( q, tape, h );
printf( "\nInput %saccepted\n",
( q == mStates -1 ) ? "" : "not " );
printf( "%lu simulation steps\n", steps );
}
fclose( fp );
time( &tEnd );
ReportElapsedTime();
}
PrintConfiguration
This function prints the contents of the TM after each simulation step. The encoding |qN>, where N stands for a state number, indicates the position of the RW head. The symbol to be processed next follows the ‘>’ character.
void PrintConfiguration( int q, char t[], int h )
{
int i;
char c;
for ( i = 0; i < h; ++i )
{
printf( "%c", t[ i ] );
}
printf( "|q%d>", q );
i = h;
while ( i < len )
{
printf( "%c", t[ i++ ] );
}
while( (c = t[ i++ ]) != ' ' )
{
printf( "%c", c );
}
printf( "\n" );
}
DescribeTM
After the TM has been simulated, function DescribeTM is called to generate and print an encoded string describing the TM so that it can be simulated by a universal Turing machine. At this point it is pointless to go over the workings of this function and of its auxiliary functions. I will come back to this function once the universal Turing machine has been dealt with later in the article. Now I turn to examples of simulations of TMs.
Examples of Turing Machine Simulations
In order to illustrate the use of the TM simulator, I will present some interesting TMs. The text files for all the TMs are also provided.
A TM that accepts the non-regular language 0^n1^n
One of the classic examples of the superiority of TMs over finite automata is a TM that accepts a non-regular language, for it is well known that finite automata cannot process non-regular languages. This example shows the processing of the regular language 0^n1^n, where ‘^’ denotes exponentiation in the logical sense, that is, multiple concatenation. As explained before, two files are required to perform the simulation. The "driver" file would be, say, 0n1n.txt with contents:
0n1nTM_in.txt
0
The file 0n1nTM_in.txt contains the description of the TM and the inputs to be processed:
;
; 0n1nTM_in.txt
;
; Turing Machine that accepts the non-regular language
; 0^n1^n for n >= 1.
;
5
01 XY
q0 0(q1 X R) Y(q3 Y R)
q1 0(q1 0 R) 1(q2 Y L) Y(q1 Y R)
q2 0(q2 0 L) X(q0 X R) Y(q2 Y L)
q3 Y(q3 Y R) B(q4 B R)
q4
*
00001111
00100
!
The results of the simulation for the two given inputs are as follows:
;
; 0n1nTM_in.txt
;
; Turing Machine that accepts the non-regular language
; 0^n1^n for n >= 1.
;
q0 0(q1 X R) Y(q3 Y R)
q1 0(q1 0 R) 1(q2 Y L) Y(q1 Y R)
q2 0(q2 0 L) X(q0 X R) Y(q2 Y L)
q3 Y(q3 Y R) B(q4 B R)
q4
*
Turing machine: 0n1nTM_in.txt
5 states;
alphabet: '01 XY', 5 symbols
transition/action matrix:
0 1 b X Y
q 0 q 1, X,R / / / q 3, Y,R
q 1 q 1, 0,R q 2, Y,L / / q 1, Y,R
q 2 q 2, 0,L / / q 0, X,R q 2, Y,L
q 3 / / q 4, b,R / q 3, Y,R
q 4 / / / / /
Simulating turing machine
|q0>00001111
X|q1>0001111
X0|q1>001111
X00|q1>01111
X000|q1>1111
X00|q2>0Y111
X0|q2>00Y111
X|q2>000Y111
|q2>X000Y111
X|q0>000Y111
XX|q1>00Y111
XX0|q1>0Y111
XX00|q1>Y111
XX00Y|q1>111
XX00|q2>YY11
XX0|q2>0YY11
XX|q2>00YY11
X|q2>X00YY11
XX|q0>00YY11
XXX|q1>0YY11
XXX0|q1>YY11
XXX0Y|q1>Y11
XXX0YY|q1>11
XXX0Y|q2>YY1
XXX0|q2>YYY1
XXX|q2>0YYY1
XX|q2>X0YYY1
XXX|q0>0YYY1
XXXX|q1>YYY1
XXXXY|q1>YY1
XXXXYY|q1>Y1
XXXXYYY|q1>1
XXXXYY|q2>YY
XXXXY|q2>YYY
XXXX|q2>YYYY
XXX|q2>XYYYY
XXXX|q0>YYYY
XXXXY|q3>YYY
XXXXYY|q3>YY
XXXXYYY|q3>Y
XXXXYYYY|q3>
XXXXYYYY |q4>
XXXXYYYY |q4>
Input accepted
41 simulation steps
|q0>00100
X|q1>0100
X0|q1>100
X|q2>0Y00
|q2>X0Y00
X|q0>0Y00
XX|q1>Y00
XXY|q1>00
XXY0|q1>0
XXY00|q1>
XXY00|q1>
Input not accepted
9 simulation steps
Elapsed time: 0 seconds
TM description for LCCP UTM:
y0000x0000001X1x000Y011Y1x001000101x0011010Y0x001Y001Y1x010001000x010X000X1x010Y010Y0x011 100 1x011Y011Y1y0
Again, at the end of the simulation, there is an encoded string describing the TM for its simulation by a universal Turing machine (named "LCCP UTM" for historical reasons as will be explained later). From the simulation results, the first input is a string in the language, while the second is not. The reader may have noticed that there is no "echoing" of the simulator parameters (name of input file and number of simulation steps) in the output file. The reason is that the output file was generated by the original simulator that I wrote in 2002. For the rest of the examples, I will not show the "driver" file, nor the TM description file, for the simulator shows the TM description, and the first configuration in each simulation shows the input to be processed.
A TM that verifies whether a string of brackets is balanced
input file? BalancedParenthesesTM_in.txt
number of simulation steps [0 = indefinite]? 0
;
; BalancedParenthesesTM_in.txt
;
; Turing Machine to check whether or not a string containing
; left and right parentheses is well-formed, that is,whether
; they can be paired of from inside to outside so that each
; left parenthesis has a right-hand mate.
;
; After Minsky, M. "Computation: Finite and Infinite Machines"
; Prentice-Hall, 1967, pp. 121-122.
;
; A description based on Minsky's is given in Feynman, R.
; "Feynman's Lectures on Computation" Westview, 1996, pp. 71-73.
;
; Due to the way transitions are described (inside parentheses)
; for the simulator, the original problem is modified to use
; square brackets '[' and ']' instead of parentheses.
;
; Input format: A ... <string of square brackets> ... A
;
; NOTE: Even though the processing of all the input cases will
; yield "Input accepted" the contents of the tape will
; indicate with a '1' that the string is well-formed
; and with a '0' that it is not.
;
; Also note that both Minsky and Feynman implicitly assume the
; existence of state q0 below.
q0 A(q1 A R)
q1 A(q3 A L) x(q1 x R) [(q1 [ R) ](q2 x L)
q2 A(q4 0 -) x(q2 x L) [(q1 x R) ](q2 ] L)
q3 A(q4 1 -) x(q3 x L) [(q4 0 -)
q4
*
Turing machine: BalancedParenthesesTM_in.txt
5 states;
alphabet: 'A[]x01', 6 symbols
transition/action matrix:
A [ ] x 0 1
q 0 q 1, A,R / / / / /
q 1 q 3, A,L q 1, [,R q 2, x,L q 1, x,R / /
q 2 q 4, 0,- q 1, x,R q 2, ],L q 2, x,L / /
q 3 q 4, 1,- q 4, 0,- / q 3, x,L / /
q 4 / / / / / /
Simulating turing machine
|q0>AA
A|q1>A
|q3>AA
|q4>1A
Input accepted
3 simulation steps
|q0>A[[[[][]][]]]A
A|q1>[[[[][]][]]]A
A[|q1>[[[][]][]]]A
A[[|q1>[[][]][]]]A
A[[[|q1>[][]][]]]A
A[[[[|q1>][]][]]]A
A[[[|q2>[x[]][]]]A
A[[[x|q1>x[]][]]]A
A[[[xx|q1>[]][]]]A
A[[[xx[|q1>]][]]]A
A[[[xx|q2>[x][]]]A
A[[[xxx|q1>x][]]]A
A[[[xxxx|q1>][]]]A
A[[[xxx|q2>xx[]]]A
A[[[xx|q2>xxx[]]]A
A[[[x|q2>xxxx[]]]A
A[[[|q2>xxxxx[]]]A
A[[|q2>[xxxxx[]]]A
A[[x|q1>xxxxx[]]]A
A[[xx|q1>xxxx[]]]A
A[[xxx|q1>xxx[]]]A
A[[xxxx|q1>xx[]]]A
A[[xxxxx|q1>x[]]]A
A[[xxxxxx|q1>[]]]A
A[[xxxxxx[|q1>]]]A
A[[xxxxxx|q2>[x]]A
A[[xxxxxxx|q1>x]]A
A[[xxxxxxxx|q1>]]A
A[[xxxxxxx|q2>xx]A
A[[xxxxxx|q2>xxx]A
A[[xxxxx|q2>xxxx]A
A[[xxxx|q2>xxxxx]A
A[[xxx|q2>xxxxxx]A
A[[xx|q2>xxxxxxx]A
A[[x|q2>xxxxxxxx]A
A[[|q2>xxxxxxxxx]A
A[|q2>[xxxxxxxxx]A
A[x|q1>xxxxxxxxx]A
A[xx|q1>xxxxxxxx]A
A[xxx|q1>xxxxxxx]A
A[xxxx|q1>xxxxxx]A
A[xxxxx|q1>xxxxx]A
A[xxxxxx|q1>xxxx]A
A[xxxxxxx|q1>xxx]A
A[xxxxxxxx|q1>xx]A
A[xxxxxxxxx|q1>x]A
A[xxxxxxxxxx|q1>]A
A[xxxxxxxxx|q2>xxA
A[xxxxxxxx|q2>xxxA
A[xxxxxxx|q2>xxxxA
A[xxxxxx|q2>xxxxxA
A[xxxxx|q2>xxxxxxA
A[xxxx|q2>xxxxxxxA
A[xxx|q2>xxxxxxxxA
A[xx|q2>xxxxxxxxxA
A[x|q2>xxxxxxxxxxA
A[|q2>xxxxxxxxxxxA
A|q2>[xxxxxxxxxxxA
Ax|q1>xxxxxxxxxxxA
Axx|q1>xxxxxxxxxxA
Axxx|q1>xxxxxxxxxA
Axxxx|q1>xxxxxxxxA
Axxxxx|q1>xxxxxxxA
Axxxxxx|q1>xxxxxxA
Axxxxxxx|q1>xxxxxA
Axxxxxxxx|q1>xxxxA
Axxxxxxxxx|q1>xxxA
Axxxxxxxxxx|q1>xxA
Axxxxxxxxxxx|q1>xA
Axxxxxxxxxxxx|q1>A
Axxxxxxxxxxx|q3>xA
Axxxxxxxxxx|q3>xxA
Axxxxxxxxx|q3>xxxA
Axxxxxxxx|q3>xxxxA
Axxxxxxx|q3>xxxxxA
Axxxxxx|q3>xxxxxxA
Axxxxx|q3>xxxxxxxA
Axxxx|q3>xxxxxxxxA
Axxx|q3>xxxxxxxxxA
Axx|q3>xxxxxxxxxxA
Ax|q3>xxxxxxxxxxxA
A|q3>xxxxxxxxxxxxA
|q3>AxxxxxxxxxxxxA
|q4>1xxxxxxxxxxxxA
Input accepted
83 simulation steps
Elapsed time: 0 seconds
TM description for LCCP UTM:
y0000x000A001A1x001A011A0x001[001[1x001]010x0x001x001x1x010A10001x010[001x1x010]010]0x010x010x0x011A10011x011[10001x011x011x0y0
A TM to generate binary numbers
This is an example of the need for the number of simulation steps as the second input to the simulator. Without this parameter, this TM would run indefinitely. The binary numbers generated are shown in bold.
input file? BinNumGenTM_in.txt
number of simulation steps [0 = indefinite]? 60
;
; BinNumGenTM_in.txt
;
; Turing Machine to Generate Binary Numbers
;
q0 0(q0 0 R) 1(q1 1 L)
q1 0(q0 1 R) 1(q1 0 L)
*
Turing machine: BinNumGenTM_in.txt
2 states;
alphabet: '01', 2 symbols
transition/action matrix:
0 1
q 0 q 0, 0,R q 1, 1,L
q 1 q 0, 1,R q 1, 0,L
Simulating turing machine
|q0>0000000010000
0|q0>000000010000
00|q0>00000010000
000|q0>0000010000
0000|q0>000010000
00000|q0>00010000
000000|q0>0010000
0000000|q0>010000
00000000|q0>10000
0000000|q1>010000
00000001|q0>10000
0000000|q1>110000
000000|q1>0010000
0000001|q0>010000
00000010|q0>10000
0000001|q1>010000
00000011|q0>10000
0000001|q1>110000
000000|q1>1010000
00000|q1>00010000
000001|q0>0010000
0000010|q0>010000
00000100|q0>10000
0000010|q1>010000
00000101|q0>10000
0000010|q1>110000
000001|q1>0010000
0000011|q0>010000
00000110|q0>10000
0000011|q1>010000
00000111|q0>10000
0000011|q1>110000
000001|q1>1010000
00000|q1>10010000
0000|q1>000010000
00001|q0>00010000
000010|q0>0010000
0000100|q0>010000
00001000|q0>10000
0000100|q1>010000
00001001|q0>10000
0000100|q1>110000
000010|q1>0010000
0000101|q0>010000
00001010|q0>10000
0000101|q1>010000
00001011|q0>10000
0000101|q1>110000
000010|q1>1010000
00001|q1>00010000
000011|q0>0010000
0000110|q0>010000
00001100|q0>10000
0000110|q1>010000
00001101|q0>10000
0000110|q1>110000
000011|q1>0010000
0000111|q0>010000
00001110|q0>10000
0000111|q1>010000
00001111|q0>10000
0000111|q1>110000
Input accepted
61 simulation steps
Elapsed time: 0 seconds
TM description for LCCP UTM:
y00x00001x01110x10011x11100y0
A TM to recognize palindromes
This example illustrates the use of comments in the description of TMs.
input file? GpalindromeTM_in.txt
number of simulation steps [0 = indefinite]? 0
; GpalindromeTM_in.txt
;
; Design a TM to recognize "generalized" palindromes, that is, strings that read
; the same forward and backward if intervening blank spaces are ignored.
;
; The test strings are enclosed by the '.' character at the beginning and the end.
;
{ find first non-'.' on the right } q0 .(q1 . R)
{ dispatch to separate states on 0/1 } q1 b(q1 . R) 0(q2 . R) 1(q5 . R) .(q7 . R)
{ seen 0, find '.' on the right } q2 b(q2 b R) 0(q2 0 R) 1(q2 1 R) .(q3 . L)
{ if matching 0, erase and repeat } q3 b(q3 . L) 0(q4 . L) .(q7 . R)
{ find '.' on the left } q4 b(q4 b L) 0(q4 0 L) 1(q4 1 L) .(q1 . R)
{ seen 1, find '.' on the right } q5 b(q5 b R) 0(q5 0 R) 1(q5 1 R) .(q6 . L)
{ if matching 1, erase and repeat } q6 b(q6 . L) 1(q4 . L) b(q7 . R)
{ no more non-'.' characters, accept } q7
*
Turing machine: GpalindromeTM_in.txt
8 states;
alphabet: '. 01', 4 symbols
transition/action matrix:
. b 0 1
q 0 q 1, .,R / / /
q 1 q 7, .,R q 1, .,R q 2, .,R q 5, .,R
q 2 q 3, .,L q 2, b,R q 2, 0,R q 2, 1,R
q 3 q 7, .,R q 3, .,L q 4, .,L /
q 4 q 1, .,R q 4, b,L q 4, 0,L q 4, 1,L
q 5 q 6, .,L q 5, b,R q 5, 0,R q 5, 1,R
q 6 / q 7, .,R / q 4, .,L
q 7 / / / /
Simulating turing machine
|q0>.0 01 10 0.
.|q1>0 01 10 0.
..|q2> 01 10 0.
.. |q2>01 10 0.
.. 0|q2>1 10 0.
.. 01|q2> 10 0.
.. 01 |q2> 10 0.
.. 01 |q2>10 0.
.. 01 1|q2>0 0.
.. 01 10|q2> 0.
.. 01 10 |q2> 0.
.. 01 10 |q2> 0.
.. 01 10 |q2>0.
.. 01 10 0|q2>.
.. 01 10 |q3>0.
.. 01 10 |q4> ..
.. 01 10 |q4> ..
.. 01 10|q4> ..
.. 01 1|q4>0 ..
.. 01 |q4>10 ..
.. 01 |q4> 10 ..
.. 01|q4> 10 ..
.. 0|q4>1 10 ..
.. |q4>01 10 ..
..|q4> 01 10 ..
.|q4>. 01 10 ..
..|q1> 01 10 ..
...|q1>01 10 ..
....|q2>1 10 ..
....1|q2> 10 ..
....1 |q2> 10 ..
....1 |q2>10 ..
....1 1|q2>0 ..
....1 10|q2> ..
....1 10 |q2> ..
....1 10 |q2> ..
....1 10 |q2>..
....1 10 |q3> ..
....1 10 |q3> ...
....1 10|q3> ....
....1 1|q3>0.....
....1 |q4>1......
....1 |q4> 1......
....1|q4> 1......
....|q4>1 1......
...|q4>.1 1......
....|q1>1 1......
.....|q5> 1......
..... |q5> 1......
..... |q5>1......
..... 1|q5>......
..... |q6>1......
..... |q4> .......
.....|q4> .......
....|q4>. .......
.....|q1> .......
......|q1> .......
.......|q1>.......
........|q7>......
........|q7>......
Input accepted
58 simulation steps
|q0>.1 0 1 0 1 0.
.|q1>1 0 1 0 1 0.
..|q5> 0 1 0 1 0.
.. |q5>0 1 0 1 0.
.. 0|q5> 1 0 1 0.
.. 0 |q5>1 0 1 0.
.. 0 1|q5> 0 1 0.
.. 0 1 |q5>0 1 0.
.. 0 1 0|q5> 1 0.
.. 0 1 0 |q5>1 0.
.. 0 1 0 1|q5> 0.
.. 0 1 0 1 |q5>0.
.. 0 1 0 1 0|q5>.
.. 0 1 0 1 |q6>0.
.. 0 1 0 1 |q6>0.
Input not accepted
13 simulation steps
Elapsed time: 0 seconds
TM description for LCCP UTM:
y0000x000.001.1x001.111.1x001 001.1x0010010.1x0011101.1x010.011.0x010 010 1x010001001x010101011x011.111.1x011 011.0x0110100.0x100.001.1x100 100 0x100010000x100110010x101.110.0x101 101 1x101010101x101110111x110 111.1x1101100.0y0
A TM to multiply two numbers in unary format
This example is from Marvin Minsky’s book Computation: Finite and Infinite Machines (Englewood Cliffs, N.J.: Prentice Hall, 1967, p. 125.) The state diagram of the TM is as follows (for convenience, I have renamed the states to fit the simulator’s format):
The following are two simulations, one for 3x2 and one for 2x4. The arguments and the results are shown in bold.
input file? mXnTM_in.txt
number of simulation steps [0 = indefinite]? 0
;
; mXnTM_in.txt
;
; Turing Machine to multiply two unary numbers.
;
; Adapted from Minsky, M. "Computation: Finite and Infinite Machines"
; Prentice-Hall, 1967, p. 125
;
; Input format: ...A...m...y...n...A00000000000000000000
; ^ plenty of 0s to hold the result
;
; Output: ...A00...00y x^n Ax... (x^(mn))
q0 0(q0 0 R) A(q0 A R) 1(q0 1 R) y(q1 y L)
q1 1(q2 0 R) 0(q1 0 L) A(q5 A -)
q2 x(q2 1 R) A(q3 A L) y(q2 y R) 1(q2 1 R) 0(q2 0 R)
q3 y(q1 y L) 1(q4 x R) A(q3 A L) x(q3 x L)
q4 0(q3 x L) A(q4 A R) 1(q4 1 R) x(q4 x R)
q5
*
Turing machine: mXnTM_in.txt
6 states;
alphabet: '01Ayx', 5 symbols
transition/action matrix:
0 1 A y x
q 0 q 0, 0,R q 0, 1,R q 0, A,R q 1, y,L /
q 1 q 1, 0,L q 2, 0,R q 5, A,- / /
q 2 q 2, 0,R q 2, 1,R q 3, A,L q 2, y,R q 2, 1,R
q 3 / q 4, x,R q 3, A,L q 1, y,L q 3, x,L
q 4 q 3, x,L q 4, 1,R q 4, A,R / q 4, x,R
q 5 / / / / /
Simulating turing machine
|q0>00A111y11A00000000
0|q0>0A111y11A00000000
00|q0>A111y11A00000000
00A|q0>111y11A00000000
00A1|q0>11y11A00000000
00A11|q0>1y11A00000000
00A111|q0>y11A00000000
00A11|q1>1y11A00000000
00A110|q2>y11A00000000
00A110y|q2>11A00000000
00A110y1|q2>1A00000000
00A110y11|q2>A00000000
00A110y1|q3>1A00000000
00A110y1x|q4>A00000000
00A110y1xA|q4>00000000
00A110y1x|q3>Ax0000000
00A110y1|q3>xAx0000000
00A110y|q3>1xAx0000000
00A110yx|q4>xAx0000000
00A110yxx|q4>Ax0000000
00A110yxxA|q4>x0000000
00A110yxxAx|q4>0000000
00A110yxxA|q3>xx000000
00A110yxx|q3>Axx000000
00A110yx|q3>xAxx000000
00A110y|q3>xxAxx000000
00A110|q3>yxxAxx000000
00A11|q1>0yxxAxx000000
00A1|q1>10yxxAxx000000
00A10|q2>0yxxAxx000000
00A100|q2>yxxAxx000000
00A100y|q2>xxAxx000000
00A100y1|q2>xAxx000000
00A100y11|q2>Axx000000
00A100y1|q3>1Axx000000
00A100y1x|q4>Axx000000
00A100y1xA|q4>xx000000
00A100y1xAx|q4>x000000
00A100y1xAxx|q4>000000
00A100y1xAx|q3>xx00000
00A100y1xA|q3>xxx00000
00A100y1x|q3>Axxx00000
00A100y1|q3>xAxxx00000
00A100y|q3>1xAxxx00000
00A100yx|q4>xAxxx00000
00A100yxx|q4>Axxx00000
00A100yxxA|q4>xxx00000
00A100yxxAx|q4>xx00000
00A100yxxAxx|q4>x00000
00A100yxxAxxx|q4>00000
00A100yxxAxx|q3>xx0000
00A100yxxAx|q3>xxx0000
00A100yxxA|q3>xxxx0000
00A100yxx|q3>Axxxx0000
00A100yx|q3>xAxxxx0000
00A100y|q3>xxAxxxx0000
00A100|q3>yxxAxxxx0000
00A10|q1>0yxxAxxxx0000
00A1|q1>00yxxAxxxx0000
00A|q1>100yxxAxxxx0000
00A0|q2>00yxxAxxxx0000
00A00|q2>0yxxAxxxx0000
00A000|q2>yxxAxxxx0000
00A000y|q2>xxAxxxx0000
00A000y1|q2>xAxxxx0000
00A000y11|q2>Axxxx0000
00A000y1|q3>1Axxxx0000
00A000y1x|q4>Axxxx0000
00A000y1xA|q4>xxxx0000
00A000y1xAx|q4>xxx0000
00A000y1xAxx|q4>xx0000
00A000y1xAxxx|q4>x0000
00A000y1xAxxxx|q4>0000
00A000y1xAxxx|q3>xx000
00A000y1xAxx|q3>xxx000
00A000y1xAx|q3>xxxx000
00A000y1xA|q3>xxxxx000
00A000y1x|q3>Axxxxx000
00A000y1|q3>xAxxxxx000
00A000y|q3>1xAxxxxx000
00A000yx|q4>xAxxxxx000
00A000yxx|q4>Axxxxx000
00A000yxxA|q4>xxxxx000
00A000yxxAx|q4>xxxx000
00A000yxxAxx|q4>xxx000
00A000yxxAxxx|q4>xx000
00A000yxxAxxxx|q4>x000
00A000yxxAxxxxx|q4>000
00A000yxxAxxxx|q3>xx00
00A000yxxAxxx|q3>xxx00
00A000yxxAxx|q3>xxxx00
00A000yxxAx|q3>xxxxx00
00A000yxxA|q3>xxxxxx00
00A000yxx|q3>Axxxxxx00
00A000yx|q3>xAxxxxxx00
00A000y|q3>xxAxxxxxx00
00A000|q3>yxxAxxxxxx00
00A00|q1>0yxxAxxxxxx00
00A0|q1>00yxxAxxxxxx00
00A|q1>000yxxAxxxxxx00
00|q1>A000yxxAxxxxxx00
00|q5>A000yxxAxxxxxx00
Input accepted
101 simulation steps
|q0>00A11y1111A0000000000
0|q0>0A11y1111A0000000000
00|q0>A11y1111A0000000000
00A|q0>11y1111A0000000000
00A1|q0>1y1111A0000000000
00A11|q0>y1111A0000000000
00A1|q1>1y1111A0000000000
00A10|q2>y1111A0000000000
00A10y|q2>1111A0000000000
00A10y1|q2>111A0000000000
00A10y11|q2>11A0000000000
00A10y111|q2>1A0000000000
00A10y1111|q2>A0000000000
00A10y111|q3>1A0000000000
00A10y111x|q4>A0000000000
00A10y111xA|q4>0000000000
00A10y111x|q3>Ax000000000
00A10y111|q3>xAx000000000
00A10y11|q3>1xAx000000000
00A10y11x|q4>xAx000000000
00A10y11xx|q4>Ax000000000
00A10y11xxA|q4>x000000000
00A10y11xxAx|q4>000000000
00A10y11xxA|q3>xx00000000
00A10y11xx|q3>Axx00000000
00A10y11x|q3>xAxx00000000
00A10y11|q3>xxAxx00000000
00A10y1|q3>1xxAxx00000000
00A10y1x|q4>xxAxx00000000
00A10y1xx|q4>xAxx00000000
00A10y1xxx|q4>Axx00000000
00A10y1xxxA|q4>xx00000000
00A10y1xxxAx|q4>x00000000
00A10y1xxxAxx|q4>00000000
00A10y1xxxAx|q3>xx0000000
00A10y1xxxA|q3>xxx0000000
00A10y1xxx|q3>Axxx0000000
00A10y1xx|q3>xAxxx0000000
00A10y1x|q3>xxAxxx0000000
00A10y1|q3>xxxAxxx0000000
00A10y|q3>1xxxAxxx0000000
00A10yx|q4>xxxAxxx0000000
00A10yxx|q4>xxAxxx0000000
00A10yxxx|q4>xAxxx0000000
00A10yxxxx|q4>Axxx0000000
00A10yxxxxA|q4>xxx0000000
00A10yxxxxAx|q4>xx0000000
00A10yxxxxAxx|q4>x0000000
00A10yxxxxAxxx|q4>0000000
00A10yxxxxAxx|q3>xx000000
00A10yxxxxAx|q3>xxx000000
00A10yxxxxA|q3>xxxx000000
00A10yxxxx|q3>Axxxx000000
00A10yxxx|q3>xAxxxx000000
00A10yxx|q3>xxAxxxx000000
00A10yx|q3>xxxAxxxx000000
00A10y|q3>xxxxAxxxx000000
00A10|q3>yxxxxAxxxx000000
00A1|q1>0yxxxxAxxxx000000
00A|q1>10yxxxxAxxxx000000
00A0|q2>0yxxxxAxxxx000000
00A00|q2>yxxxxAxxxx000000
00A00y|q2>xxxxAxxxx000000
00A00y1|q2>xxxAxxxx000000
00A00y11|q2>xxAxxxx000000
00A00y111|q2>xAxxxx000000
00A00y1111|q2>Axxxx000000
00A00y111|q3>1Axxxx000000
00A00y111x|q4>Axxxx000000
00A00y111xA|q4>xxxx000000
00A00y111xAx|q4>xxx000000
00A00y111xAxx|q4>xx000000
00A00y111xAxxx|q4>x000000
00A00y111xAxxxx|q4>000000
00A00y111xAxxx|q3>xx00000
00A00y111xAxx|q3>xxx00000
00A00y111xAx|q3>xxxx00000
00A00y111xA|q3>xxxxx00000
00A00y111x|q3>Axxxxx00000
00A00y111|q3>xAxxxxx00000
00A00y11|q3>1xAxxxxx00000
00A00y11x|q4>xAxxxxx00000
00A00y11xx|q4>Axxxxx00000
00A00y11xxA|q4>xxxxx00000
00A00y11xxAx|q4>xxxx00000
00A00y11xxAxx|q4>xxx00000
00A00y11xxAxxx|q4>xx00000
00A00y11xxAxxxx|q4>x00000
00A00y11xxAxxxxx|q4>00000
00A00y11xxAxxxx|q3>xx0000
00A00y11xxAxxx|q3>xxx0000
00A00y11xxAxx|q3>xxxx0000
00A00y11xxAx|q3>xxxxx0000
00A00y11xxA|q3>xxxxxx0000
00A00y11xx|q3>Axxxxxx0000
00A00y11x|q3>xAxxxxxx0000
00A00y11|q3>xxAxxxxxx0000
00A00y1|q3>1xxAxxxxxx0000
00A00y1x|q4>xxAxxxxxx0000
00A00y1xx|q4>xAxxxxxx0000
00A00y1xxx|q4>Axxxxxx0000
00A00y1xxxA|q4>xxxxxx0000
00A00y1xxxAx|q4>xxxxx0000
00A00y1xxxAxx|q4>xxxx0000
00A00y1xxxAxxx|q4>xxx0000
00A00y1xxxAxxxx|q4>xx0000
00A00y1xxxAxxxxx|q4>x0000
00A00y1xxxAxxxxxx|q4>0000
00A00y1xxxAxxxxx|q3>xx000
00A00y1xxxAxxxx|q3>xxx000
00A00y1xxxAxxx|q3>xxxx000
00A00y1xxxAxx|q3>xxxxx000
00A00y1xxxAx|q3>xxxxxx000
00A00y1xxxA|q3>xxxxxxx000
00A00y1xxx|q3>Axxxxxxx000
00A00y1xx|q3>xAxxxxxxx000
00A00y1x|q3>xxAxxxxxxx000
00A00y1|q3>xxxAxxxxxxx000
00A00y|q3>1xxxAxxxxxxx000
00A00yx|q4>xxxAxxxxxxx000
00A00yxx|q4>xxAxxxxxxx000
00A00yxxx|q4>xAxxxxxxx000
00A00yxxxx|q4>Axxxxxxx000
00A00yxxxxA|q4>xxxxxxx000
00A00yxxxxAx|q4>xxxxxx000
00A00yxxxxAxx|q4>xxxxx000
00A00yxxxxAxxx|q4>xxxx000
00A00yxxxxAxxxx|q4>xxx000
00A00yxxxxAxxxxx|q4>xx000
00A00yxxxxAxxxxxx|q4>x000
00A00yxxxxAxxxxxxx|q4>000
00A00yxxxxAxxxxxx|q3>xx00
00A00yxxxxAxxxxx|q3>xxx00
00A00yxxxxAxxxx|q3>xxxx00
00A00yxxxxAxxx|q3>xxxxx00
00A00yxxxxAxx|q3>xxxxxx00
00A00yxxxxAx|q3>xxxxxxx00
00A00yxxxxA|q3>xxxxxxxx00
00A00yxxxx|q3>Axxxxxxxx00
00A00yxxx|q3>xAxxxxxxxx00
00A00yxx|q3>xxAxxxxxxxx00
00A00yx|q3>xxxAxxxxxxxx00
00A00y|q3>xxxxAxxxxxxxx00
00A00|q3>yxxxxAxxxxxxxx00
00A0|q1>0yxxxxAxxxxxxxx00
00A|q1>00yxxxxAxxxxxxxx00
00|q1>A00yxxxxAxxxxxxxx00
00|q5>A00yxxxxAxxxxxxxx00
Input accepted
147 simulation steps
Elapsed time: 0 seconds
TM description for LCCP UTM:
y0000x000000001x000100011x000A000A1x000y001y0x001000100x001101001x001A101A1x010001001x010101011x010A011A0x010y010y1x010x01011x0111100x1x011A011A0x011y001y0x011x011x0x1000011x0x100110011x100A100A1x100x100x1y0
The preceding examples of TMs have illustrated the operation of the simulator. Again, all the source files for TMs that I have run are provided. Now I turn to Marvin Minsky’s description of a universal Turing machine.
The "Computer Architecture 101" Game
Besides his crowning achievement on the unsolvability of the halting problem, Turing provided a constructive proof of the existence of a universal machine (UM) which could simulate the operation of any specific TM. Because of this, the UTM is the mathematical model of any general-purpose digital computer. Turing’s contribution to the field of computer science should be considered in light of the fact that his model predated by more than a decade real, stored-program, general-purpose computers in the von Neumann sense.
To the best of my knowledge, the late Marvin Minsky was one of the few authors (if not the only one besides Turing) ever to provide a precise, concise, complete, and working description of a UTM as a TM. (Minsky, M. L. Computation: Finite and Infinite Machines. Englewood Cliffs, N.J.: Prentice-Hall, 1967, pp. 137-143.) Unfortunately, almost no textbook on Automata Theory published after Minsky’s has cared to reproduce or quote his UTM. To my pleasant surprise, it was reproduced by none other than the late Richard Feynman. (Hey, T., and R.W. Allen, Eds. Feynman Lectures on Computation. Westview, 1999, pp. 75-80.) Although saying that his discussion closely followed Minsky’s, Feynman did not go beyond that. The problem is that Minsky’s state diagrams leave out "default" operational details, such as what to do if a symbol on the tape is not what the machine expects in a certain state. Feynman clearly recognized that, for at some point (page 79 in the reference) he tells his reader "[h]ave fun figuring out how it works!" Regarding Turing’s paper, Martin Davis said "This is a brilliant paper, but the reader should be warned that many of the technical details are incorrect as given." (Davis, M, Ed., The Undecidable: Basic Papers On Undecidable Propositions, Unsolvable Problems And Computable Functions, Raven Press, 1965, p. 115.) Charles Petzold went to painstaking detail to correct Turing’s mistakes. (Petzold, C., The Annotated Turing, Wiley Publishing, Inc., 2008, pp. 143-161.)
Since I believe that the UTM is too important a concept to be left as just an interesting mathematical model, I devote this section to the design, implementation, and simulation of Minsky’s UTM. Then, I will use it to simulate a specific TM.
The UTM takes as input (on its tape) a description of a particular TM \(T\), plus the contents of a pseudo-tape on which \(T\) operates. By keeping track of the current state of \(T\), and of the symbol currently scanned by its RW head, the UTM can simulate its operation. Each state of a TM is uniquely specified by means of the quintuple, \(Q_i S_j Q_k S_l D_m\)or in words
<present state, present symbol, next state, next symbol, direction of motion of the RW head>.
Contents of the UTM Tape
The tape of the UTM is divided into several sections. As explained later, each section begins with a special marker symbol. The following figure illustrates the UTM tape.
In the figure above, the pseudo tape of \(T\) spans the cells (or squares) from the beginning of the UTM’s tape to the cell preceding the first cell containing \(q_T\). In the pseudo tape, \(h\) denotes the position of the head of machine \(T\) where the symbol \(S_T\) was scanned.
Binary Notation for Encoding Turing-Machine Quintuples
The quintuples of the TM (\(T\)) to be simulated by the UTM are encoded in terms of the following standard representation.
An example encoding for restricted (binary) four-state TMs is as follows:
x0010110x1011101x1100000y
Encoding of the Condition of a Turing Machine Between its Pseudo-Tape and its Description
The condition (present state [\(q_T\)], symbol scanned [\(s_T\)]) of the TM being simulated by the UTM is bracketed by the special symbols y and x, as shown below. Observe that symbol y marks the end of the TM’s pseudo-tape, while symbol x marks the beginning of the quintuples describing the TM. Further occurrences of x to the right separate quintuples. The last quintuple is followed by symbol y and a 0. (See Minsky, M. Computation: Finite and Infinite Machines. Englewood Cliffs, N.J.: Prentice-Hall, 1967, p. 144.) An example of a UTM tape simulating a four-state TM is as follows:
In the tape above, the present state is 10 and the symbol scanned at \(h\) is 1. In all simulations, h is on the first cell of the pseudo tape and the initial state is \(Q_0\) with the symbol scanned being 0.
The Locate, Copy, Clean-up, Perform (LCCP) UTM
I believe that the beauty of Minsky’s definition of the UTM lies in his decomposition of it into four subroutines which, by themselves, can be implemented as specific TMs! Minsky’s state diagram for the UTM is shown below. (Minsky, M.L. Computation: Finite and Infinite Machines. Englewood Cliffs, N.J.: Prentice-Hall, 1967, p. 142.)
Locate. Search to the right to find the first state-symbol pair that matches the one represented in the "machine condition" area. Along the way, change 0’s to a’s and 1’s to c’s. Upon finding the desired pair (changing its digits also to a’s and c’s), return to the leftmost x. (If no pair is found, the simulation of T is aborted.) The transformation from the initial tape to the tape at the end of a successful search, would look like the following.
Copy. Starting on the leftmost x, go to the right until passing the last a or c and scanning for the first time some 0’s and 1’s. These digits describe the new state \(Q_k\), the new symbol \(S_l\) that must eventually be printed at location h, and the direction of motion \(D_m\). Changing 0’s to a’s and 1’s to c’s, copy the 0’s and 1’s representing \(Q_k\) and \(S_l\) into the machine-condition region; do not put \(D_m\) on the tape, but remember it.
Clean-up. Shift to the left until reaching h. Erase h and put (temporarily) in its place the encoding (a or c) of the direction \(D_m\) remembered. Shift to the right and change all a’s and c’s to 0’s and 1’s, except for the a or c in h’s old location that now represents \(D_m\). Move to the immediate left of the leftmost x. Erase the \(S_l\) which is there, remember it, and put (temporarily) s in its place.
(Actually, the head should be scanning the 1 to the left of s, but I am quoting Minsky’s description.)
Perform. Shift to the left until finding a or c, representing the direction \(D_m\) that \(T\) should move. Put \(S_l\) (0 or 1) in place of the a or c, and shift one square left or right according to whether \(D_m\) was a or c. Read the symbol at the new tape location, remember it, and put h in its place. Shift right until finding s. Replace s by the remembered symbol, using a for 0 and c for 1. Go back to Locate.
Back to the Simulator
Now is the proper place to go over the operation of function DescribeTM of the simulator. This function generates a description of a TM suitable to be processed by the LCCP UTM.
void DescribeTM()
{
int i, j;
printf( "\nTM description for LCCP UTM:\n\n" );
GenerateBinaryStates();
printf( "y%s0", binary[ 0 ] );
for ( i = 0; i < mStates; ++i )
{
for ( j = 0; j < mSymbols; ++j )
{
PrintQuintuple( i, j, TMrule[ i ][ j ] );
}
}
printf( "y0\n" );
}
Function GenerateBinaryStates generates the states comprising the description of the TM for the LCCP UTM.
void GenerateBinaryStates()
{
int i, j, k, nBits = Log2( mStates );
for ( i = 0; i < mStates; ++i )
{
binary[ i ][ nBits ] = '\0';
k = i;
for ( j = nBits - 1; -1 < j; --j )
{
binary[ i ][ j ] = (k & 1) ? '1' : '0';
k >>= 1;
}
}
}
Function Log2 computes the logarithm base-2 of the number of states to obtain the number of bits to encode states in the quintuples.
int Log2( int n )
{
int nBits = 1, Pof2 = 2;
while ( Pof2 < n )
{
Pof2 <<= 1;
++nBits;
}
return nBits;
}
Function PrintQuintuple prints a quintuple in the format required by the LCCP UTM for simulating the TM.
void PrintQuintuple( int i, int j, TMstrPtr p )
{
if ( p != NULL )
{
printf( "x%s%c%s%c%c",
binary[ i ], alphabet[ j ],
binary[ p->q ], p->s, (p->d == 'L') ? '0' : '1' );
}
}
Implementation of the LCCP UTM as a TM
Not surprisingly, this LCCP UTM (so named by me in honor of Minsky’s masterpiece) can be synthesized as any TM to solve a specific problem. Each of the phases of the LCCP UTM will be synthesized and illustrated with the simulation of the simple 2-state TM to generate binary numbers. The transition table for this never-halting TM is
and its encoding for simulation by the LCCP UTM is 0h0010000y00x00001x01110x10011x11100y0.
Locate Phase of the LCCP UTM
Search to the right to find the first state-symbol pair that matches the one represented in the "machine condition" area. Along the way, change 0’s to a’s and 1’s to c’s. Upon finding the desired pair (changing its digits also to a’s and c’s), return to the leftmost x. (If no pair is found, the simulation of T is aborted.)
q0 find leftmost x
q1 scan machine condition, replacing 0/1 by a/c
q2 parse and restore digit of machine condition
q3 digit = 0, skip rest of machine condition until finding x
abort if finding rightmost y;
q4 digit = 1, skip rest of machine condition until finding x
abort if finding rightmost y;
q5 look for 0__ in TM description
q6 look for 1__ in TM description
q7 0__ or 1__ found, go to scan next digit of machine condition
q8 1__/0__ found when looking for 0__/1__, wipe out useless entry
(replace 0/1 by a/c) until finding x for next instruction
q9 look for 'y' on left, replacing 0/1 by a/c, re-start parse
Copy Phase of the LCCP UTM
Starting on the leftmost x, go to the right until passing the last a or c and scanning for the first time some 0’s and 1’s. These digits describe the new state \(Q_k\), the new symbol \(S_l\) that must eventually be printed at location h, and the direction of motion \(D_m\). Changing 0’s to a’s and 1’s to c’s, copy the 0’s and 1’s representing \(Q_k\) and \(S_l\) into the machine-condition region; do not put \(D_m\) on the tape, but remember it.
machine condition located in TM description
q10 find 0/1, replacing by a/c
q11 0 found, find y on left to write "0" (ya__)
q12 1 found, find y on left to write "1" (yc__)
q13 find 0 or 1 on the right, write "0", that is, 'a'
if x found, direction of head motion is 0 = L
q14 find 0 or 1 on the right, write "1", that is, 'c'
if x found, direction of head motion is 1 = R
q15 find x on the right to repeat the copy process
Clean-Up Phase of the LCCP UTM
Shift to the left until reaching h. Erase h and print (temporarily) in its place the encoding (a or c) of the direction \(D_m\) remembered. Shift to the right and change all a’s and c’s to 0’s and 1’s, except for the a or c in h’s old location that now represents \(D_m\). Move to the immediate left of the leftmost x. Erase the \(S_l\) which is there, remember it, and put (temporarily) s in its place.
q16 x found on right, "0" written last = direction is L
find h on left, replace with 'a'
q17 x found on right, "1" written last = direction is R
find h on left, replace with 'c'
q18 restore QtSt region, replacing a/c by 0/1,
until finding leftmost x
q19 restore TM description, replacing a/c by 0/1
q20 find left y
q21 find leftmost x
q22 put 's' temporarily to the immediate left of x
Perform Phase of the LCCP UTM
Shift to the left until finding a or c, representing the direction \(D_m\) that \(T\) should move. Put \(S_l\) (0 or 1) in place of the a or c, and shift one square left or right according to whether \(D_m\) was a or c. Read the symbol at the new tape location, remember it, and put h in its place. Shift right until finding s. Replace s by the remembered symbol, using a for 0 and c for 1. Go to step 1.
move left until finding a or c, representing the direction
that T should move
q23 symbol to write is 0, direction a = L, c = R
q24 symbol to write is 1, direction a = L, c = R
q25 read new symbol, and replace with h
q26 new symbol = 0, find s on the right, replace with 0,
and fetch next instruction
q27 new symbol = 1, find s on the right, replace with 1,
and fetch next instruction
q28 final state
That is all there is to implement the LCCP UTM. Unfortunately, the reader has been deprived of the joy of synthesizing the UTM state by state. I remember this to be one of my favourite tasks when I taught Automata Theory. The application of the LCCP UTM to the simulation of a special-purpose TM will be illustrated next.
A Turing Machine to Compute the Greatest Common Divisor of Two Integers
In order to illustrate the operation of the LCCP UTM, I will use a TM to compute the greatest common divisor (GCD) of two integers. This function can be implemented by Euclid’s algorithm as follows:
int GCD( int m, int n )
{
if ( n < m ) return GCD( n, m );
else
{
int r = n % m;
if ( r == 0 ) return m;
else
{
return GCD( r, m );
}
}
}
This primitive-recursive function can be implemented by a TM. The two integer arguments to the function can be encoded in unary format (so, 3 would be encoded as 111) and be separated by 0. The following is the output produced by the TM simulator for the computation of the GCD of 6 and 4. Obviously the result is 2 (encoded as 11 in unary format). The inputs to the GCD TM and the result are shown in bold.
input file? gcdTM6x4_in.txt
number of simulation steps [0 = indefinite]? 0
; gcdTM6x4_in.txt
;
; TM to compute the primitive recursive function GCD
; (Greatest Common Divisor) by Euclid's algorithm.
;
; gcd( m, n )
; =
; ( <( n, m ) --> gcd( n, m ),
; ==( \( n, m ), 0 ) --> m,
; T --> gcd( \( n, m ), m ) )
;
; Input format: a pair of unary numbers separated by a 0,
; with PLENTY of 0's to the left of the first number.
;
q0 0(q0 0 R) 1(q1 1 L)
q1 0(q2 1 R) 1(q1 1 L)
q2 0(q10 0 R) 1(q3 0 R)
q3 0(q4 0 R) 1(q3 1 R)
q4 0(q4 0 R) 1(q5 0 R)
q5 0(q7 0 L) 1(q6 1 L)
q6 0(q6 0 L) 1(q1 1 L)
q7 0(q7 0 L) 1(q8 1 L)
q8 0(q9 0 L) 1(q8 1 L)
q9 0(q2 0 R) 1(q1 1 L)
q10 0(q11 0 R) 1(q10 1 R)
q11
*
Turing machine: gcdTM6x4_in.txt
12 states;
alphabet: '01', 2 symbols
transition/action matrix:
0 1
q 0 q 0, 0,R q 1, 1,L
q 1 q 2, 1,R q 1, 1,L
q 2 q10, 0,R q 3, 0,R
q 3 q 4, 0,R q 3, 1,R
q 4 q 4, 0,R q 5, 0,R
q 5 q 7, 0,L q 6, 1,L
q 6 q 6, 0,L q 1, 1,L
q 7 q 7, 0,L q 8, 1,L
q 8 q 9, 0,L q 8, 1,L
q 9 q 2, 0,R q 1, 1,L
q10 q11, 0,R q10, 1,R
q11 / /
Simulating turing machine
|q0>000000001111110111100
0|q0>00000001111110111100
00|q0>0000001111110111100
000|q0>000001111110111100
0000|q0>00001111110111100
00000|q0>0001111110111100
000000|q0>001111110111100
0000000|q0>01111110111100
00000000|q0>1111110111100
0000000|q1>01111110111100
00000001|q2>1111110111100
000000010|q3>111110111100
0000000101|q3>11110111100
00000001011|q3>1110111100
000000010111|q3>110111100
0000000101111|q3>10111100
00000001011111|q3>0111100
000000010111110|q4>111100
0000000101111100|q5>11100
000000010111110|q6>011100
00000001011111|q6>0011100
0000000101111|q6>10011100
000000010111|q1>110011100
00000001011|q1>1110011100
0000000101|q1>11110011100
000000010|q1>111110011100
00000001|q1>0111110011100
000000011|q2>111110011100
0000000110|q3>11110011100
00000001101|q3>1110011100
000000011011|q3>110011100
0000000110111|q3>10011100
00000001101111|q3>0011100
000000011011110|q4>011100
0000000110111100|q4>11100
00000001101111000|q5>1100
0000000110111100|q6>01100
000000011011110|q6>001100
00000001101111|q6>0001100
0000000110111|q6>10001100
000000011011|q1>110001100
00000001101|q1>1110001100
0000000110|q1>11110001100
000000011|q1>011110001100
0000000111|q2>11110001100
00000001110|q3>1110001100
000000011101|q3>110001100
0000000111011|q3>10001100
00000001110111|q3>0001100
000000011101110|q4>001100
0000000111011100|q4>01100
00000001110111000|q4>1100
000000011101110000|q5>100
00000001110111000|q6>0100
0000000111011100|q6>00100
000000011101110|q6>000100
00000001110111|q6>0000100
0000000111011|q6>10000100
000000011101|q1>110000100
00000001110|q1>1110000100
0000000111|q1>01110000100
00000001111|q2>1110000100
000000011110|q3>110000100
0000000111101|q3>10000100
00000001111011|q3>0000100
000000011110110|q4>000100
0000000111101100|q4>00100
00000001111011000|q4>0100
000000011110110000|q4>100
0000000111101100000|q5>00
000000011110110000|q7>000
00000001111011000|q7>0000
0000000111101100|q7>00000
000000011110110|q7>000000
00000001111011|q7>0000000
0000000111101|q7>10000000
000000011110|q8>110000000
00000001111|q8>0110000000
0000000111|q9>10110000000
000000011|q1>110110000000
00000001|q1>1110110000000
0000000|q1>11110110000000
000000|q1>011110110000000
0000001|q2>11110110000000
00000010|q3>1110110000000
000000101|q3>110110000000
0000001011|q3>10110000000
00000010111|q3>0110000000
000000101110|q4>110000000
0000001011100|q5>10000000
000000101110|q6>010000000
00000010111|q6>0010000000
0000001011|q6>10010000000
000000101|q1>110010000000
00000010|q1>1110010000000
0000001|q1>01110010000000
00000011|q2>1110010000000
000000110|q3>110010000000
0000001101|q3>10010000000
00000011011|q3>0010000000
000000110110|q4>010000000
0000001101100|q4>10000000
00000011011000|q5>0000000
0000001101100|q7>00000000
000000110110|q7>000000000
00000011011|q7>0000000000
0000001101|q7>10000000000
000000110|q8>110000000000
00000011|q8>0110000000000
0000001|q9>10110000000000
000000|q1>110110000000000
00000|q1>0110110000000000
000001|q2>110110000000000
0000010|q3>10110000000000
00000101|q3>0110000000000
000001010|q4>110000000000
0000010100|q5>10000000000
000001010|q6>010000000000
00000101|q6>0010000000000
0000010|q6>10010000000000
000001|q1>010010000000000
0000011|q2>10010000000000
00000110|q3>0010000000000
000001100|q4>010000000000
0000011000|q4>10000000000
00000110000|q5>0000000000
0000011000|q7>00000000000
000001100|q7>000000000000
00000110|q7>0000000000000
0000011|q7>00000000000000
000001|q7>100000000000000
00000|q8>1100000000000000
0000|q8>01100000000000000
000|q9>001100000000000000
0000|q2>01100000000000000
00000|q10>1100000000000000
000001|q10>100000000000000
0000011|q10>00000000000000
00000110|q11>0000000000000
00000110|q11>0000000000000
Input accepted
138 simulation steps
Elapsed time: 0 seconds
TM description for LCCP UTM:
y00000x00000000001x00001000110x00010001011x00011000110x00100101001x00101001101x00110010001x00111001111x01000010001x01001010101x01010011100x01011011010x01100011000x01101000110x01110011100x01111100010x10000100100x10001100010x10010001001x10011000110x10100101101x10101101011y0
What is important now is the description of the GCD TM (shown just above) for its simulation by the LCCP UTM.
Description of the LCCP UTM
The description of the LCCP UTM and its input tape for the TM simulator can be written from the transition tables agiven bove for the implementation of the LCCP UTM. The input tape contains the pseudo tape and the description of the TM to be simulated. The pseudo tape of the TM to be simulated is shown in bold.
;
; LCCP_UTM_in.txt
;
; Description of the LCCP UTM for simulation
;
29
x01acyhs
;
; Locate Phase
;
q0 x(q1 x L) 0(q0 0 R) 1(q0 1 R) y(q0 y R) h(q0 h R)
q1 x(q1 x L) 0(q1 a L) 1(q1 c L) y(q2 y R)
q2 x(q10 x R) a(q3 0 R) c(q4 1 R)
q3 x(q5 x R) a(q3 a R) c(q3 c R) y(q28 y -)
q4 x(q6 x R) a(q4 a R) c(q4 c R) y(q28 y -)
q5 x(q5 x R) 0(q7 a L) 1(q8 c R) a(q5 a R) c(q5 c R)
q6 x(q6 x R) 0(q8 a R) 1(q7 c L) a(q6 a R) c(q6 c R)
q7 x(q7 x L) 0(q2 0 R) 1(q2 1 R) a(q7 a L) c(q7 c L)
q8 x(q9 x L) 0(q8 a R) 1(q8 c R)
q9 x(q9 x L) 0(q9 a L) 1(q9 c L) a(q9 a L) c(q9 c L) y(q2 y R)
;
; Copy Phase
;
q10 x(q10 x R) 0(q11 a L) 1(q12 c L) a(q10 a R) c(q10 c R)
q11 x(q11 x L) 0(q11 0 L) 1(q11 1 L) a(q11 a L) c(q11 c L) y(q13 y R)
q12 x(q12 x L) 0(q12 0 L) 1(q12 1 L) a(q12 a L) c(q12 c L) y(q14 y R)
q13 x(q16 x L) 0(q15 a R) 1(q15 a R) a(q13 a R) c(q13 c R)
q14 x(q17 x L) 0(q15 c R) 1(q15 c R) a(q14 a R) c(q14 c R)
q15 x(q10 x R) 0(q15 0 R) 1(q15 1 R)
;
; Clean-Up Phase
;
q16 0(q16 0 L) 1(q16 1 L) a(q16 a L) c(q16 c L) y(q16 y L) h(q18 a R)
q17 0(q17 0 L) 1(q17 1 L) a(q17 a L) c(q17 c L) y(q17 y L) h(q18 c R)
q18 x(q19 x R) 0(q18 0 R) 1(q18 1 R) a(q18 0 R) c(q18 1 R) y(q18 y R)
q19 x(q19 x R) 0(q20 0 L) 1(q20 1 L) a(q19 0 R) c(q19 1 R) y(q20 y L)
q20 x(q20 x L) 0(q20 0 L) 1(q20 1 L) y(q21 y R)
q21 x(q22 x L) 0(q21 0 R) 1(q21 1 R)
q22 0(q23 s L) 1(q24 s L)
;
; Perform Phase
;
q23 0(q23 0 L) 1(q23 1 L) a(q25 0 L) c(q25 0 R) y(q23 y L)
q24 0(q24 0 L) 1(q24 1 L) a(q25 1 L) c(q25 1 R) y(q24 y L)
q25 0(q26 h R) 1(q27 h R)
q26 0(q26 0 R) 1(q26 1 R) y(q26 y R) s(q1 0 R)
q27 0(q27 0 R) 1(q27 1 R) y(q27 y R) s(q1 1 R)
q28
*
h00000001111110111100y00000x00000000001x00001000110x00010001011x00011000110x00100101001x00101001101x00110010001x00111001111x01000010001x01001010101x01010011100x01011011010x01100011000x01101000110x01110011100x01111100010x10000100100x10001100010x10010001001x10011000110x10100101101x10101101011y0
!
The following figure shows the console screen at the end of the simulation.
The simulation of the greatest common divisor TM by the LCCP UTM yielded the result 110h (2 in unary format to the left of symbol h) for the inputs 6 (111111) and 4 (1111). The simulation took 840,039 steps in 42,630 seconds (710.5 minutes, 11.84 hours). Observe that the simulator printed "input not accepted." This will always be the printout when the simulator runs the LCCP UTM.
More importantly, at the end of the simulation, there is a TM description for the LCCP UTM. But in this case, the description is that of the LCCP UTM itself. This means that the LCCP can simulate itself simulating a particular TM! In 2003 I did so and the simulation took almost 1.5 million steps. Re-directing the output to a file, the output file size was 438,874,709 bytes.
Running the Code
The ZIP file contains two directories: Turing and tms. The Turing directory contains the source code Turing.cpp and the tms directory contains the text files for all the Turing machines described in this article. To run the code, create an unmanaged C++ solution named Turing. Replace the Turing.cpp default code with the code from the Turing directory. To simulate a Turing machine, say sampleTM, copy the sampleTM.txt and sampleTM_in.txt files to the unmanaged C++ Debug directory. Change to that directory. Then, at the command prompt, issue the command
Turing.exe <sampleTM.txt
