%% Version:  1.0  -  Date: 26 April 2007  -  File: leantm.pl
%%
%% Purpose: leanTM: A Turing Machine Simulator in Prolog
%%
%% Author:  Jens Otten
%%
%% Usage:   tm(A,Q,B).
%%          % where (A,Q,B) is a configuration, i.e. Q is a
%%          % (start) state and A,B are of the form [a,b,c,..]
%%          % defining the (initial) contents of the tape
%%          %
%%          % Example: [leantm].
%%          %          tm([],q_0,[1,1,1,1,1,1]).
%%          %
%%          % Loads leanTM and starts the TM defined below
%%          % on the input word 111111 and returns yes/no;
%%          % works for terminating nondeterministic TMs
%%          % as well (just define delta in the usual way)
%%
%% License: GPL

%% The transition function delta(q,X):=(q',X',D) is defined
%% in the form delta(q,X,q',X',D) with D either 'l' or 'r';
%% ONLY SMALL LETTERS or NUMBERS are allowed for q,q',X,X';
%% the default blank symbol is '!'

% TM 1: tests if number of '1' is even
delta(q_0,1, q_1,1,r). delta(q_0,!, q_2,!,r).
delta(q_1,1, q_0,1,r). delta(q_1,!, q_3,!,r).

% TM 2: doubles the number of '1'
% delta(q_0,1, q_0,1,r). delta(q_0,!, q_1,!,l).
% delta(q_1,1, q_2,!,r). delta(q_1,!, q_4,!,r).
% delta(q_2,1, q_2,1,r). delta(q_2,!, q_3,1,l).
% delta(q_3,1, q_3,1,l). delta(q_3,!, q_1,1,l).

% TM 3: adds 1 to binary presentation of a natural number
% delta(q_0,0, q_0,0,r). delta(q_0,1, q_0,1,r). delta(q_0,!, q_1,!,l).
% delta(q_1,0, q_2,1,l). delta(q_1,1, q_1,0,l). delta(q_1,!, q_2,1,l).
% delta(q_2,0, q_2,0,l). delta(q_2,1, q_2,1,l). delta(q_2,!, q_3,!,r).

%% The set of accepting states {q_1,...q_n} is defined
%% in the form accept([q_1,...,q_n]).

accept([q_2]). % only required for TM 1

%% Do not change anything below this line except you know
%% what you are actually doing ...
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
tm(A,Q,[X|B]) :-
  print(A), print(Q), print([X|B]), nl,
  delta(Q,X,Q1,X1,D),
  (D=l ->
    (A=[] -> tm([],Q1,[!,X1|B]) ; append(A1,[Y],A), tm(A1,Q1,[Y,X1|B]));
    append(A,[X1],A1), (B=[] -> tm(A1,Q1,[!]) ; tm(A1,Q1,B))
  ).
tm(_,Q,[X|_]) :- \+delta(Q,X,_,_,_), accept(F), member(Q,F).