CSc 8710 - Fall 2002
Homework 2
Due: 10 September, 2002
-----------------------

(1) Solve Problem 2.2 of the online text in Prolog

(2) Write a Turing Machine Simulator in Prolog.

Assume a Turing Machine is described using two predicates: 

  start_state(State).
  delta(FromState,ToState,ReadSymbol,WriteSymbol,MoveDirection).

For example the following is a TM for accepting language with
strings involving a's and b's and having equal number of a's and b's.

start_state(1).
delta(1,1,b,b,r).
delta(1,1,x,x,r).
delta(1,2,a,x,l).
delta(1,5,#,#,l).
delta(2,2,x,x,l).
delta(2,2,b,b,l).
delta(2,3,#,#,r).
delta(3,3,a,a,r).
delta(3,3,x,x,r).
delta(3,4,b,x,l).
delta(4,4,a,a,l).
delta(4,4,x,x,l).
delta(4,1,#,#,r).
delta(5,5,x,x,l).
delta(5,h,#,#,r).

Note: States are numbered 1 thru n and h stands for the halt state; 
      The # symbol is used to denote blank symbol on tape.

The TM Simulator program will behave as follows under Prolog:

[~/8710][4:27pm] pl
Welcome to SWI-Prolog (Version 3.2.9)
Copyright (c) 1993-1999 University of Amsterdam.  All rights reserved.

For help, use ?- help(Topic). or ?- apropos(Word).

?- ['tm.pro'].
tm.pro compiled, 0.00 sec, 3,196 bytes.

Yes
?- ['equal.tm'].
equal.tm compiled, 0.01 sec, 1,556 bytes.

Yes
?- run_tm(abaaabbb).
Final Tape Contents are:
#xxxxxxxx#

Yes
?- run_tm(abaaab).

No
?- halt.
[~/8710][4:28pm]


(3) Improve the TM Simulator to enable step execution of the TM. A sample
    run in Prolog is given below:


[~/teaching/481/w98][4:28pm] pl
Welcome to SWI-Prolog (Version 3.2.9)
Copyright (c) 1993-1999 University of Amsterdam.  All rights reserved.

For help, use ?- help(Topic). or ?- apropos(Word).

?- ['tmstep.pro'].
tmstep.pro compiled, 0.00 sec, 4,040 bytes.

Yes
?- ['equal.tm'].
equal.tm compiled, 0.00 sec, 1,556 bytes.

Yes
?- run_tm(abab).
Tape: abab
      ^
|: 
Tape: #xbab
      ^
|: 
Tape: #xbab
       ^
|: 
Tape: #xbab
        ^
|: 
Tape: #xxab
       ^
|: 
Tape: #xxab
      ^
|: 
Tape: #xxab
       ^
|: 
Tape: #xxab
        ^
|: 
Tape: #xxab
         ^
|: 
Tape: #xxxb
        ^
|: 
Tape: #xxxb
       ^
|: 
Tape: #xxxb
      ^
|: 
Tape: #xxxb
       ^
|: 
Tape: #xxxb
        ^
|: 
Tape: #xxxb
         ^
|: 
Tape: #xxxb
          ^
|: 
Tape: #xxxx
         ^
|: 
Tape: #xxxx
        ^
|: 
Tape: #xxxx
       ^
|: 
Tape: #xxxx
      ^
|: 
Tape: #xxxx
       ^
|: 
Tape: #xxxx
        ^
|: 
Tape: #xxxx
         ^
|: 
Tape: #xxxx
          ^
|: 
Tape: #xxxx#
           ^
|: 
Tape: #xxxx#
          ^
|: 
Tape: #xxxx#
         ^
|: 
Tape: #xxxx#
        ^
|: 
Tape: #xxxx#
       ^
|: 
Tape: #xxxx#
      ^
|: 
Final Tape Contents are:
#xxxx#
Yes
?- run_tm(aba).
Tape: aba
      ^
|: 
Tape: #xba
      ^
|: 
Tape: #xba
       ^
|: 
Tape: #xba
        ^
|: 
Tape: #xxa
       ^
|: 
Tape: #xxa
      ^
|: 
Tape: #xxa
       ^
|: 
Tape: #xxa
        ^
|: 
Tape: #xxa
         ^
|: 
Tape: #xxx
        ^
|: 
Tape: #xxx
       ^
|: 
Tape: #xxx
      ^
|: 
Tape: #xxx
       ^
|: 
Tape: #xxx
        ^
|: 
Tape: #xxx
         ^
|: 

No
?- halt.
[~/8710]


4. Modify the tmstep program so that we can do spying on a given state.

Design a predicate, run_tm(Tape,P), which takes an additional 
parameter P: the state to spy on. The TM should execute in the same
was as in the stepping mode except that the TM should stop whenever the
state P is reached and display tape contents. Upon hitting ENTER, the
TM should continue executing and stop again at the given state, if it
is reached.

Call this file tmspy.pro