%------------------------------------------------------------------------------
% TM Interpreter.
%
%   TM input is a list of symbols.
%   TM Program is a set of facts of the form:
%   	deltaT(state,input symbol,new state)
%   The state of the computation is represented by
%   the relation
%	accepT(Q,Prefix, Suffix)
%   where
%	-Q is the current state
%	-Prefix is the contents of the input tape before the current cell
%	-Rest is the rest of the input tape including the current input symbol
%		as its first element.
%------------------------------------------------------------------------------

:- ensure_loaded('utilities').



%--------------------
% Start the Machine
%--------------------
acceptT(Input_Tape) :-
       initial(Q),
		    writeseqnl([Input_Tape,'---> Initial Tape']),
       acceptT(Q,[],Input_Tape).

%--------------------
%Move Right on Input
%--------------------
acceptT(Q,Prefix,[Input | Rest])  :-
       	deltaT(Q,Input,Q1,right),
	
	writeseqnl([Prefix,'>',Input,'<',Rest,'--->',Q,'To',Q1,' Move Rt']),
       
	append(Prefix,[Input],NewPrefix),
	acceptT(Q1,NewPrefix,Rest).

%--------------------
%Move Left on Input
%--------------------
acceptT(Q,Prefix,[Input | Rest]) :-
	deltaT(Q,Input,Q1,left),
	
	writeseqnl([Prefix,'>',Input,'<',Rest,'--->',Q,'To',Q1,' Move Lt']),
       
	append(NewPrefix,[Last],Prefix),
	acceptT(Q1,NewPrefix, [Last,Input | Rest]).

%--------------------
%Write a new symbol
%%--------------------
acceptT(Q,Prefix,[Input | Rest]) :-
      	deltaT(Q,Input,Q1,New),
      	
	not(=(New,left)), 
      	not(=(New,right)),
      	
	writeseqnl([Prefix,'>',Input,'<',Rest,'--->',Q,'To',Q1,' Write:',New]),
      
	acceptT(Q1,Prefix,[New | Rest]).

%--------------------
%Halt the machine
%--------------------
acceptT(Q,Prefix,[Input | Rest]) :-
         final(Q),
         writeseqnl([Prefix,'>',Input,'<',Rest,'--->','Final Tape']).




%-----------------------------
%Declare the final 
% & initial states for the TM
%-----------------------------
final(halt).
initial(q0).


%--------------------------------
% TM program to add 1
%
%--------------------------------
%  deltaT(q0,1,q0,right).
%  deltaT(q0,#,q1,1).
%  deltaT(q1,1,halt,right).


%-------------------------------------------------------
% TM program to subtract two numbers separated by a blank

%   Example: acceptT([1,1,1,1,#,1,1,1,end]). is 4 - 3
%            Result Tape = [1,#,#,#,#,#,#,end].
%
%-------------------------------------------------------

% q0: Scan to end of first Number
     deltaT(q0,1,q0,right).
     deltaT(q0,#,q1,right).

% q1: scan to end of middle blanks or end of computation
     deltaT(q1,#,q1,right).
     deltaT(q1,end,halt,end).  % Hit end Smaller number is consumed

% q1: At beginning of smaller number go into q2.
      deltaT(q1,1,q2,right).

% q2: Scan to end of smaller number go into q3.
      deltaT(q2,1,q2,right).
      deltaT(q2,#,q3,left).         %Found end of smaller number
      deltaT(q2,end,q3,left).	    %Or end of tape.	

% q3: Erase trailing 1 from smaller number  
      deltaT(q3,1,q3,#).
      deltaT(q3,#,q4,left).

% q4: Scan back across remainder of second number
      deltaT(q4,1,q4,left).
      deltaT(q4,#,q5,left).


% q5: Scan thru middle blanks subtract one from tail of first number
%     go back into state q1 and look for more in second number.
%
     deltaT(q5,#,q5,left).   
     deltaT(q5,1,q1,#).