\def\R{\mbox{\makebox[.2em][l]{I}R}} \def\N{\mbox{\makebox[.2em][l]{I}N}} \def\Z{\mbox{\makebox[.283em][l]{Z}Z}} \def\C{\makebox[.6em]{\makebox[-.18em]{C}\rule{.03em}{1.5ex}}} \def\Q{\makebox[.6em]{\makebox[-.25em]{Q}\rule{.03em}{1.5ex}}} \def\qed{\hfill $\Box$} \documentstyle[german]{article} \frenchspacing \setlength{\parindent}{0pt} \textheight=242mm \textwidth=160mm \topmargin=-10mm \headsep=17mm \oddsidemargin=+5mm \evensidemargin=+5mm \pagestyle{myheadings} \pagenumbering{arabic} \markboth{Die Unl”sbarkeit des Wortproblems fr Semi-Thue-Systeme und Thue-Systeme}{Die Unl”sbarkeit des Wortproblems fr Semi-Thue-Systeme und Thue-Systeme} \newcommand{\deflabel}[1]{\bf #1 \hfill}% \newenvironment{deflist}[1]% {\begin{list}{}% {\settowidth{\labelwidth}{\bf #1}% \setlength{\leftmargin}{\labelwidth}% \addtolength{\leftmargin}{\labelsep}% \renewcommand{\makelabel}{\deflabel}}}% {\end{list}}% \begin{document} \begin{center} \section*{Vortragsnotizen ``Das Wortproblem f"ur Semi-Thue-Systeme''} \subsection*{Seminar "uber mathematische Logik, 15.04.1992} Michael Meyling \end{center} \subsection*{Einleitung} Die Unl"osbarkeit des Halteproblems f"ur Turingmaschinen kann dazu benutzt werden, die Unentscheidbarkeit anderer, interessanterer Probleme zu beweisen. Dabei geht es stets um die Frage, ob ein Pr"adikat einer entscheidbaren Menge von Objekten entscheidbar ist. Man zeigt dazu, da"s die L"osung dieser Frage die L"osung des Halteproblems beinhalten w"urde. Die universelle Turingmaschine wird dann zur Konstruktion eines speziellen Objektes benutzt, von dem man nicht entscheiden kann, ob ihm das Pr"adikat zukommt oder nicht. Alle Beweise beruhen im Prinzip auf dem Diagonalverfahren. \subsection*{Historische Einbettung} Der Begriff des Algorithmus ist einer der grundlegenden Begriffe der Mathematik. Er ist intuitiv gegeben und gew"ohnlich versteht man darunter ein allgemeines Verfahren zur L"osung einer Klasse von Problemen. Dabei soll dieses Verfahren durch eine eindeutige Vorschrift so bis in alle Einzelheiten festgelgt sein, da"s f"ur seine Anwendung kein ``Geist'' erforderlich ist. Klassische Beispiele hierf"ur sind der Euklidische Algorithmus und das Gau"ssche Eliminationsverfahren. Schon von den Arabern sind, unter dem Einflu"s der Inder, Algorithmen zur Behandlung algebraischer Aufgaben entwickelt worden. Das Wort ``Algorithmus'' geht auf den Namen des arabischen Mathematikers Mohammed Ibn Musa Alchwarizmi (um 800) zur"uck, der durch sein (sp"ater als ``liber algorithmi'' zitiertes) Buch "uber die Behandlung algebraischer Gleichungen wesentlich zur Verbreitung der damals entstandenen Rechenmethoden beigetragen hat. Die von den Arabern eingef"uhrten mathematischen Methoden haben den Spanier Raymundus Lullus (ca. 1235-1315) angeregt zu seiner ber"uhmten ``Ars Magna'', die dem Wunsch nach einer schematischen Erzeugung aller wahren Aussagen entsprang. Obwohl die Ideen von Lullus von geringem mathematischem Wert sind, hatten sie einen gro"sen Einflu"s auf die Nachwelt: noch zweihundert Jahre sp"ater ver"offentlichte Cardano seine algebraischen Algorithmen als Teil der Ars Magna. Die Auffassung, das letzten Endes alle Fragestellungen der Mathematik, ja selbst der Philosophie einer algorithmischen L"osung zug"anglich seien, wurde von ber"uhmten Mathematikern geteilt. So seien hier Descartes, Leibniz und Hilbert als Repr"asentanten genannt. Descartes entwickelte die analytische Geometrie in der Absicht, die Geometrie algebraischen Rechenmethoden zug"anglich zu machen. Auch von Leibniz ist bekannt, da"s er sich sehr um die Entwicklung von Algorithmen bem"uht hat und da"s ihm eine allumfassende Methode, jedes Problem durch ``Rechnen'' zu l"osen, vorschwebte. Er betont, da"s er von Lullus beeinflu"st sei, jedoch entwickelte er pr"azisere Vorstellungen von diesem Begriff. Er unternahm wohl als erster den Versuch, f"ur diese Zwecke geeignete automatisch arbeitende Maschinen zu ersinnen, ohne allerdings zum Ziel zu gelangen. Zumindest war er einer der ersten, die eine Rechenmaschine gebaut haben. Bis in die neueste Zeit jedoch blieb der Begriff des Algorithmus ungenau: von gewissen Vorschriften wurde behauptet, sie seien Algorithmen zur L"osung bestimmter Probleme. Auch die Tatsache, da"s schon im vorigen Jahrhundert f"ur gewisse Probleme Unl"osbarkeitsbeweise gef"uhrt worden waren, z.B. f"ur Konstruktionen mit Zirkel und Lineal, Aufl"osbarkeit algebraischer Gleichungen mit Hilfe von Radikalen, beeinflu"ste die Mathematiker nicht in ihrem Glauben an die prinzipielle L"osbarkeit aller mathematischen Probleme, denn diese Beweise zeigten nur die Undurchf"uhrbarkeit einer gewissen Aufgabe mit bestimmten Hilfsmitteln (Zirkel und Lineal, Radikale), aber nicht die generelle Unl"osbarkeit. Bei den sp"ateren Unl"osbarkeitsbeweisen ist das etwas anderes. Denn, wie Emil Post es formulierte, sind diese Beweise zwar ebenfalls Beweise der Unl"osbarkeit einer Aufgabe mit gewissen Hilfsmitteln, jedoch scheint es hier so zu sein, da"s diese Hilfsmittel die einzigen sind, die dem Menschen zur L"osung dieser Aufgabe zur Verf"ugung stehen. Diese Beweise zeigen n"amlich, da"s es mathematische Probleme gibt, f"ur die es keinen Algorithmus zu ihrer L"osung geben kann. Der in einer solchen Aussage vorkommende Begriff des Algorithmus mu"s nat"urlich exakt definiert sein und man k"onnte leicht meinen, eine strenge mathematische Definition w"are vielleicht zu eng, den intuitiven Begriff des Algorithmus zu fassen, es hat sich jedoch erwiesen, da"s alle bisherigen verschiedenen Ans"atze zu demselben Begriff gef"uhrt haben. Der Wunsch, Algorithmen zur L"osung m"oglichst vieler mathematischer Probleme zu haben, f"uhrte nat"urlich dazu, da"s man immer allgemeinere Algorithmen zu finden suchte. Das legte es nahe, solche allgemeinen Verfahren im Bereich der Logik zu suchen. Dort hatte man Kalk"ule entwickelt, die es gestatten, gro"se Teile der Mathematik mit Hilfe eines solchen Kalk"uls aus wenigen Axiomen herzuleiten, so z.B. in den Principia Mathematica (1910-1913) von A.N. Whitehead and B. Russel. Es lag nun der Gedanke nahe, nach einem allgemeinen Algorithmus zu fragen, der es erm"oglicht, alle mathematischen S"atze einer mathematischen Theorie, z.B. der Geometrie, die als erste Theorie axiomatisiert worden war, aus Axiomen der Theorie herzuleiten. Das Entscheidungsproblem der modernen Logik war formuliert. Mit den Bestrebungen, dieses Problem zu l"osen, begann die eigentliche Theorie der Algorithmen, der Begriff des Algorithmus wurde pr"azis definiert. Sowohl historisch als auch in logischer Hinsicht ist das Problem der Pr"azisierung des Algorithmenbegriffs eng verkn"upft mit der Pr"azisierung des Begriffs der berechenbaren Funktion. Die logische Verbindung in einer Richtung ist anschaulich klar: damit eine Funktion berechenbar ist, mu"s es einen Algorithmus geben, mit dessen Hilfe man f"ur jedes Argument den zugeh"origen Funktionswert ausrechnen kann. Umgekehrt kann man mit der G"odelisierung den Begriff des Algorithmus zur"uckf"uhren auf den Begriff der berechenbaren Funktion. Die historische Verbindung liegt darin, da"s die ersten Versuche, den Algorithmusbegriff zu pr"azisieren, durch die exakte Formulierung des Begriffes der berechenbaren Funktion unternommen wurde. Diese Untersuchungen begannen mit einer Arbeit von Th. Skolem in Jahre 1923. Die von Skolem betrachteten Funktionen sind die primitiv-rekusiven Funktionen (in heutiger Sprechweise). Aber als selbstst"andige Funktionenklasse, als Begriff, wurden diese Funktionen erst 1931 von Kurt G"odel in seiner epochemachenden Arbeit eingef"uhrt. (Schon 1928 hatte W. Ackermann ein Beispiel f"ur eine offensichtlich berechenbare Funktion angegeben, die nicht primitiv-rekursiv ist.) Das war der Anla"s, eine allgemeinere Definition der Berechenbarkeit zu suchen, un 1934 entwickelten J. Herbrand und K. G"odel das Konzept der allgemein-rekursiven Funktion. Als G"odel diesen Begriff nach einem Vorschlag von Herbrand einf"uhrte, war er noch nicht davon "uberzeugt, damit den allgemeinen Begriff der berechenbaren Funktion gefunden zu haben. Erst 1936, als A. Church und S.C. Kleene eine v"ollig andere Pr"azisierung des Berechenbarkeitsbegriffes gefunden hatten (die $\lambda$-Definierbarkeit) und sie in Zusammenarbeit mit J.B. Rosser die "Aquivalenz dieses Begriffes mit dem von Herbrand und G"odel nachweisen konnten, sprach Church seine ber"uhmte These aus: ``Der intuitiv gegebene, allgemein gebr"auchliche Begriff der berechenbaren arithmetischen Funktion ist identisch mit dem exakt definierten Begriff der allgemein-rekursiven Funktion''. Diese These wurde durch viele sp"atere Ergebnisse immer mehr gest"arkt, so da"s heute ihre G"ultigkeit allgemein angenommen wird. Es ist klar, da"s sie nicht bewiesen werden kann, sie ist jedoch sozusagen ``experimentell'' best"atigt worden: jede bisher bekannte berechenbare Funktion erwies sich als allgemein-rekursiv, und alle Pr"azisierungen des Berechenbarkeitsbegriffs sind dem der allgemein rekursiven Funktion "aquivalent. Da sich herausstellte, da"s man auch arithmetische Funktionen zu betrachten hatte, die wie die allgemein-rekursiven Funktionen erkl"art waren, jedoch nur mit einer Teilmenge der nat"urlichen Zahlen als Definitionsbereich, f"uhrte man den weiteren Begriff der partiell-rekursiven Funktion ein (Kleene 1938) und verwandte ihn ebenfalls in der Churchschen These anstelle des Begriffs der allgemein-rekursiven Funktion. Ein weiterer, sehr entscheidener Schritt in die Theorie der Berechenbarkeit war die Arbeit von A.M. Turing ``On Computable Numbers, with an Application to the Entscheidungsproblem'' 1936-37. Hier wird der fundamentale Begriff der automatischen Maschine, heute Turingmaschine genannt. schon vor der technischen Entwicklung von Rechenmaschinen eingef"uhrt. Dieser Begriff erm"oglicht einen sehr nat"urlichen und einfachen Zugang zu einer exakten Definition der berechenbaren Funktion und des Algorithmus. Fast gleichzeitig mit Turing und unabh"angig von ihm ver"offentlichte E. Post 1937 einen ganz "ahnlichen Vorschlag zur Pr"azisierung des Berechenbarkeitsbegriffs, und oft werden Turingmaschinen heute in der Postschen Weise beschrieben. Da es ganz plausibel ist, da"s jede berechenbare Funktion mit einer Turingmaschine berechnet werden kann, sprach Turing die sp"ater als Turingsche These bezeichnete These aus, da"s die Begriffe der mit einer Turingmaschine berechenbaren Funktion und der im gew"ohnlichen Sinne berechenbaren Funktion "aquivalent sind. Gerade deshalb war es von Bedeutung, da"s Turing 1937 die Gleichwertigkeit seines Berechenbarkeitsbegriffes und der $\lambda$-Definierbarkeit von Church nachweisen konnte. Somit waren Churchsche und Turingsche These identisch. Man hatte nun f"ur den Begriff der berechenbaren Funktion drei verschiedene Pr"azisierungen gefunden und ihre "Aquivalenz nachgewiesen. Dabei hat der Begriff der Turing-Berechenbarkeit noch eine besondere Bedeutung. Er liefert n"amlich eine Definition der mechanischen Berechenbarkeit. Das erste Problem der klassischen Mathematik, dessen Unl"osbarkeit nachgewiesen wurde, ist ein Problem von A. Thue (1914) aus der Theorie der Halbgruppen. Seine Unl"osbarkeit wurde gleichzeitig, aber unabh"angig von E. Post und A.A. Markov 1947 bewiesen. Aus seiner Unl"osbarkeit l"a"st sich die Unl"osbarkeit einer Reihe weiterer, z.T. sehr bedeutender und ber"uhmter Probleme der Mathematik folgern, wie z.B. die Unl"osbarkeit des Wortproblems der Gruppentheorie oder das Entscheidungsproblem der Pr"adikatenlogik. (Siehe {\it Brauer, Ebbinghaus, Boche\'{n}ski}) \subsection*{Turingmaschinen} \begin{deflist}{Bem: } \item[Kon:] $0\in \N$ \item[Def:] Unter einem {\bf Alphabet} $\cal A$ verstehen wir eine nichtleere Menge. \\ $\displaystyle \bigcup_{n\in \N}\{f|f:\{1,...,n\} \rightarrow \cal A\}$ \qquad sei die {\bf Menge $W\left( A\right) $ aller W"orter "uber dem Alphabet $\cal A$}. \item[Kon:] Sei $\cal A$ ein Alphabet, dann bezeichnen wir das {\bf leere Wort}$:\emptyset \rightarrow \cal A$ mit $\Diamond$. \item[Def:] Gegeben sei ein $n$-elementiges Alphabet ${\cal A}=\{a_{1},...,a_{n}\}$. Mit $a_{0}$ bezeichnen wir das leere (uneigentliche) Symbol. $r,l,s$ seien Symbole, die in $\cal A$ nicht vorkommen. Eine {\bf Turingmaschine} $M$ {\bf "uber} $A$ ist gegeben durch eine $4$-spaltige und $\left( m+1\right) \left( n+1\right) $-reihige Matrix ($m\in \N$) der Form:\\ \[\begin{array}{cccc} q_{0} & a_{0} & v_{1} & q'_{1} \\ \vdots & \vdots & \vdots & \vdots \\ q_{0} & a_{n} & v_{n+1} & q'_{n+1} \\ q_{1} & a_{0} & v_{n+2} & q'_{n+2} \\ \vdots & \vdots & \vdots & \vdots \\ q_{1} & a_{n} & v_{2n+2} & q'_{2n+2} \\ \vdots & \vdots & \vdots & \vdots \\ \vdots & \vdots & \vdots & \vdots \\ q_{m} & a_{0} & v_{mn+m+1} & q'_{mn+m+1} \\ \vdots & \vdots & \vdots & \vdots \\ q_{m} & a_{n} & v_{\left( m+1\right) \left( n+1\right) } & q'_{\left( m+1\right) \left( n+1\right) } \\ \end{array} \] Dabei seien $q_{0},...,q_{m}$ verschiedene nat"urliche Zahlen gr"o"ser Null sowie $q'_{j}\in \{q_{0},...,q_{m}\}$ und $v_{j}\in \{a_{0},...,a_{n},r,l,s\}$ f"ur $j\in \{1,...,\left( m+1\right) \left( n+1\right) \}$. \item[Bem:] Zu jeder Turingmaschine "uber einem beliebigen endlichem Alphabet gibt es eine Turingmaschine "uber dem Alphabet $\{|\}$ die dasselbe leistet. \end{deflist} \section*{Das Halteproblem f"ur Turingmaschinen} \subsection*{Einf"uhrendes} Wir definieren f"ur jede Turingmaschine $T$ "uber $\cal A$ und jedem Wort $w$ "uber $\cal A$ das Pr"adikat $E$ durch: $E\left( T\right) := \mbox{``$T$ angesetzt hinter $w$ stoppt''}$. Das Halteproblem besteht in der Frage, ob $E$ ein entscheidbares Pr"adikat f"ur Turingmaschinen ist. \begin{deflist}{Bem: } \item[Kon:] Wir betrachten im folgenden nur solche Turingmaschinen, deren Alphabet ein endliches Anfangsst"uck des festen unendlichen Alphabets $\{a_{1},a_{2},a_{3},...\}$ ist. (Dies bedeutet keine echte Einschr"ankung!) Weiterhin schreiben wir $|$ f"ur $a_{1}$ und $*$ f"ur das leere Symbol. \item[Def:] $p:\N \mapsto \N$ sei die {\bf Primzahlfunktion}, d.h. die Abbildung, die jeder nat"urlichen Zahl $n$ die $\left( n+1\right) $-te Primzahl zuordnet. \item[Def:] $M$ sei eine Turingmaschine "uber einem $n$-elementigen Alphabet ${\cal A}=\{a_{1},...,a_{n}\}$ mit $m$ Zust"anden $q_{0},...,q_{m}$, \ $a_{0}$ sei das leere Symbol. Durch $\left( l,r,s,a_{0},...,a_{n}\right) $ wird $\{1,...,n+4\}$ bijektiv auf $\{l,r,s,a_{0},...,a_{n}\}$ abgebildet. Die zu $M$ geh"orige Matrix ist durch Angabe der ihrer beiden letzten Spalten und $n$ eindeutig bestimmt. In den beiden letzten Spalten, die eine $\left( \left( n+1\right) \left( m+1\right) \right) \times 2$ Matrix $\left( c_{i,j}\right) $ bilden, werden die Symbole durch ihre zugeordneten Zahlen ersetzt. Wir codieren diese Angaben jetzt durch die Zahl $\displaystyle t:=p_{0}^{n}p_{1}^{n} \prod_{i=1}^{\left( n+1\right) \left( m+1\right) } p_{i+1}^{2^{c_{i,1}}\left( 2c_{i,2}+1\right) }$, $t$ hei"se {\bf die G"odelnummer von} $M$. \item[Bem:] Die obige Abbildung ist injektiv und berechenbar. \item[Def:] Eine Menge $B$ von Worten "uber einem Alphabet {\cal A} hei"st {\bf entscheidbar}, falls es eine Turingmaschine $M$ "uber $\cal A$ gibt, so da"s $M$ angesetzt hinter ein Wort $w$ genau dann auf $|$ stehenbleibt, falls $w\in B$, und $M$ angesetzt hinter $w$ genau dann auf $*$ stehenbleibt, falls $w\not\in B$. \item[Bem:] Es ist entscheidbar, ob eine beliebige nat"urliche Zahl $n$ die G"odelnummer einer Turingmaschinen ist oder nicht. \item[Def:] Unter dem {\bf Maschinenwort} $w_{M}$ einer Turingmaschine $M$, verstehen wir das $t$-tupel $\left( |,|,|,...,|\right) $, wobei $t$ die G"odelnummer von $M$ ist. \item[Def:] Eine Eigenschaft $E$ von Turingmaschinen hei"st entscheidbar, wenn entscheidbar ist, ob die zu einem beliebigen Maschinenwort geh"orige Turingmaschine die Eigenschaft $E$ hat. \item[Bem:] Eine Eigenschaft $E$ von Turingmaschinen ist genau dann entscheidbar, wenn f"ur eine beliebiges Wort "uber $\{|\}$ entscheidbar ist, ob es ein Maschinenwort einer Turingmaschine ist, welche die Eigenschaft $E$ hat. \item[Lemma:] Es ist nicht entscheidbar, ob eine beliebige Turingmaschine $M$, angesetzt hinter $w_{M}$, auf $*$ stoppt. \item[Bew:] Angenommen es gebe eine Turingmaschine $T$, die f"ur alle Turingmaschinen $M$ entscheiden kann, ob $M$, angesetzt hinter $w_{M}$, auf $*$ stoppt. Wir setzen $T$ hinter $w_{T}$ an. Falls $T$ auf $|$ stoppt, dann stoppt $T$ angesetzt hinter $w_{T}$ auf $*$; falls $T$ auf $*$ stoppt, dann stoppt $T$ angesetzt hinter $w_{T}$ nicht auf $*$. Widerspruch! \qed \item[Lemma:] Es ist nicht entscheidbar, ob eine beliebige Turingmaschine $M$, angesetzt hinter $w_{M}$, stoppt. \item[Bew:] Angenomen es gebe eine Turingmaschine $T$, die f"ur alle Turingmaschinen $M$ entscheiden kann, ob $M$, angesetzt hinter $w_{M}$, stoppt. Dann konstruiere man sich eine Turingmaschine die falls $M$, angesetzt hinter $w_{M}$, nicht stoppt, auf $*$ stoppt, und sonst $M$, angesetzt hinter $w_{M}$, simuliert (universelle Turingmaschine), und dann falls das letzte Feld mit $*$ beschriftet ist auf $|$, sonst auf $*$, anh"alt . Widerspruch zum vorherigen Lemma! \qed \item[Lemma:] Es ist nicht entscheidbar, ob eine beliebige Turingmaschine $M$, angesetzt auf das leere Band, stoppt. \item[Bew:] Angenomen es gebe eine Turingmaschine $T$, die f"ur alle Turingmaschinen $M$ entscheiden kann, ob $M$, angesetzt auf das leere Band, stoppt. Dann konstruiere man sich eine Turingmaschine die zun"achst $w_{M}$ kopiert und dann (universelle Turingmaschine) $M$ simuliert. Widerspruch zum vorherigen Lemma! \qed \end{deflist} \subsection*{Die universelle Turingmaschine} Eine ``universelle'' Turingmaschine $U$ kann jede beliebige Turingmaschine in einem gewissen Sinne simulieren. Der Konstruktion von $U$ liegt folgender Gedanke zugrunde: Wenn man eine Turingmaschine auf eine gewisse Inschrift in einem gewissen Feld ansetzt, so arbeitet sie gem"a"s gewisser Vorschriften, die sie ihrer Tafel entnimmt. Es liegt nun nahe, eine Turingmaschine zu konstruieren, die sich wie eine beliebig vorgegebene Turingmaschine verhalten kann, sofern man ihr die dazugh"orige Tafel in geeigneter Weise als zus"atzliche Information auf das Band gibt. Wir codieren also die Tafel und die Bandinschrift in zwei W"ortern und interpretieren die codierten Anweisungen f"ur die codierte Bandinschrift. \begin{deflist}{Bem: } \item[Satz:] Es ist nicht entscheidbar, ob eine universelle Turingmaschine $U$, angesetzt auf eine beliebige Inschrift in einem beliebigen Feld, nach endlich vielen Schritten stehenbleibt, oder nicht. \end{deflist} \section*{Die Unl"osbarkeit des Wortproblems f"ur Semi-Thue-Systeme und Thue-Systeme} \subsection*{Grundlegende Definitionen und Bemerkungen} \begin{deflist}{Bem: } \item[Def: ] Gegeben sei ein $n$-elementiges Alphabet $\cal A$. Auf $W\left( \cal A\right) $ definieren wir die zweistellige Verkn"upfung $\bullet$: \\ F"ur $w_{1},w_{2}\in W\left( \cal A\right) $ \ mit \ $w_{1}:\{1,...,l\} \rightarrow \cal A$ \ und \ $w_{2}:\{1,...,m\} \rightarrow \cal A$ \ f"ur geignete \ $l,m\in \N$ \ sei \\ $\forall i\in \{1,...,l+m\} \quad \left( w_{1}\bullet w_{2}\right) \left( i\right) := \left\{ \begin{array}{ll} w_{1}\left( i\right) & \mbox{falls $i\leq m$} \\ w_{2}\left( i\right) & \mbox{sonst} \\ \end{array} \right. $ \\ Die Verkn"upfung $\bullet$ nennt man auch {\bf Verkettung}. \item[Bem:] Sei $\cal A$ ein Alphabet. Dann bildet $W\left( \cal A\right) $ zusammen mit der Verkettung ein Monoid. \item[Kon:] Das Verkn"upfungszeichen der Verkettung wird h"aufig weggelassen. \item[Def:] Sei $\cal A$ ein endliches Alphabet und $\cal S$ eine endliche und nicht leere Menge von geordneten Paaren von Worten aus $W\left( \cal A\right) $. Dann hei"st $\cal S$ {\bf Semi-Thue-System "uber} $\cal A$ und die Elemente von $\cal S$ werden {\bf definierende Relationen} genannt. \\ Auf $W\left( \cal A\right) $ wird mithilfe von $\cal S$ das zweistelliges Pr"adikat $\rightarrow _{\cal S}$ erkl"art: \\ $\rightarrow _{\cal S}\left( w_{1},w_{2}\right) \ := \ w_{1} \rightarrow _{\cal S} w_{2} \ := \ \exists \left( d_{1},d_{2}\right) \in {\cal S} \ \exists u,v\in W\left( {\cal A}\right) :\, \left( w_{1}=ud_{1}v \, \wedge \ w_{2} = ud_{2}v\right) $ \\ Man sagt dann auch, $w_{1}$ sei {\bf im Hinblick auf $\cal S$ unmittelbar "uberf"uhrbar in} $w_{2}$. \item[Def:] Sei $\cal S$ ein Semi-Thue-System "uber $\cal A$, dann wird auf $W\left( \cal A\right) $ mithilfe von $\cal S$ das zweistelliges Pr"adikat $\leadsto _{\cal S}$ erkl"art: \\ $\displaystyle \leadsto _{\cal S}\left( w_{1},w_{2}\right) \ := \ w_{1} \leadsto _{\cal S} w_{2} \ := \ \exists n\in \N \, \exists u_{0},...,u_{n}\in W\left( {\cal A}\right) :\, \left( w_{1} = u_{0} \, \wedge \, \bigwedge _{i=1}^{n} u_{i-1} \rightarrow _{\cal S} u_{i} \, \wedge \, u_{n} = w_{2}\right) $ \\ Man sagt dann auch, $w_{1}$ sei {\bf im Hinblick auf $\cal S$ "uberf"uhrbar in} $w_{2}$. \item[Bem:] Sei $\cal S$ ein Semi-Thue-System "uber $\cal A$, dann ist $\leadsto _{\cal S}$ reflexiv und transitiv und es gilt:\\ $ \forall w_{1},w_{2},u_{1},u_{2}\in W\left( a\right) :\, \left( w_{1} \leadsto _{\cal S} w_{2} \, \wedge \, u_{1} \leadsto _{\cal S} u_{2}\right) \ \Rightarrow \ w_{1}u_{1} \leadsto _{\cal S} w_{2}u_{2} $. \item[Bew:] Die Reflexivit"at ergibt sich mit $n=0$ aus der Definition, die Transitivit"at durch Hintereinanderschreibung der beiden Ketten. Die letzte Aussage erh"alt man durch Nachweis von $w_{1}u_{1} \leadsto _{\cal S} w_{2}u_{1}$ und $w_{2}u_{1} \leadsto _{\cal S} w_{2}u_{2}$ mit der Transitivit"at. \item[Def:] Sei $\cal S$ ein Semi-Thue-System "uber $\cal A$ und sei $\left( d_{1},d_{2}\right) \in {\cal S}$. Dann hei"st $\left( d_{2},d_{1}\right) $ die {\bf inverse Regel} zu $\left( d_{1},d_{2}\right) $. \item[Def:] Sei $\cal S$ ein Semi-Thue-System "uber $\cal A$ und es gelte ${\cal S} = \{ \left( d_{2},d_{1}\right) |\left( d_{1},d_{2}\right) \in {\cal S}\}$, dann hei"st ${\cal S}$ ein {\bf Thue-System}. \item[Bem:] F"ur ein Thue-System ist $\rightarrow$ eine vertr"agliche "Aquivalenzrelation, so da"s die Faktorhalbgruppe gebildet werden kann. \item[Def:] Sei $\cal S$ ein Thue-System "uber $\cal A$ und es gebe eine Abbildung $\sigma :{\cal A} \rightarrow {\cal A}$ mit der Eigenschaft $\sigma \circ \sigma = \mbox{id}_{\cal A}$. Au"serdem gelte $\{\left( a,\sigma \left( a\right) \right) |a\in {\cal A}\} \subseteq {\cal S}$. Dann hei"st $\cal S$ zusammen mit $\sigma $ ein {\bf Gruppensystem "uber} $\cal A$. \end{deflist} Das {\bf Wortproblem f"ur ein Semi-Thue-System} $\cal S$ ist das Problem, einen Algorithmus zu finden, der f"ur beliebige Worte $w,w'$ in endlich vielen Schritten entscheidet, ob $w \rightarrow _{\cal S} w'$. \\ Das {\bf allgemeine Wortproblem f"ur Semi-Thue-Systeme} ist die Frage nach einem Algorithmus, mit dem man f"ur beliebige vorgegebene Semi-Thue-Systeme das Wortproblem l"osen kann. \subsection*{Unl"osbarkeit des Wortproblems} Wir wollen nun zeigen, da"s das allgemeine Wortproblem f"ur Semi-Thue-Systme unl"osbar ist. Dazu betrachten wir die zu eine Turingmaschine zugeh"orige Menge von Konfigurationsworten "uber einem geeigneten Alphabet und definieren $\rightarrow$ durch den Begriff der Folgekonfiguration. Dann schlie"sen wir von der Unl"osbarkeit des Halteproblems auf die Unl"osbarkeit des Wortproblems f"ur Semi-Thue-Systeme. \begin{deflist}{Bem: } \item[Def:] $M$ sei eine Turingmaschine "uber dem $n$-elementigen Alphabet ${\cal A}_{0}=\{a_{1},...,a_{n}\}$. $M$ habe die Zust"ande $0,...,m $ \ $\left( m\in \N\right) $, die den Symbolen $q_{0},..., q_{m}$ entsprechen. $a_{0}$ bezeichne das leere Symbol und $e$, $r$, $r'$, $s$ Hilfsbuchstaben. Weiterhin sei ${\cal A}:=\{a_{0},...,a_{n},q_{0},..., q_{m},e\}$ \ $\left( m+n+6\right) $-elementig, Gro"sbuchstaben sollen die zu einem Symbol geh"origen W"orter bezeichnen (z.B: $S:\{1\} \rightarrow {\cal A}: 1 \mapsto s$). Das der Konfiguration $K=\left( a,B,c\right) $ von $M$ zugeordnete {\bf Konfigurationswort} $w_{K}\in W\left( \cal A\right) $ wird wie folgt ermittelt: \begin{itemize} \item Man betrachte den kleinsten zusammenh"angenden Abschnitt von $B$, der die markierten Felder sowie das Feld $a$ umfa"st. \item Diese Teilinschrift von $B$ gebe man durch ein Wort aus $W\left( {\cal A}\right) $ wieder. \item Unmittelbar links von dem Symbol f"ur das Feld $a$ f"uge man das Wort $Q_{c}$ ein. \item Man f"uge links und rechts das Hilfswort $E$ an. \end{itemize} Aus dem so bestimmten Konfigurationswort l"a"st sich die urspr"ungliche Konfiguration (bis auf Parallelverschiebung des Rechenbandes) ablesen. \end{deflist} Wir konstruieren jetzt ein Semi-Thue-System ${\cal S}\left( M\right) $ "uber $\cal A$ wie folgt: Jeder Zeile $\left( i,a_{j},v,k\right) $ von $M$ wird eine oder mehrere Regeln von ${\cal S} \left( M\right) $ zugeordnet. \begin{itemize} \item Einer Zeile $\left( i,a_{j},a_{l},k\right) $ wird die definierende Regel \\ $\begin{array}{ll} %$ \mbox{(a)} %$ \qquad\qquad & \left( Q_{i}A_{j},Q_{k}A_{l}\right) \\ \end{array} $ \\ zugeordnet. \item Einer Zeile $\left( i,a_{j},r,k\right) $ mit $j\not=0$ werden die definierenden Regeln \\ $\begin{array}{lll} %$ \mbox{(b)} %$ \qquad\qquad & \left( Q_{i}A_{j}A_{t},A_{j}Q_{k}A_{l}\right) & \mbox{f"ur } t=0,...,n \\ & \left( Q_{i}A_{j}E,A_{j}Q_{k}A_{0}E\right) \\ \end{array}$ \\ zugeordnet. (Die letztgenannte Regel entspricht dem Fall, da"s das Arbeitsfeld das letzte Zeichen von $w_{K}$ ist, so da"s beim "Ubergang zu $K'$ ein leeres Feld angeh"angt werden mu"s.) \item Einer Zeile $\left( i,a_{0},r,k\right) $ werden die definierenden Regeln \\ $\begin{array}{lll} & \left( A_{u}Q_{i}A_{0}A_{t},A_{u}A_{0}Q_{k}A_{t}\right) & \mbox{f"ur } u,t=0,...,n \\ %$ \mbox{(b')} %$ \qquad\qquad & \left( EQ_{i}A_{0}A_{t},EQ_{k}A_{t}\right) & \mbox{f"ur }t=0,...,n \\ & \left( A_{u}Q_{i}A_{0}E,A_{u}A_{0}Q_{k}A_{0}E\right) & \mbox{f"ur } u=0,...,n \\ & \left( EQ_{i}A_{0}E,EQ_{k}A_{0}E\right) \\ \end{array} $ \\ zugeordnet. \item Einer Zeile $\left( i,a_{j},l,k\right) $ mit $j\not=0$ werden die definierenden Regeln \\ $\begin{array}{lll} %$ \mbox{(c)} %$ \qquad\qquad & \left( A_{u}Q_{i}A_{j},Q_{k}A_{u}A_{j}\right) & \mbox{f"ur } u=0,...,n \\ & \left( EQ_{i}A_{j},EQ_{k}A_{0}A_{j}e\right) \\ \end{array}$ \\ zugeordnet. \item Einer Zeile $\left( i,a_{0},l,k\right) $ werden die definierenden Regeln \\ $\begin{array}{lll} & \left( A_{u}Q_{i}A_{0}A_{t},Q_{k}A_{u}A_{0}A_{t}\right) & \mbox{f"ur } u,t=0,...,n \\ %$ \mbox{(c')} %$ \qquad\qquad & \left( A_{u}Q_{i}A_{0}E,Q_{k}A_{u}E\right) & \mbox{f"ur }u=0,...,n \\ & \left( EQ_{i}A_{0}A_{t},EQ_{k}A_{0}A_{0}A_{t}\right) & \mbox{f"ur } t=0,...,n \\ & \left( EQ_{i}A_{0}E,EQ_{k}A_{0}E\right) \\ \end{array} $ \\ zugeordnet. \item Einer Zeile $\left( i,a_{i},s,k\right) $ werden die definierenden Regeln \\ $\begin{array}{lll} & \left( Q_{i}A_{j},R\right) \\ & \left( A_{u}R,R\right) & \mbox{f"ur } u=0,...,n \\ %$ \mbox{(d)} %$ \qquad\qquad & \left( ER,R'\right) \\ & \left( R'A_{t},R'\right) & \mbox{f"ur }t=0,...,n \\ & \left( R'E,S\right) \\ \end{array} $ \\ zugeordnet. \end{itemize} Die Regeln aus (d) dienen dazu, Endkonfigurationen in $S$ zu "uberf"uhren. Falls man das Wortproblem f"ur Thue-Systeme nicht als unl"osbar nachweisen will, gen"ugen in (d) etwas k"urzere Regeln, au"serdem ben"otigt man dann auch die Symbole $r$ und $r'$ nicht mehr: Einer Zeile $\left( i,a_{i},s,k\right) $ werden die definierenden Regeln \\ $\begin{array}{lll} & \left( Q_{i}A_{j},S\right) \\ %$ \mbox{(d')} %$ \qquad\qquad & \left( A_{u}S,S\right) & \mbox{f"ur } u=0,...,n \\ \\ & \left( SA_{t},S\right) & \mbox{f"ur } t=1,...,n \\ \end{array} $ \\ zugeordnet. Dabei werden Endkonfigurationen in $ESE$ "uberf"uhrt. \\ \\ Wir definieren $w^{*}:=S$ und zeigen, da"s folgendes gilt: \begin{deflist}{Bem: } \item[Satz:] \begin{deflist}{Bem: } \item[(1)] Ist $K'$ eine Folgekonfiguration von $K$, so gilt $w_{K} \rightarrow _{\cal S} w_{K'}$. \item[(2)] Ist $K'$ eine Folgekonfiguration von $K$ und gilt $w_{K} \rightarrow _{\cal S} w$, so ist $w=w_{K'}$. \item[(3)] Ist $K$ eine Endkonfiguration, so gilt $w_{K} \rightarrow _{\cal S} w^{*}$. \item[(4)] $w^{*}$ ist kein Konfigurationswort. \end{deflist} \item[Bew:] \begin{deflist}{Bem: } \item[(1)] Ergibt sich direkt aus den definierenden Regeln (a),(b),(b'), (c),(c'). \item[(2)] Wir nennen ein Wort aus $W\left( \cal A\right) $ ein {\bf Normalwort}, wenn es genau einen der Buchstaben $Q_{0},...,Q_{m},R,R',S$ enth"alt. Es gilt: \begin{deflist}{Bem: } \item[(5)] F"ur jede Konfiguration $K$ von $M$ ist $w_{K}$ ein Normalwort. \item[(6)] Ist $w\in W\left( \cal A\right) $ ein Normalwort und gilt f"ur ein weiteres $w'\in W\left( \cal A\right) $ \ $w \rightarrow _{{\cal S}\left( M\right) } w'$, so ist $w'$ eindeutig bestimmt, denn auf jedes Normalwort kann h"ochstens eine der Regeln (a),(b),(b'),(c),(c'),(d) angewandt werden. \end{deflist} Aus (5),(6) und (1) folgt (2). \item[(3)] Die definierenden Regeln von (d) sorgen daf"ur, da"s f"ur jede Endkonfiguration $K$ das Wort $w_{K}$ in $w^{*}$ "uberf"uhrt werden kann: Durch Anwendung der ersten Regel von (d) entsteht aus $w_{K}$ ein Wort der Gestalt $EA_{u_{p}}...A_{u_{1}}RA_{t_{1}}...A_{t_{q}}E$. Mithilfe des zweiten Regelsatzes von (d) erh"alt man nach mehrmaliger Anwendung schlie"slich $ERA_{t_{1}}...A_{t_{q}}E$ und die dritte Regel liefert dann $R'A_{t_{1}}...A_{t_{q}}E$. Mithilfe des vierten Regelsatzes von (d) bekommt man $R'E$ und die f"unfte Regel f"uhrt letztendlich auf $S$. \item[(4)] Jedes Konfigurationswort enth"alt ein Wort $Q_{k}$, also ist $w^{*}=S$ kein Konfigurationswort. \end{deflist} \end{deflist} \begin{deflist}{Bem:} \item[Lemma:] $M$, angesetzt auf $B$ in $a$, bleibt genau dann nach endlich vielen Schritten stehen, wenn f"ur $K=\left( a,B,c_{0}\right) $ gilt: $w_{K} \leadsto _{{\cal S}\left( M\right) } w^{*}$. \item[Bew:] \begin{deflist}{Bem: } \item[``$\Rightarrow$'':] $M$ bleibe, angesetzt auf $B$ in $a$ nach endlich vielen Schritten stehen. $K_{p}$ sei die dann erreichte Endkonfiguration. Dann gilt nach (1) $w_{K} \leadsto _{{\cal S}\left( M\right) } w_{K_{p}}$ und nach (3) $w_{K_{p}} \leadsto _{{\cal S}\left( M\right) } w^{*}$, also (wegen der Transitivit"at) $w_{K} \leadsto _{{\cal S}\left( M\right) } w^{*}$. \item[``$\Leftarrow$'':] Es gelte $w_{K} \leadsto _{{\cal S}\left( M\right) } w^{*}$, dann gibt es eine Kette $w_{K}=w_{0} \rightarrow _{{\cal S}\left( M\right) } w_{2} \rightarrow _{{\cal S}\left( M\right) } ... \rightarrow _{{\cal S}\left( M\right) } w_{p} \rightarrow _{{\cal S}\left( M\right) } w^{*}$. Angenommen $M$ stoppt nicht nach endlich vielen Schritten, dann gibt es zu jedem $i\in \N$ eine $i$-te Konfiguration $K_{i}$. Wir beweisen nun mit vollst"andiger Induktion, da"s gilt: $\forall i\in \{0,...,p\}: w_{K_{i}}=w_{K}$. \begin{deflist}{II } \item[I] $K_{0}=K \ \Rightarrow \ w_{K_{0}}=w_{K}$ \item[II] Sei f"ur ein $i