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