A Turing Machine with GPSS

Course: CSC-554

Yields in One Step implemented with GPSS, James Canavan
E-Mail: jaco@donotenter.com
WWW: www.donotenter.com
© December, 1993

Table of Contents

What is a Turing Machine?

A turing machine is defined as a set of sets and a function that defines the changes in these sets.

M =(K,Sigma, s, Delta)

Delta = is the actual function that determines the following states- yet, this set (Delta) is really a set of functions that define each move.
K = is the set of all the states possible,
Sigma = is the alphabet for the machine,
s = is the first state.

Definition 4.1.3 from "elements of the theory of computation", Harry Lewis, et. al.

Let be a Turing machine and let (q1,w1,a1,u1) and (q2,w2,a2,u2) be configurations of M.


(q1,w1,a1,u1) --->M (q2,w2,a2,u2)

RETURN TO TOP OF PAGE

This definition tells which state to "fire" - that is, how to move down the tape using the machine definition defined in Delta. To do this there are several conditions - they are given formally as three conditions defined after it has been assured that b (the new symbol read from the tape) is a member of Sigma or a machine directive (L, R) - and of course, b must be a part of the definition in a valid transition state. Either the machine goes to the next state defined when it reads in a b character, or it follows one of the Machine directives (L, R). - the head moves LEFT or it moves RIGHT. My use of this algorithm counts the instances of a comparison - I use this for my Sigma. That is, instead of using the output as an alphabet of characters - I use the number of mappings between states. My example uses two states:

Figure One: Number of Mappings Between States

The selection of f1 - f4 comes from 1) generating a random number (uniform) between 1 and 10, 2) testing if that number is less than 5. Since all the functions are the same ( although I used three identical functions in code for clarity ) - the generated counts came very close to each other - so close, in fact, regression analysis was not needed; all I had to do was look at the data in order to say, " ... yea, it looks about the same". But 'running' this algorithm ( same GPSS code ) on two different machines ( 25 MHz, 386 PC and 12 MHz, 8088 IBM laptop ) gave ( sort of depressing, yet ) surprising results.

Figure Two: Yields In One Step Algorythm

Basically, after we consider the machines to be pre-defined, there are 3 different cases to consider when implementing the function Yields In One Step: (one) we re-write a symbol - without moving the head position, (two) we move to the LEFT one square, (three) we move to the RIGHT one square. When moving either way, we come across a blank - that blank becomes the present scanned symbol.

Yields in one step defines a mapping of S1 to S2 - this project uses this algorithm on two machines by running a GPSS program simulation. The alphabet is replaced with a simple count the number of times the same function is selected. The function is a simple comparison of a randomly generated number.

I felt that this algorithm, if implemented on two different microprocessors, would result in two different numbers of function calls - since I was using the cardinality of function calls as the set Sigma. The machine directives ( that is, whether the head (pointer) moves LEFT or RIGHT) were NOT stored on the tape (logically) - but rather coded into the code. Unknowingly, I coded this logic as a sequential execution of the same function, rather than a Poisson distribution of different (even just two) functions. My main thesis question for this projects is:

Using a similar "yields in one step" algorithm ( implemented with GPSS ) , what hardware responses result from two different computers (PC's)?

RETURN TO TOP OF PAGE

GPSS Code Listing:

;GPSS/PC Program File B:TUR2.GPS. (V 2, # 39271)
10 *
20 STRING MATRIX ,10,5
30 ACCEPT FUNCTION RN3,C2
0.0,0/1.0,10
40 STATE1 FUNCTION RN1,C2
0.0,0/1.0,10
50 STATE2 FUNCTION RN2,C2
0.0,0/1.0,10
60 GENERATE ,,,100
70 TEST LE 5,FN$ACCEPT TRAP ;null string
80 IN_Q1 TEST LE 5,FN$STATE1 GO_Q2
90 CHECK1 TEST LE 5,FN$ACCEPT TRAP
100 *
110 MSAVEVALUE STRING+,1,2,1
120 TRANSFER ,IN_Q1
130 IN_Q2 TEST LE 5,FN$STATE2 GO_Q1
140 CHECK2 TEST LE 5,FN$ACCEPT TRAP
150 *
160 MSAVEVALUE STRING+,1,4,1
170 TRANSFER ,IN_Q2
180 GO_Q2 MSAVEVALUE STRING+,1,1,1
190 TRANSFER ,IN_Q2
200 GO_Q1 MSAVEVALUE STRING+,1,3,1
210 TRANSFER ,IN_Q1
220 TRAP MSAVEVALUE STRING+,10,5,1
300 TERMINATE 1
RETURN TO TOP OF PAGE

Data Capture and Results:

Using GPSS's matrix window feature, I counted the occurrences of functions seven times for both the 386, 25 MHz, and 8088 12 MHz computers. The averages I got were very similar; I checked out the differences between 'run' values - no noticeable differences could be found. Conclusion: the algorithm runs the same on both computers.

RETURN TO TOP OF PAGE

Conclusions:

At first glance, no differences between the number of function choices seems to offer no conclusion. But, insight into how the turing algorithm was manipulated into this analysis seeps out:

* The functions are basically sequential.
* The functions:
1) accept at q1 or q2,
2) change states,
3) go to trap state -implying nondeterminism

* The machine logic (defined as controlled by LEFT or RIGHT) was determined by the program - not the tape.
Perhaps, if these program 'constructs' were changed around, a difference in function calls would be noticed.

RETURN TO TOP OF PAGE

Bibliography:

1) Elements of the Theory of Computation, Harry R. Lewis &, Christos H. Papadimitriou, Prentice-Hall, Inc., Englewood Cliffs, New Jersey, 1981.
2) Program Verification, Nissim Francez, Addison-Wesley Publishing Company, 1992.
3) The Science of Programming, David Gries, Springer-Verlag, 1981.
4) The Logical Design of Operating Systems, Lubomir, Alan Shaw, Prentice-Hall, 1988.
5) GPSS manual, and tutorial.
6) Class Notes from CSC-554, Sam Sengupta, 1993.

Here is the author's E-mail address: jaco@donotenter.com