% Turing Machine Definition 4.1.3 from "Elements of the Theory of Computation"
% December 4, 1992
% Rev 1.01      
% Written by James A. Canavan using Arity PROLOG 6.0

last( Item, [Item] ).           % Page 571
last( Item, [First | Rest] ) :- 
        last( Item, Rest).
member( X, [X | Tail]).
member( X, [Head | Tail]):-     
        member(X, Tail).
conc( [], L, L).
conc( [X | L1], L2, [ X | L3] ):-
        conc( L1, L2, L3).

ding_dong :- write(' Hang State !!! '),
             put(7).

% Machine One
k(1,[q0,q1]).                   % k = set of states, Mid = machine id
                                % q1 is a state
sigma(1,[a,#]).                         % sigma = alphabet, Mid = machine id
                                % [a,#] are members of alphabet
delta(1,        q0,[a],q1,[#] ).                % delta is function
delta(1,        q0,[#],[h], [#] ).
delta(1,        q1,[a],q0,[a] ).
delta(1,        q1,[#],q0,[$_R$]).

initial(1,q0).                          % i = initial state, Mid = machine id

config(1,q0,[e],[a],[a,a,a,#]).                 % here is a sample input configuration
                                        % for machine 1
% End of Machine One

% Machine Two
delta( 2, q0, [a], q0, [$_L$] ).
delta( 2, q0, [#], [h], [#]   ).

config(2,q0, [#,a,a], [a], [a,#] ).
% End of Machine Two

% machine with id number Mid, with sets k, sigma, delta, and initial state.
machine(Mid,k(Mid,Kset), sigma(Mid,Sset), delta(Mid,Dset), initial(Mid,Iset)).

machine(3, k(3,[q0,q2]), sigma(3,[a,b,#]),  delta(3,[[q0,[a],q1,[$_L$] ],
                                                    [q0,[b],q1,[$_L$] ],
                                                    [q0,[#],q1,[$_L$] ],
                                                    [q1,[a],q0,[b] ],
                                                    [q1,[b],q0,[a] ],
                                                    [q1,[#],q2,[$_R$] ],
                                                    [q2,[a],q2,[$_R$] ],
                                                    [q2,[b],q2,[$_R$] ],
                                                    [q2,[#],h ,[ # ]  ] ] ), initial(3, q0) ).

% YIELDS IN ONE STEP - Definition 4.1.3 on page 173
case1(Out) :-  Out \== [$_L$], Out \== [$_R$].

case_one(Id,Q2,W1,Out,U1):-
        ifthen(Out == [h], !),
        %write(Out),nl,
        y_i_o_s( Id, Q2,W1,Out,U1),!. 

case2(Out) :- Out == [$_L$].

case_two(Id, Q1, [Head | Tail], A1, U1 ) :-
        delta( Id, Q1, A1, Q3, Oldout),
        conc( A1, U1, U2),
        [Head2 | Tail2] = [ Head | Tail],
        last( Ahold , [Head | Tail]),
        conc( W2, [_], [Head2 | Tail2] ),              % from pg 571
        A2 = [Ahold],
        delta(Id, Q3, A2, Q4, Out),
        y_i_o_s( Id, Q4, W2, A2, U2),!.         

case3(Out) :- Out == [$_R$].       
case_three( Id, Q1, W1, A1, [Head | Tail] ) :-
        ifthen(A1 == [h], !),
        delta( Id, Q1, A1, Q3, OldOut),
        U2 = Tail,
        A2 = [Head], 
        conc( W1, A1, W2 ),
        delta(Id, Q3, A2, Q4,Out),
        y_i_o_s(Id, Q4, W2, A2, U2),!.

% Yield of One Step y_i_o_s( Id, _,  _, [h] , _),!.     
y_i_o_s( Id, Q1, W1, A1, U1) :-
        ifthen(Q1 == [h], ding_dong),
        write(' '),write(Q1),write(' '),write(W1),write(' '), write(A1), write(' '),
        write(U1),write(' --->'),nl,
        delta(Id, Q1, A1, Q2, Out),
        case( [ case1(Out) -> case_one(Id, Q2,W1,Out,U1),
                case2(Out) -> case_two(  Id, Q1, W1, A1, U1),
                case3(Out) -> case_three(Id, Q1, W1, A1, U1)  ]).
        
% End of yield in one Step !