\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<p$ die Behauptung richtig, dann gilt
             nach (1) da
             $K_{i+1}$ eine Folgekonfiguration von $K_{i}$ ist: $w_{K}=
             w_{K_{i}} \rightarrow _{{\cal S}\left( M\right) } w_{K_{i+1}}$. Nach (2)
             folgt nun $w_{K_{i}}=w_{i}$.
        \end{deflist}
        Nun ist aber nach (4) $w_{p}=w^{*}$ kein Konfigurationswort.
        Widerspruch. \qed
    \end{deflist}
 \end{deflist}
\begin{deflist}{Bem: }
  \item[Satz:] Das allgemeine Wortproblem f"ur Semi-Thue-Systeme ist 
    unl"osbar.
  \item[Bew:] W"are das allgemeine Wortproblem f"ur Semi-Thue-Systeme l"osbar,
    so k"onnte man auf Grund des vorherigen Lemmas entscheiden, ob eine
    beliebige Turingmaschine $M$ angesetzt auf ein beliebiges $B$ in $a$
    nach endlich vielen Schritten stehenbleibt. Damit w"are aber das
    Halteproblem l"osbar. Widerspruch! \qed
  \item[Satz:] Sei $U$ eine universelle Turingmaschine. Dann ist das
    Wortproblem f"ur das Semi-Thue-System ${\cal S}\left( U\right) $ unl"osbar.
  \item[Bew:] Wenn das Wortproblem f"ur ${\cal S}\left( U\right) $ l"osbar w"are, so k"onnte
    man entscheiden ob $U$, angesetzt hinter ein beliebiges Wort, nach
    endlich vielen Schritten stehenbleibt. Dies ist jedoch f"ur eine
    universelle Turingmaschine nicht m"oglich. Widerspruch! \qed
\end{deflist}

\begin{deflist}{Bem:}
  \item[Def:] Die Erweiterung von ${\cal S}\left( M\right) $ durch Hinzuf"ugen der inversen 
    definierenden Regeln zu einem Thue-System nennen wir ${\cal T}\left( M\right) $.
  \item[Bem:]     \begin{deflist}{Bem: }
    \item[(7)] Sei f"ur $w,w'\in W\left( \cal A\right) $ ein Normalwort und 
       $w \rightarrow _{{\cal S}\left( M\right) } w'$
       oder $w' \rightarrow _{{\cal S}\left( M\right) } w$ so ist auch $w'$ ein Normalwort,
       denn in jeder Regel von ${\cal S}\left( M\right) $ tritt in beiden Komponenten
       genau einer der Buchstaben $Q_{0},...,Q_{m},R,R',S$ auf.
    \item[(8)] Es gibt kein $w\in W\left( \cal S\right) $, so da"s $w^{*} \rightarrow
       _{{\cal S}\left( M\right) } w$, denn auf $w^{*}$ ist keine definierende Regel von
       ${\cal S}\left( M\right) $ anwendbar.
    \end{deflist}
  \item[Lemma:] F"ur jedes Konfigurationswort $w_{K}$ gilt:
    $w_{K} \leadsto _{{\cal T}\left( M\right) } w^{*} \ \Leftrightarrow \ w_{K} \leadsto
    _{{\cal S}\left( M\right) } w^{*}$.
  \item[Bew:] Wir brauchen nur ``$\Rightarrow$'' zu zeigen. \\
    Angenommen es
    gebe eine Konfiguration $K$ f"ur die gilt: 
    $w_{K} \leadsto _{{\cal T}\left( M\right) } w^{*} \ \wedge \
    \neg \left( w_{K} \leadsto _{{\cal S}\left( M\right) } w^{*}\right) $. Dann gibt es eine Kette
    $w_{K}=w_{0} \leadsto _{{\cal T}\left( M\right) } w_{1} \leadsto _{{\cal T}\left( M\right) } 
    ... \leadsto _{{\cal T}\left( M\right) } w_{p}=w^{*}$. Nach (5) und (7) sind alle
    Worte $w_{0},...,w_{p}$ Normalworte. Es gibt n.V. einen Index $i<p$
    f"ur den gilt: $w_{i+1} \leadsto _{{\cal S}\left( M\right) } w^{*}$ aber nicht
    $w_{i} \leadsto _{{\cal S}\left( M\right) } w^{*}$. Die definierende Regel $R$ aus 
    ${\cal T}\left( M\right) $, welche $w_{i}$ unmittelbar in
    $w_{i+1}$ "uberf"uhrt, kann nicht in ${\cal S}\left( M\right) $ liegen, da sonst
    $w_{i} \leadsto _{{\cal S}\left( M\right) } w^{*}$ folgen w"urde. Also liegt die zu
    $R$ inverse Regel in ${\cal S}\left( M\right) $ und somit gilt:
    gilt: $w_{i+1} \leadsto _{{\cal S}\left( M\right) } w_{i}$. Aus 
    $w_{i+1} \leadsto _{{\cal S}\left( M\right) } w^{*}$ folgt die Existenz eines
    $v\in W\left( \cal A\right) $ mit $w_{i+1} \rightarrow _{{\cal S}\left( M\right) } v$. Es ist
    $v \not =w^{*}$, denn sonst w"urde $w^{*}=v \rightarrow _{{\cal S}\left( M\right) } 
    w_{i}$ im Widerspruch zu (8) folgen. Nun folgt aus 
    $w_{i+1} \leadsto _{{\cal S}\left( M\right) } w_{i}$ und 
    $w_{i+1} \rightarrow _{{\cal S}\left( M\right) } v$ mit (6), da"s 
    $v=w_{i}$. Daraus k"onnen wir jetzt $w_{i} \rightarrow _{{\cal S}\left( M\right) } 
    w^{*}$ schlie"sen, da $v \rightarrow _{{\cal S}\left( M\right) } 
    w^{*}$ . Widerspruch! \qed
  \item [Satz:] Das allgemeine Wortproblem f"ur Thue-Systeme ist unl"osbar und
    das Wortproblem eines einer universellen Turingmaschine zugeordneten
    Thue-Systems ist unl"osbar.
  \item [Bew:] Dieser Satz folgt direkt aus dem vorherigen Lemma und den beiden
    letzten S"atzen.
\end{deflist}

Von der linguistischen Fragestellung nach einer formalen Beschreibung von
Grammatiken ausgehend, hat N. Chomsky mittels Semi-Thue-Systemen die nach ihm
benannten formalen Sprachen definiert, mit denen man gerade gewisse
Teilmengen von endlich erzeugten freien Monoiden beschreiben kann.
In der Informatik werden Programmiersprachen formal durch Chomskysprachen 
definiert. ({\it Hotz} Einleitung)
\\ \\
Wir haben nun ein Thue-System mit unl"osbarem Wortproblem konstruiert,
ohne uns "uberhaupt darum zu k"ummern, als wie kompliziert sich dieser Kalk"ul
erweist. Man kann in einer ersten Approximation annehmen, da"s die 
Kompliziertheit durch die Anzahl der Elemente des Alphabets und die Anzahl
der definierenden Relationen charakterisiert wird.
Sehr einfache "Uberlegungen zeigen, da"s zu einem $m$-elementigen
Thue-System "uber einem
$n$-elementigen Alphabet mit unl"osbarem Wortproblem auch ein
$m$-elementiges Thue-System "uber einem $2$-elementigen Alphabet mit
unl"osbarem Wortproblem existiert.
Es entsteht die Aufgabe, ein Thue-System mit unl"osbarem Wortproblem und der
kleinsten Anzahl definierender Relationen zu finden. Es gibt Gr"unde
anzunehmen, da"s Thue-Systeme mit genau einer definierenden Relation ein
l"osbares Wortproblem haben. Andererseits wurde von G.S. Cejtin gezeigt, da"s
folgendes Thue-System $\cal T$ "uber dem Alphabet $\{a,b,c,d,e\}$ ein unl"osbares
Wortproblem hat: ${\cal H}:=\{\left( ac,ca\right) ,\left( ad,da\right) ,\left( bc,cb\right) ,\left( bd,db\right) ,\left( eca,ce\right) ,
\left( edb,de\right) ,\left( cca,ccae\right) \}$ \ ${\cal T}$ entstehe aus $\cal H$ durch Hinzuf"ugen
der inversen Relationen. Ein Thue-System mit unl"osbarem Wortproblem und
weniger als $7$ definierenden Relationen ist einstweilen (1974?)
unbekannt. ({\it Malcev} p. 229)
\\ \\

Novikov 1952, 1955 und unabh"angig voneinander Boone und Britton 1958 zeigten, 
da"s Dehn's Wortproblem im allgemeinen unl"osbar ist. Au"serdem stellten sie
endliche Repr"asentationen von Gruppen vor, f"ur die es keinen Algorithmus gibt
der f"ur ein beliebiges aus den Generatoren gebildetes Wort feststellen kann, ob
es das neutrale Element ist. 
Schon 1947 wurde von Post und 1950 von Turing bewiesen, da"s das Wortproblem in
Halbgruppen mit K"urzungsregel im allgemeinen unl"osbar ist.
Zuerst benutzte Rabin 1958 und sp"ater Baumslag, Boone und B. H. Neumann, die
Entdeckungen Novikovs dazu, praktisch alle Probleme die endliche 
Repr"asentationen von Gruppen betreffen, als im allgemeinen unl"osbar nachzuweisen.


\subsection*{Literaturverzeichnis}
\begin{deflist}{\qquad }
  \item[Hermes, H.:] Aufz"ahlbarkeit, Entscheidbarkeit, Berechenbarkeit. 
    Springer, Berlin 1978
  \item[Magnus, W. $\backslash$ Karrass, A. $\backslash$ Solitar, D.:]
    Combinatorical Group Theory. Interscience, New York 1966
  \item[Britton, J. L.:] The Word Problem for Groups. Proc. 
    London math. Soc., Vol. 8 1958
  \item[Hotz, G. $\backslash$ Walter, H.:] Automatentheorie und formale
    Sprachen I. BI, Mannheim 1968
  \item[Hotz, G. $\backslash$ Claus, V.:] Automatentheorie und formale
    Sprachen III. BI, Mannheim 1972
  \item[Ebbinghaus, H.-D. $\backslash$ Mahn, F.-K. :] Turing-Maschinen und 
    berechenbare Funktionen. In: Selecta Mathematica II, Springer, Berlin 1970
  \item[Brauer, W. $\backslash$ Indermark, K.:] Algorithmen, rekursive 
    Funktionen und formale Sprachen. BI, Mannheim 1968
  \item[Boche\'{n}ski, J.M.:] Formale Logik. Karl Alber, Freiburg 1956
  \item[Malcev, A.I.:] Algorithmen und rekursive Funktionen. Vieweg, 
    Braunschweig 1974
  \item[Huppert, B.:] Endliche Gruppen I. Springer, Berlin 1967
\end{deflist}

\begin{flushright} Michael Meyling \end{flushright}
\end{document}
