/* File: turing0.pl           Author: Mihaela Malita
   Title: A Turing Machine that erases the input string
    tm((OldState,LetterRead),(NewState,Move)).
    Move is: <- (left) or -> (right). Move=e means it writes blank(e) that is: deletes.
    Head stays: if Move = Letter.Types of transitions are:
    t((s,a),(q,b)).   OldState=s reads an a; jumps to state q and overwrites b
    t((s,a),(q,->)).  OldState=s reads an a; jumps to state q and moves right
    t((s,a),(q,<-)).  OldState=s reads an a; jumps to state q and moves left
    Input tape is [a,a,a,e]  Head is on first a
    At first blank (e) we assume the string finishes. No blanks in the data on the input tape 
        Example:    ?- start.
                    Turing Machine that erases the input string
                    String to compute: [a,a,a].
                                    s-[]-[a, a, a, e]
                    tm-s-a-q-e      q-[]-[e, a, a, e]
                    tm-q-e-s- (->)  s-[e]-[a, a, e]
                    tm-s-a-q-e      q-[e]-[e, a, e]
                    tm-q-e-s- (->)  s-[e, e]-[a, e]
                    tm-s-a-q-e      q-[e, e]-[e, e]
                    tm-q-e-s- (->)  s-[e, e, e]-[e]
                    tm-s-e-h-e      h-[e, e, e]-[e]
                    YES
                    Continue(y/n)?= n.
***********************************************************************/
final(h).    % final state 
start(s).    % start state
tm((s,e),(h,e)).          %1   JUMP to NewState if reads BLANK, head does not move
tm((s,a),(q,e)).          %2   DELETE a (write BLANK instead)
tm((q,e),(s,->)).         %3   If read=BLANK change state and MOVE RIGHT
start:- write('Turing Machine that erases the input string\n'),
        write('String to compute: '),read(W),
        Left=[],append(W,[e],Right),start(S),tab(15),write(S-Left-Right),nl,
        (compute(S,Left,Right)->write('YES');write('NO')),(yesorno -> start).
yesorno:- nl,write('Continue(y/n)?= '),read(R),R=y.
% configuration: State-WordLeft-WordRight, WordRight=[$,Read,...,e]
compute(Q,_,_):- final(Q).   % halt when final state
                
% tm((q,A),(s,->)).       Move to next symbol on the tape and go to new state                      
compute(State,Left,Right):- Right=[A|T],tm((State,A),(NewState,->)),
                            append(Left,[A],NewLeft),NewRight=T,
    write(tm-State-A-NewState-(->)),tab(5),write(NewState-NewLeft-NewRight),nl,
                            compute(NewState,NewLeft,NewRight).    
                                                    
% tm((q,A),(s,<-)).       Move to previous symbol on the tape and go to new state                      
compute(State,Left,Right):- Right=[A|T],tm((State,A),(NewState,<-)),
                            append(Newleft,[X],Left),NewRight=[X,A|T],
    write(tm-State-A-NewState-(<-)),tab(5),write(NewState-NewLeft-NewRight),nl,
                            compute(NewState,NewLeft,NewRIGHT).    

% tm((s,a),(q,b)).       If a is read then overwrite b, go to Newstate                      
compute(State,Left,Right):- Right=[A|T],tm((State,A),(NewState,B)),NewRight=[B|T],
    write(tm-State-A-NewState-B),tab(5),write(NewState-Left-NewRight),nl,
                            compute(NewState,Left,NewRight).