/* File: turing5.pl
   Author: Mihaela Malita
   Title: A Turing Machine that INCREMENTs a binary number
   Tape Alphabet={0,1,e} States={q0,q1,2,q3,q4,q5,q6,q7} Final=q1 Start=q0 
    Types of transitions, t((OldState,LetterRead),(NewState,Move)) 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 [e, 1, 0, e]  Output tape is [e, 1, 1, e]
    Head is on leftmost non-blank.  Configuration: State-TapeLeft-TapeRight
                Example:    ?- start.
            Turing Machine for adding 1 to a binary integer 
            Number in binary: [1,1,1].
                                q0-[e]-[1, 1, 1, e]
            tm-q0-1-q0- (->)    q0-[e, 1]-[1, 1, e]
            tm-q0-1-q0- (->)    q0-[e, 1, 1]-[1, e]
            tm-q0-1-q0- (->)    q0-[e, 1, 1, 1]-[e]
            tm-q0-e-q2- <-      q2-[e, 1, 1]-[1, e]
            tm-q2-1-q3-0        q3-[e, 1, 1]-[0, e]
            tm-q3-0-q4- <-      q4-[e, 1]-[1, 0, e]
            tm-q4-1-q5-0        q5-[e, 1]-[0, 0, e]
            tm-q5-0-q4- <-      q4-[e]-[1, 0, 0, e]
            tm-q4-1-q5-0        q5-[e]-[0, 0, 0, e]
            tm-q5-0-q4- <-      q4-[]-[e, 0, 0, 0, e]
            tm-q4-e-q6-1        q6-[]-[1, 0, 0, 0, e]
            NO
            Continue(y/n)?= y.
            Turing Machine for adding 1 to a binary integer 
            Number in binary: [1,0,1].
                                q0-[e]-[1, 0, 1, e]
            tm-q0-1-q0- (->)    q0-[e, 1]-[0, 1, e]
            tm-q0-0-q0- (->)    q0-[e, 1, 0]-[1, e]
            tm-q0-1-q0- (->)    q0-[e, 1, 0, 1]-[e]
            tm-q0-e-q2- <-      q2-[e, 1, 0]-[1, e]
            tm-q2-1-q3-0        q3-[e, 1, 0]-[0, e]
            tm-q3-0-q4- <-      q4-[e, 1]-[0, 0, e]
            tm-q4-0-q1-1        q1-[e, 1]-[1, 0, e]
            YES
            Continue(y/n)?= n.  
***********************************************************************/     
start(q0).
final(q1).

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

tm((q2,0),(q1,1)).     % if last digit is 0 write 1 and HALT

tm((q2,1),(q3,0)).     % last digit is 1, overwrite 0
tm((q3,0),(q4,<-)).    % find first 0 right and transform it to 1

tm((q4,1),(q5,0)).     % transform 1 to 0 and go left
tm((q5,0),(q4,<-)).    % and go left
tm((q4,0),(q1,1)).     % found a 0 write 1 and halt

tm((q4,e),(q6,1)).     % found just 1's we have to insert 1 (111+1=1000)
tm((q6,1),(q7,<-)).
tm((q7,e),(q1,1)).      

start:- write('Turing Machine for adding 1 to a binary integer \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.

% 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).