/* File: turing7.pl
   Author: Mihaela Malita
   Title: A Turing Machine for testing ZEROs
   Checks if there are just zeros on the tape
  
   Tape Alphabet={0,1,e} States={q0,q1,q2} Final=q1,q2 Start=q0 
   t((OldState,LetterRead),(NewState,Move)).
    Move is: <- (left) or -> (right). 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 [0, 1, 0, e]  Output tape is [e, $, 1, 1, e]
    Head is on first 0  
            ?- start.
            Turing Machine for checking if ALL ZERO 
            String in binary: [1,1,0].
                             q0-[]-[1, 1, 0, e]
            tm-q0-1-q1-1     q1-[]-[1, 1, 0, e]
            NO
            Continue(y/n)?= y.
            Turing Machine for checking if ALL ZERO 
            String in binary: [0,0,0,0].
                                 q0-[]-[0, 0, 0, 0, e]
            tm-q0-0-q0- (->)     q0-[0]-[0, 0, 0, e]
            tm-q0-0-q0- (->)     q0-[0, 0]-[0, 0, e]
            tm-q0-0-q0- (->)     q0-[0, 0, 0]-[0, e]
            tm-q0-0-q0- (->)     q0-[0, 0, 0, 0]-[e]
            tm-q0-e-q2-e         q2-[0, 0, 0, 0]-[e]
            YES
            Continue(y/n)?= y.
            Turing Machine for checking if ALL ZERO 
            String in binary: [0].
                                q0-[]-[0, e]
            tm-q0-0-q0- (->)    q0-[0]-[e]
            tm-q0-e-q2-e        q2-[0]-[e]
            YES
            Continue(y/n)?= n.
***********************************************************************/     
start(q0).
final(q2). % YES just 0's on the tape

% find right end
tm((q0,0),(q0,->)).
tm((q0,1),(q1,1)).   % found 1 final state
tm((q0,e),(q2,e)).   % found final

start:- write('Turing Machine for checking if ALL ZERO \n'),
                    write('String in binary: '),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.

% The Turing machine halts when final state
        compute(Q,_,_):- final(Q).   
                
% 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((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).