CSc 8710 - DDLP - Fall 2010
Homework 4 - Due October 24 (Sunday), 2010
TM Simulator extensions: step and spy modes
-------------------------------------------

(1) Consider the TM Simulator code given below.

run_tm(L) :- start_state(S), atom_chars(L,[X|R]), go(S,[],X,R).

go(h,L,X,R) :- 
  append(L,[X],L1), append(L1,R,T), atom_chars(A,T),
  write('Final Tape Contents are:'), nl, write(A).

go(P,L,X,[])    :- delta(P,Q,X,Y,r), append(L,[Y],NewL), go(Q,NewL,#,[]).
go(P,L,X,[W|R]) :- delta(P,Q,X,Y,r), append(L,[Y],NewL), go(Q,NewL,W,R).
go(P,[],X,R)    :- delta(P,Q,X,Y,l), go(Q,[],#,[Y|R]).
go(P,[W|L],X,R) :- delta(P,Q,X,Y,l), 
                   reverse([W|L],[Z|L1]), reverse(L1,L2), go(Q,L2,Z,[Y|R]).

Extend this program in two different ways to provide TM debug capabilities.

STEP MODE: In this version, the run_tm predicate should simulate the given TM 
step by step and display the tape contents after each step; Also, the program 
should wait for user to press the ENTER key to execute the next step. Here is a
sample interaction:

2 ?- run_tm(abba).
Tape: abba  1
      ^
Tape: #xbba  2
      ^
Tape: #xbba  3
       ^

...
...
Tape: #xxxx#  5
       ^
Tape: #xxxx#  5
      ^
Final Tape Contents are:
#xxxx#
true .


SPY MODE: In this extension, the run_tm predicate takes an additional
parameter, state name to spy on: run_tm(Tape,P). The TM should execute 
in the same way 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. Here is a sample interaction:

2 ?- run_tm(abba,1).
Tape: abba
      ^
Tape: #xxba
       ^
Tape: #xxba
        ^
Tape: #xxba
         ^
Tape: #xxba
          ^
Tape: #xxxx
       ^
Tape: #xxxx
        ^
Tape: #xxxx
         ^
Tape: #xxxx
          ^
Tape: #xxxx#
           ^
Final Tape Contents are:
#xxxx#
true .