/* File: turing6.pl
   Author: Mihaela Malita
   Title: A Turing Machine that DECREMENTS a binary number
    Tape Alphabet={0,1,e} States={q0,q1,2,q3,q4,q5,q6,q7} Start=q0 Final=q7 
    Transitions: 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, writes b over a
    t((s,a),(q,->)).  OldState=s, reads an a, jumps to state q, moves right
    t((s,a),(q,<-)).  OldState=s, reads an a, jumps to state q, moves left
    Input tape is [e, 1, 0, 0, e]  Output tape is [e, 1, 1, e]
    Head is on first 1 (the leftmost non-blank)
    Example:   
***********************************************************************/     
start(q0).
final(q7).

tm((q0,0),(q0,->)).     % find right end
tm((q0,1),(q0,->)).
tm((q0,e),(q1,<-)).     % found rightmost digit

tm((q1,1),(q8,0)).      % if rightmost digit is 1 write 0 and HALT

tm((q1,0),(q2,1)).      % if rightmost digit is 0 write 1 and go left
tm((q2,1),(q3,<-)).    

tm((q3,0),(q4,1)).      % till first 1 is found write 1 instead of 0
tm((q4,1),(q3,<-)).

tm((q3,1),(q5,<-)).    % first 1 found must make it 0 if it is not the first digit
tm((q5,e),(q6,->)).    % check if first digit
tm((q6,1),(q7,e)).     % if first digit we have to delete it (case: 1000-1 =111)and HALT

tm((q5,1),(q7,1)).     % it was not the first digit. HALT
tm((q5,0),(q7,0)).
                        
start:- write('Turing Machine for DECREMENT a binary number\n'),
                    write('Number in binary: '),read(W),
                    Left=[e],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 NewState                      
        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 NewState                       
        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 with 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).