/******************************************************************
Prolog-Programm zur Simulation der Turingmaschine

SaRq
SbRq
ScRq
S#Rq
qaRq
qbRq
qcRq
q##H

bei der Startkonfiguration

##acbac##
   S

Wir stellen in Prolog die Konfiguration als Wort, hier "##aScbac##" dar
(Zustand wird vor das Arbeitsfeld geschrieben).
******************************************************************/

% Interpretiere ein Wort in Double Quotes als Liste von Characters:
:- set_prolog_flag(double_quotes,chars).

:- initialization(start).          %Beim Programmstart

% Wir deklarieren das 2-stellige Praedikat => als Infix-Operator
:- op(800,xfx,=>).

% Simuliere die Turingmaschine durch das Semi-Thue-System
"Sa" => "aq".
"Sb" => "bq".
"Sc" => "cq".
"S#" => "#q".
"qa" => "aq".
"qb" => "bq".
"qc" => "cq".
"q#" => "H#".

% Die Zeichen des Bandalphabets der Turingmaschine:
zeichen('a').
zeichen('b').
zeichen('c').
zeichen('#').

% Die Zustaende der Turingmaschine:
zustand('S').
zustand('q').
zustand('H').


% konk([L1,...,Ln],K)  K ist Konkatenation der Listen L1,...,Ln.
konk([],[]).
konk([[]|Ls],K) :-
  konk(Ls,K).
konk([[X|L]|Ls],[X|K]) :-
  konk([L|Ls],K).

% Berechnungsschritt fuehrt von Konfiguration_alt zu Konfiguration_neu
schritt(Konfiguration_alt,Konfiguration_neu) :-
  konk([U,X,V],Konfiguration_alt),
  X => Y,
  konk([U,Y,V],Konfiguration_neu).



% Das Hauptpraedikat des Programms
start :-
  starte_mit_Konfiguration("##aScbac##").
start.                   %Wenn kein Schritt mehr moeglich, halte mit Erfolg

% starte_mit_Konfiguration(+Konfiguration)
% Starte die Turingmaschine mit Konfiguration.
% Schlaegt fehl, wenn kein Schritt mehr moeglich.
starte_mit_Konfiguration(Konfiguration) :-
  gib_Konfiguration_aus(Konfiguration),
  schritt(Konfiguration,Konfiguration_neu),
  starte_mit_Konfiguration(Konfiguration_neu).

gib_Konfiguration_aus(Konfiguration) :-
  gib_Bandinhalt_aus(Konfiguration),
  gib_Zustand_aus(Konfiguration).

% gib_Bandinhalt_aus(+Konfiguration)
gib_Bandinhalt_aus([]) :-
  nl.
gib_Bandinhalt_aus([Zeichen|Rest]) :-   %Wenn die Konfiguration mit einem
  zeichen(Zeichen),                     %Zeichen des Bandalphabets beginnt,
  put_char(Zeichen),                    %gib dieses Zeichen und den
  gib_Bandinhalt_aus(Rest).             %Rest des Bandinhalts aus.
gib_Bandinhalt_aus([Zustand|Rest]) :-   %Wenn Konfiguration
  zustand(Zustand),                     %mit einem Zustand beginnt,
  gib_Bandinhalt_aus(Rest).             %gib Rest des Bandinhalts aus.

% gib_Zustand_aus(+Konfiguration)
gib_Zustand_aus([Zeichen|Rest]) :-      %Wenn die Konfiguration mit einem
  zeichen(Zeichen),                     %Zeichen des Bandalphabets beginnt,
  put_char(' '),                        %ruecke Zustand um 1 mehr ein als
  gib_Zustand_aus(Rest).                %beim Rest der Konfiguration.
gib_Zustand_aus([Zustand|_Rest]) :-     %Wenn die Konfiguration
  zustand(Zustand),                     %mit einem Zustand beginnt,
  put_char(Zustand),                    %gib diesen Zustand
  nl,                                   %und zwei Zeilenschaltungen aus.
  nl.

% Bemerkungen:
% 1. In dieser Turingmaschine kommt kein Elementarbefehl L vor.
% Bei der Simulation durch ein Semi-Thue-System wuerde eine
% Programmzeile mit einem Elementarbefehl L uebersetzt in mehrere
% Regeln des Semi-Thue-Systems.
% 2. Im Allgemeinen muss man zur Simulation von Turingmaschinen
% durch Semi-Thue-Systeme auch den Fall betrachten, dass der Schreib-
% Lese-Kopf an den Rand des durch das Wort beschriebenen Teils des
% Bandes stoesst. Dazu ist noetig, zusaetzlich zwei Zeichen als
% linken und rechten Begrenzer einzusetzen, etwa [ und ]. Die Regeln
% des Semi-Thue-Systems sind dann um Regeln fuer den Fall des
% Erreichens eines der Begrenzer zu erweitern.

% Das Beispiel hier wurde bewusst so gewaehlt, dass beide
% Komplikationen nicht auftreten, um es einfacher verstaendlich
% zu machen.
