Turingmaschinensimulator -- Bienenvariante

Dateiinhalt

%% Version:  1.0  -  Datum: 1. Juni 2007  -  Datei: tm_biene.pl
%%
%% Theoretische Informatik II - Sommersemester 2007
%%
%% Hausaufgabe 7.5 (Fleissige Biene) - Abgabetermin: 18.06.2007, 10 Uhr
%%
%% Name 1:                         Matrikelnummer:
%% Name 2:                         Matrikelnummer:
%% Name 3:                         Matrikelnummer:
%% Name 4:                         Matrikelnummer:
%%
%% Aufgabe: Konstruieren Sie eine "Fleissige Biene" Turingmaschine mit
%%          zwei und vier Zustaenden, die eine moeglichst grosse Produk-
%%          tivitaet hat. Der Endzustand wird nicht mitgezaehlt. Das
%%          Bandalphabet enthaelt nur die Symbole B (das Leerzeichen)
%%          und * (eine Blume).
%%
%%          Die Produktivitaet Ihrer Turingmaschine, angesetzt auf das
%%          leere Band, ist der groesste Abstand zwischen zwei Blumen *
%%          der Ausgabe, inklusive dieser Blumen. Sie ist 0, falls die
%%          Turingmaschine nicht anhaelt. So ist, zum Beispiel, die Pro-
%%          duktivitaet der Turingmaschine, die *B**B*BB* auf das Band
%%          schreibt, gleich 9. Als Nebenbedingung darf Ihre Turingma-
%%          schine nicht gleichzeitig eine "Busy Beaver" Turingmaschine
%%          sein, d.h. die Ausgabe Ihrer Turingmaschine mit zwei bzw.
%%          vier Zustaenden darf keine 4 bzw. 13 Blumen enthalten.
%%
%%          Die Uebergangsfunktion Ihrer fleissigen Biene wird unten
%%          definiert (siehe Beispiel). Sie koennen Ihre Turingmaschine
%%          testen, indem Sie "tm([],q0,[!])." aufrufen. Sie stoppen die
%%          Turingmaschine (sofern notwendig) mit "Ctrl-C". Das Ausrufe-
%%          zeichen stellt das Leerzeichen dar. Sie koennen auch andere
%%          Namen fuer Zustaende oder Symbole des Bandalphabets waehlen,
%%          jedoch *muss* das erste Zeichen ein Kleinbuchstabe sein.
%%
%% Nuetzliche Prolog-Kommandos
%%    [<programm>].   laedt die Datei <programm>.pl
%%    make.           laedt das Programm erneut, wenn es geandert wurde
%%    halt.           beendet das Prolog System
%%
%% Abgabe:  Senden Sie dieses gesamte Programm mit Ihren "lauffaehigen"
%%          Uebergangsfunktionen bis zum Abgabetermin an die folgende
%%          Email-Adresse: fleissige.biene@cs.uni-potsdam.de.
%%          Geben Sie im Betreff der email einen Nachnamen *und* die
%%          Nummer Ihrer Uebungsgruppe an, also etwa "Mustermann, 4".

%% Die Uebergangsfunktion delta(q,X):=(q',X',D) wird in der folgenden
%% Form definiert "delta(q,X,q',X',D).", wobei D entweder 'l' or 'r' ist

% TM 1 - Fleissige Biene mit zwei Zustaenden
%
% Hier steht die von Ihnen definierte Uebergangsfunktion
% (auskommentieren, falls Sie TM 2, siehe unten, testen)

delta(q0,!, q1,*,l). delta(q0,*, qe,*,r).
delta(q1,!, q0,*,r). delta(q1,*, q1,*,l).

% TM 2 - Fleissige Biene mit vier Zustaenden
%
% Hier steht die von Ihnen definierte Uebergangsfunktion
% (auskommentieren, falls Sie TM 1, siehe oben, testen)

% delta(q0,!,  , , ). delta(q0,*,  , , ).
% delta(q1,!,  , , ). delta(q1,*,  , , ).
% delta(q2,!,  , , ). delta(q2,*,  , , ).
% delta(q3,!,  , , ). delta(q3,*,  , , ).

%% Die (optionale!) Menge der akzeptierenden Zustaende {q1,...qN} wird
%% in der folgenden Form definiert "accept([q1,...,qN])."

accept([qe]). % Endzustand

%% Das folgende Programm ist der Turingmaschinen-Simulator. Aendern Sie
%% nichts unterhalb dieser Zeile, es sei denn, Sie wissen was Sie tun!
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
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).