/* File: turing10.pl NOT FINISHED
   Author: Mihaela Malita
   Title: Turing Machine for COPY (DUPLICATE). Input= e w e;  Output= e w e w e
   Method: 
   read first leftmost and delete it 
   copy it on second blank right
   go back left to second blank (skip in between blank) and write the symbol you deleted
   go right next symbol 
   if it is blank then HALT (it is the in between blank)
   if not go to beginning.
   Tape Alphabet={a,b,e} States={q0-q8,q10,q20,q30,q40,q50,q60} Final=q8 Start=q0  e= blank 
   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
            2 ?- start.
            Turing Machine for COPY (DUPLICATE) a string
            String to duplicate: [b,a].
                                q0-[e]-[b, a, e, e, e, e]
            tm-q0-b-q10-e       q10-[e]-[e, a, e, e, e, e]
            tm-q10-e-q20- (->)  q20-[e, e]-[a, e, e, e, e]
            tm-q20-a-q20- (->)  q20-[e, e, a]-[e, e, e, e]
            tm-q20-e-q30- (->)  q30-[e, e, a, e]-[e, e, e]
            tm-q30-e-q40-b      q40-[e, e, a, e]-[b, e, e]
            tm-q40-b-q40- <-    q40-[e, e, a]-[e, b, e, e]
            tm-q40-e-q50- <-    q50-[e, e]-[a, e, b, e, e]
            tm-q50-a-q50- <-    q50-[e]-[e, a, e, b, e, e]
            tm-q50-e-q60-b      q60-[e]-[b, a, e, b, e, e]
            tm-q60-b-q7- (->)   q7-[e, b]-[a, e, b, e, e]
            tm-q7-a-q0-a        q0-[e, b]-[a, e, b, e, e]
            tm-q0-a-q1-e        q1-[e, b]-[e, e, b, e, e]
            tm-q1-e-q2- (->)    q2-[e, b, e]-[e, b, e, e]
            tm-q2-e-q3- (->)    q3-[e, b, e, e]-[b, e, e]
            tm-q3-b-q3- (->)    q3-[e, b, e, e, b]-[e, e]
            tm-q3-e-q4-a        q4-[e, b, e, e, b]-[a, e]
            tm-q4-a-q4- <-      q4-[e, b, e, e]-[b, a, e]
            tm-q4-b-q4- <-      q4-[e, b, e]-[e, b, a, e]
            tm-q4-e-q5- <-      q5-[e, b]-[e, e, b, a, e]
            tm-q5-e-q6-a        q6-[e, b]-[a, e, b, a, e]
            tm-q6-a-q7- (->)    q7-[e, b, a]-[e, b, a, e]
            tm-q7-e-q8-e        q8-[e, b, a]-[e, b, a, e]
            YES
            Continue(y/n)?= n.       
***********************************************************************/     
start(q0). final(q8). % start and final states 

tm((q0,a),(q1,e)).    % start with first 'a' and delete it
tm((q0,b),(q10,e)).    %%%  start with first 'b' and delete it

tm((q1,e),(q2,->)).     % go right to find first e (memorize a)
tm((q10,e),(q20,->)).   % go right to find first e (memorize b)
tm((q2,a),(q2,->)).     % go right to find first e (memorize a)
tm((q2,b),(q2,->)).     %%% go right to find first e (memorize a)
tm((q20,b),(q20,->)).   %%% go right to find first e (memorize b)
tm((q20,a),(q20,->)).   %%% go right to find first e (memorize b)
tm((q2,e),(q3,->)).     % (in between e) is found (memorize a)
tm((q20,e),(q30,->)).   %%% (in between e) is found (memorize b)
 
tm((q30,a),(q30,->)).   %%% go till next e (memorize b)
tm((q30,b),(q30,->)).   %%% go till next e (memorize b)
tm((q3,a),(q3,->)).     % go till next e (memorize a)
tm((q3,b),(q3,->)).     %%% go till next e (memorize a)

tm((q3,e),(q4,a)).      % overright 'a'
tm((q30,e),(q40,b)).    %%% overright 'b'

tm((q4,a),(q4,<-)).     % find leftmost blank (memorize a)
tm((q4,b),(q4,<-)).     %%% find leftmost blank (memorize a)
tm((q40,a),(q40,<-)).   % find leftmost blank (memorize b)
tm((q40,b),(q40,<-)).   %%% find leftmost blank (memorize b)

tm((q4,e),(q5,<-)).     % skip in between blank
tm((q40,e),(q50,<-)).   %%% skip in between blank

tm((q5,a),(q5,<-)).     % find leftmost  to put 'a' back
tm((q5,b),(q5,<-)).     %%% find leftmost  to put 'a' back
tm((q50,a),(q50,<-)).   %%% find leftmost  to put 'b' back
tm((q50,b),(q50,<-)).   %%% find leftmost  to put 'b' back

tm((q5,e),(q6,a)).      %  put 'a' back
tm((q50,e),(q60,b)).    %%%  put 'b' back

tm((q6,a),(q7,->)).     % go to next character to copy
tm((q60,b),(q7,->)).    %%% go to next character to copy

tm((q7,e),(q8,e)).      % if next char is in_between e then HALT
tm((q7,a),(q0,a)).      % if next char is 'a', start all over
tm((q7,b),(q0,b)).      %%% if next char is 'b', start all over

start:- write('Turing Machine for COPY (DUPLICATE) a string\n'),
    write('String to duplicate: '),read(W),
    Left=[e],append(W,[e,e,e,e],Right),start(S), % put as many e's as |w| 
    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.

% Turing Machine halts when in final state
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)),
                    not(member(B, [->,<-])),NewRight=[B|T],
    write(tm-State-A-NewState-B),tab(5),write(NewState-Left-NewRight),nl,
                    compute(NewState,Left,NewRight).