
/* Adapted from Crookes, D., "USING PROLOG TO PRESENT ABSTRACT MACHINES"
   ACM SIGCSE Bulletin, Vol. 20 No. 3, Sept. 1988 */


% A Turing machine is represented by a predicate
%
%   tm(initial_state, initial_tape, final_tape)

% An entr in the transition table is represented by a predicate
%
%   quintuple(current_state, input_symbol, output_symbol, new_state,
%       head_movement)
%
% (It is assumed that output_symbol replaces input_symbol
% in the current cell of the tape)

% An action on the tape is represented by a predicate
%
%   move(tape_before, direction, tape_after)

% An event in the life of the Turing machine (i.e. one episode in the
% history of a particular computation) is represented by a predicate
%
%   event(current_state, current_tape, new_state, new_tape)

% The tape is represented as a (potentially infinite) sequence of cells
% by a function
%
%   tape(left_part, current_cell, right_part) 

% States are represented by symbols, depending on the specific program 
% (e.g. even, odd).
% The special symbol halt represents the halting state

% Directions are represented by special symbols (i.e. ->, -, <-)


/* Turing machine definition */

tm(halt, T, T).
tm(Q, T, T1) :-
    event(Q, T, Q1, T2),
    tm(Q1, T2, T1).
    
event(Q, tape(L, C, R), Q1, T) :-
    quintuple(Q, C, S, Q1, D),
    move(tape(L, S, R), D, T).

move(T, -, T).
move(tape(L,C,[X|R]), ->,  tape([C|L],X,R)).
move(tape(L,C,R), <-, tape(L1,X1,R1)) :-
    move(tape(R1,X1,L1), ->, tape(R,C,L)).

% Add blank cells when required 
move(tape(L,C,[]), ->,  tape([C|L],b,[])).


/* Example program (as FSA): a parity checker */

quintuple(even, 0, 0, even, ->).
quintuple(even, 1, 1, odd, ->).
quintuple(odd, 0, 0, odd, ->).
quintuple(odd, 1, 1, even, ->).
quintuple(even, b, even, halt, -).
quintuple(odd, b, odd, halt, -).


% Run an example as:
% ?- tm(even, tape([], 1, [0,1,1,0]), T).
