home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
OS/2 Shareware BBS: 8 Other
/
08-Other.zip
/
TURING.ZIP
/
TURING.DOC
< prev
next >
Wrap
Text File
|
1990-06-23
|
31KB
|
598 lines
Turing Machine
Simulator
for
OS/2
by
Bert Casper
May, 1990
Table of Contents
1. Overview. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
2. User's Guide. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
2.1 Program Syntax . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
2.2 Input File Syntax. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.2.1 The Value Fields. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.2.2 Subroutines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.2.3 Some Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
3. How the Program Works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3.1 Compilation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3.2 Program Structure. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1. Overview
The program described in this document simulates various different types of Turing machines in
OS/2's graphical environment. It reads specification input files and then checks whether or not user
provided input is accepted by the specified Turing machine.
The program can simulate the following types of Turing machines,
Standard (single, half infinite tape, single track, no memory, no subroutines).
Up to two memory registers in the Turing machine.
Up to four tracks on the tape.
Turing machine subroutines.
Moves are either left, right or stationary.
Variables in transaction specifications are supported.
The program will run on any OS/2 compatible machine, and requires no special graphic adapters.
It has no memory requirements beyond those for OS/2. It is compatible with OS/2, versions 1.1,
1.2 and above, both standard and extended editions.
All source code for the simulator was written in C. Chapter 3 describes the source code and how
to compile and link it on a standard OS/2 workstation.
2. User's Guide
The program's name is TURING.EXE, and it is started from either a full-screen or windowed OS/2
command prompt, by typing: START TURING. This will always open a graphical window under
the Presentation Manager for the program.
Note that it may be necessary to start several copies of the program to use certain of its functions
(see below).
2.1 Program Syntax
The program has a menu bar with the following entries: File, Input, Speed, Start, Step, Initialize
and Stop. To exit the program, use the pull down menu icon in the top-left-hand corner.
File: Clicking this function will pop up a dialogue box, which prompts for a file name. The
default is ON1N.TUR. Enter the file name for the Turing machine specification which
you wish to run and click the OK button. Note that the program will search for the file
only on the current directory. Enter a directory path if the file is not in the current
directory. Click the CANCEL button if you wish to cancel this operation.
After the OK button is clicked, the program will automatically load the specification
(or give you an error message if it cannot do so), and initialize the machine to run.
Input: Clicking this function will pop up a dialogue box, which prompts for input to the tracks
of the Turing machine's tape. Enter the number of the track you want to provide input
for in the first field and then press <TAB> to switch to the second field. Note that the
cursor will automatically jump to the end of this second input field, which may not be
visible in the dialogue box. To bring the cursor to the beginning of the entry field, press
<HOME>. Now enter your input string. You may edit this input string by using the
standard keyboard editing functions.
After the input is correct, click the OK button. The machine will display the input on
the tape. Note that it is impossible to provide input for more than one track at once. To
provide input for several tracks, use the input function repeatedly.
Speed: Clicking this function will pop up a dialogue box, which prompts for the delay which
is to be applied between successive Turing machine transactions. The default is 300 ms.
The minimum delay is 0 and the maximum delay is practically unlimited. All delays are
given in milliseconds. The delay is useful for having the Turing machine execute quickly
if it is just to be determined if a specified string is accepted or not, and having the
machine execute slowly if its exact operation is to be studied.
Start: Click this function to start execution of the Turing machine. You can restart the Turing
machine with this function if you stopped it at any time before it finished execution.
Initialize:Clicking this function will set all machine parameters, like the positioning of the head,
and the current state, to their defaults, as provided by the specification file. This function
is useful if a machine is to be run more than once with the same input.
Step: This function allows a stepwise execution of the Turing machine. It can only be used
after the machine has been started, using the START function, described above. To use
the STEP function, start the execution of the machine, using the START function and
then stop it immediately using the STOP function described below. You can make sure
that it executes no more than one step by increasing the machine's delay time, as
specified by using the SPEED function. Now click the STEP function every time you
wish the machine to proceed to execute the next transaction. You can restart the machine
at any time, causing it to execute automatically, by clicking the START function.
Stop: This function will stop the execution of a Turing machine immediately. The machine can
be restarted by using the START function. It can also be executed stepwise by using the
STEP function.
If the Turing machine accepts an input string, it will play a few happy notes, and if it does not
accept it, it will 'grunt'. Note that it is possible for the machine to execute forever, in which case
the string is not accepted. Usually this is easily seen. In this case you have to stop the machine
manually, by using the STOP function, described above.
Inside the head of the machine, the simulator always displays the current state of the Turing
machine, which is P, followed by a number, 0 or greater. Below the state the simulator shows
either one or two boxes in the head of the machine, which represent the memory registers of the
Turing machine. The simulator will always display the current contents of these registers inside the
boxes.
At the bottom left-hand corner of the screen, the simulator displays the current position of the
head on the tape (the first position is 1). It also displays the total number of moves or transactions
which the head or machine has gone through while reading and processing the current input. In a
box at the bottom center of the screen, the simulator displays the name of the Turing machine, as
provided in the input file syntax specification (see below).
2.2 Input File Syntax
The TMS accepts standard ASCII files, created with any ASCII editor, which have the general
format given in text box 1. Some notes of caution about the file format,
- The file may not contain any special codes or symbols, which a word
processor, like for example WordPerfect inserts into documents to
paginate them.
- The only white character the file may contain is a blank. There may
be no TABS or so-called white ASCII symbols (symbols which appear
to be a blank on a standard text screen) in it.
- The maximum file size is currently 5000 bytes. This number is totally
arbitrary.
To better understand the input file syntax, it is a good idea to look at how the program reads the
file. From the program's point of view the file has 5 fields,
(1) The first field contains non-blank characters which make up words that are
helpful descriptions to the user. The standard words used in the input file are
given in text box 1. The first descriptive word is TRACKS. It identifies to the
user that the number that follows is the number of tracks of the input tape. None
of these words is fixed. The user can substitute whatever he wishes. However,
the order is important and must be strictly obeyed.
(2) The second field is a variable number of blanks. There must be at least one
blank in this field. This field serves only for readability, to offset the actual
values from the descriptive words.
(3) The third field is a value, or a number of values, as described below.
(4) The fourth field only applies to the transactions at the end of the file. It is the
field containing the '=', for the delta-function assignments. It may contain a
variable number of blanks before the '=' and a variable number of blanks after
the '='. There must be at least one blank before and one blank after the '='.
(5) The fifth field is the second transaction value, as described below.
2.2.1 The Value Fields
The value fields contain the actual information which makes up the Turing Machine. They are fields
three and five. Symbols for these values are used in text box 1, and these symbols will be
described in detail below,
string (NAME) The string is a series of ASCII characters with ASCII values 30 or
greater, no more than 30 in length, which identifies the Turing machine.
t (TRACKS) The t can stand for a numerical value between 1 and 4 inclusive, which
indicates the number of tracks of the Turing Machine.
s (STATES) The s stands for the total number of states of the Turing Machine. It
must be greater than zero. Note that a Turing Machines with states p0,
p1 and p2 has three states. The total number of states includes the
initial and final states. The maximum number of states supported is 99.
m (MEMORY) The m stands for the number of internal memory registers which the
Turing Machine has. This number is a value between 0 and 2 inclusive.
Σi (SIGMA) Stands for the ith component of the sigma set of the Turing Machine,
i.e. the set of input symbols. The set's components are separated by
commas.
Γi (GAMMA) Stands for the ith component of the gamma set of the Turing Machine,
i.e. the set of output symbols. The set's components are separated by
commas.
f (FINAL) The f stands for the number of the final state of the Turing Machine,
i.e. the state which is to be interpreted as the final state. There can be
no more than one final state. If a Turing Machine has three states, p0,
p1 and p2, and the final state is p2, then the value of f is 2.
ti (TRANS) Stands for the various transaction values. There can be a maximum of
15 of these values, and a minimum of 5. The 'i' can stand for the
following,
1: Input state: Has to be a valid state number (REQUIRED).
2: Input memory 1: Can be an element of the set gamma, or a '*'.
The '*' stands for 'don't care', meaning that the value of this
memory location does not matter. (OPTIONAL: REQUIRED
if MEMORY is 1 or 2).
3: Input memory 2: Can be an element of the set gamma, or a '*'.
The '*' stands for 'don't care', meaning that the value of this
memory location does not matter. (OPTIONAL: REQUIRED
if MEMORY is 2).
4: Input from track 1: Can be an element of the set gamma, or
one of the following,
d => Has to be equal to memory location 1.
e => Has to be equal to memory location 2.
f => Has to be not-equal to memory location 1.
g => Has to be not-equal to memory location 2.
* => Don't care.
(REQUIRED).
5: Input from track 2: Identical to item 4. (OPTIONAL:
REQUIRED if TRACKS is 2 or greater).
6: Input from track 3: Identical to item 4. (OPTIONAL:
REQUIRED if TRACKS is 3 or greater).
7: Input from track 4: Identical to item 4. (OPTIONAL:
REQUIRED if TRACKS is 4).
8: Output state: Has to be a valid state number (REQUIRED).
9: Output memory 1: Can be an element of the set gamma, or one
of the following,
d => The input from track 1 goes into memory 1.
e => The input from track 2 goes into memory 1.
f => The input from track 3 goes into memory 1.
g => The input from track 4 goes into memory 1.
* => The memory is not altered.
(OPTIONAL: REQUIRED if MEMORY is 1 or 2).
10: Output memory 2: Identical to item 9 with memory 1 replaced
by memory 2. (OPTIONAL: REQUIRED if MEMORY is
2).
11: Output to track 1: Can be an element of the set gamma, or one
of the following,
d => Contents of memory 1 are output.
e => Contents of memory 2 are output.
f => Input from track 2 is output.
g => Input from track 3 is output.
h => Input from track 4 is output.
* => Input from track 1 is output.
(REQUIRED).
12: Output to track 2: Can be an element of the set gamma, or one
of the following,
d => Contents of memory 1 are output.
e => Contents of memory 2 are output.
f => Input from track 1 is output.
g => Input from track 3 is output.
h => Input from track 4 is output.
* => Input from track 2 is output.
(OPTIONAL: REQUIRED if TRACKS is 2 or greater).
13: Output to track 3: Can be an element of the set gamma, or one
of the following,
d => Contents of memory 1 are output.
e => Contents of memory 2 are output.
f => Input from track 1 is output.
g => Input from track 2 is output.
h => Input from track 4 is output.
* => Input from track 3 is output.
(OPTIONAL: REQUIRED if TRACKS is 3 or greater).
14: Output to track 4: Can be an element of the set gamma, or one
of the following,
d => Contents of memory 1 are output.
e => Contents of memory 2 are output.
f => Input from track 1 is output.
g => Input from track 2 is output.
h => Input from track 3 is output.
* => Input from track 4 is output.
(OPTIONAL: REQUIRED if TRACKS is 4).
15: Direction of move: Can be one of the following,
R => Head moves right.
L => Head moves left.
S => Head remains stationary.
(REQUIRED).
The Turing machine may include as many transactions as desired (to the maximum size of the
file). The transactions may be of two types, as shown in text box 1. The first, or standard type
specifies the state transition and new values for memory and or tracks which the turing machine
is to go to when it reaches a certain state and reads a certain input. The second type is used to
specify that a subroutine is to be called. The right hand side then has the special form shown in
text box 1:
[C:state:string]
The C is just an identifier (which could stand for Call). The state is the state which the
subroutine call is to return to, and the string is a file name for a Turing machine specification,
which the program uses to define the subroutine, which has to be a Turing machine.
2.2.2 Subroutines
The Turing machine simulator can simulator Turing machine subroutines. This is implemented in
the following way,
All tapes of the main machine are copied to the sub-machine. The sub-machine
does not have to make use of all of them.
The current position of the main machine is where the sub-machine starts
execution. For the sub-machine this is the beginning of the tape. It cannot alter
anything that is on the tape to the left of this position.
If the sub-routine fails, the input is not accepted.
If the sub-routine accepts the input it returns the result, meaning all tracks it
altered, plus its current position to the main machine. The main machine
continues execution from that position and with the altered input data.
The syntax for using a subroutine is specified in section 2.2.1. Note that the main machine is
always responsible for presenting the sub-machine with an input tape it will accept, from the
position it is at when it makes the call, onward.
Theoretically there is no limit to the depth of nesting which can be used. I.e. a subroutine can
call a subroutine, can call a subroutine, etc. Practically this is not of much use, since a standard
screen cannot display very many turing machine windows in such a way that the user can still see
what the simulator is doing.
2.2.3 Some Examples
Example 1: The text box below shows the specification for the very simple Turing machine,
called Zero=One (the file name is ON1N.TUR).
This Turing machine checks whether or not the number of zeros in the input
equals the number of ones. It requires no memory, and only one track. It does
not call any subroutines. Note that no use is made of variables in the
transactions.
Example 2: The text box below shows the specification for a Turing machine which reverses
the input. Technically the input has to consist of elements of the set sigma, but
since the specification uses variables, it will accept any input and reverse it.
The Turing machine requires two memory registers and makes much use of
variables in order to keep down the number of transactions which have to be
specified in the specification. The machine uses only one track, and no
subroutines.
Example 3: The following Turing machine is an example of a multi-track machine. It uses
two tracks and accepts strings of the form wcw, and uses the second track for
checking off symbols. It requires one memory register to remember the symbols
it compares. The machine also makes use of various variables to reduce the
number of transactions required in the specification.
Example 4: The following Turing machine is an example of a machine which calls a
subroutine. The main machine is shown in text box 5 and the subroutine is
shown in text box 6. The whole machine will multiply two numbers given in
unary format (i.e. 000100 will return 000000).
3. How the Program Works
3.1 Compilation
The Turing machine simulator program listing is given in the appendix. It has two compilation
units, called TURING.C and TURING2.C. To compile the simulator, the following files are
required,
- TURING.C
- TURING2.C
- TURING.H
- TURING.RC
- TURING.DEF
Either the IBM C compiler 1.1, or the Microsoft C compiler version 5.1 or higher are needed to
compile the program. The program must be compiled in OS/2 protected mode. Also needed are the
resource compiler and the include files and library files which are part of the OS/2 Programmer's
Toolbox, available from both IBM and Microsoft.
To compile and link the program, proceed as follows,
(1) Compile the two compilation units of the simulator, by executing the following command-
line commands,
cl -c -Alfw -G2sw -Gt -W3 turing.c
cl -c -Alfw -G2sw -Gt -W3 turing2.c
Note that case is important for the compiler and must strictly be observed. This implies
that the 'A' must be capital, as must the 'G' and the 'W', while all other characters must
be lowercase. The program names are not case-sensitive.
(2) Next link the compilation units to the necessary libraries to produce an executable file,
by executing the following command,
link turing turing2, /align:16, NUL, os2, turing
Again, this is case-sensitive.
(3) The final step in the compilation process is to compile the resource file (TURING.RC)
and link it to the already existing executable file (TURING.EXE). Note: If this step is
omitted, the program will not work! Use the following command line command,
rc turing
This is not case-sensitive.
To make the compilation process easier, a batch file, called TURMAKE.CMD exists, which will
do all the above. No make-file is included, since the make-file formats of IBM's C and Microsoft's
C are different.
3.2 Program Structure
The program has standard OS/2 Presentation Manager structure. The MAIN routine does nothing
but create a queue and manage it. The ClientWndProc is responsible for correspondence with the
Presentation Manager. There are three dialogue procedures, called FileDlgProc and InputDlgProc,
and SpeedDlgProc which handle user input. All other functions are called from the ClientWndProc
and are custom functions of the simulator. What they do is explained in detail below.
main Creates and then manages the program's queue. Destroys this queue when the
program is exited. (located in TURING.C, lines 38-61).
ClientWndProc Basically consists of a large SWITCH procedure which handles those incoming
messages which are of interest to the simulator. Most of these messages involve
OS/2 specific handling, and a treatment of this goes beyond the scope of this
document. (located in TURING.C, lines 64-334).
FileDlgProc Creates a dialogue box which is displayed when the user wishes to change the
input file name. The user input is then returned to the program. (located in
TURING2.C, lines 662-683).
InputDlgProc Creates a dialogue box which is displayed when the user wishes to change the
input of the tape. The user specifies to which track he wishes to give input and
then specifies the input itself. (located in TURING2.C, lines 606-635).
SpeedDlgProc Creates a dialogue box which is displayed when the user wishes to change the
speed with which the simulator executes. The user specifies a delay which is
applied between successive transactions. This delay can can be from 0 to 65536
milliseconds in length. (located in TURING2.C, lines 638-659).
Turing The main work-horse of the simulator. This routine is called to process a
transaction of the Turing machine. All transactions of the current machine are
loaded into the structure DELTA, shown on lines 20 to 28 in the listing of
TURING2.C in the appendix, by the load routine, described below. The turing
routine indexes this structure with the current state to determine what possible
input and memory combinations will lead to a state change. It checks all
possibilities, until it finds a match. The first match is always executed. If it does
not find a match, the simulation fails, i.e. the input string is not accepted.
If a match is found, the memory register(s) (MEMORY[]), the position of the
head (POSITION), the tape (INPUT[][]), and the current state (STATE) are
updated and the routine exits. If the new state is the final state, the simulator
accepts the input string by playing a merry tune and the routine is exited.
(located in TURING2.C, lines 41-254).
Load This routine is called whenever new specification data is to be loaded from a
new specification file. The routine reads the file sequentially, skipping all valid
blanks and descriptive words in it to read the relevant values into the various
data structures of the program. Note that no syntax checking of any kind is
performed. If the syntax of the file is incorrect, the results are unpredictable.
(located in TURING2.C, lines 257-407).
Draw_Screen This routine draws the tape, its contents and the informational boxes at the
bottom of the screen. (located in TURING2.C, lines 524-584).
Draw_Machine This routine draws the Turing machine's head and the memory registers, as well
as the state inside it. The routine is called whenever the head moves, to redraw
the head in its new position. (located in TURING2.C, lines 433-501).
Erase_Machine This routine is needed to erase the machine's head, so that it can be redrawn
in a new position. (located in TURING2.C, lines 504-521).
Update_Tape This routine is used to update the input/output tape whenever the Turing machine
writes data out to it. The routine can handle all tracks of the tape, but the track
it should write to must be specified. (located in TURING2.C, lines 410-430).
Initialize This routine resets all parameters of the simulation, which allows it to be
restarted at any point. (located in TURING2.C, lines 587-603).
