Turingmaschinen-Simulator leanTM

Dateiinhalt

%% 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);
%%          % press Ctrl-C to stop TM; 'halt.' exits Prolog
%%
%% 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; q,q',X, and X' have to begin
%% with a SMALL LETTER or a NUMBER; the default blank symbol is '!'

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


% TM 1: tests if number of '1's 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).
%accept([q_2]).

% TM 2: doubles the number of '1's
% 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).
%accept([]).

% 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).
accept([]).

% TM 4 (NTM): tests if word contains the string aaa
%delta(q_0,a, q_0,a,r). delta(q_0,a, q_1,a,r). delta(q_0,b, q_0,b,r).
%delta(q_1,a, q_2,a,r). delta(q_2,a, q_3,a,r).
%delta(q_3,a, q_3,a,r). delta(q_3,b, q_3,b,r).
%accept([q_3]).


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