home of Michael Meyling

Die Unlösbarkeit des Wortproblems für Semi-Thue-Systeme und Thue-Systeme

Vortragsnotizen ``Das Wortproblem für Semi-Thue-Systeme''

Seminar über mathematische Logik, 15.04.1992

Michael Meyling

Einleitung

Die Unlösbarkeit des Halteproblems für Turingmaschinen kann dazu benutzt werden, die Unentscheidbarkeit anderer, interessanterer Probleme zu beweisen. Dabei geht es stets um die Frage, ob ein Prädikat einer entscheidbaren Menge von Objekten entscheidbar ist. Man zeigt dazu, daß die Lösung dieser Frage die Lösung des Halteproblems beinhalten würde. Die universelle Turingmaschine wird dann zur Konstruktion eines speziellen Objektes benutzt, von dem man nicht entscheiden kann, ob ihm das Prädikat zukommt oder nicht.
Alle Beweise beruhen im Prinzip auf dem Diagonalverfahren.

Historische Einbettung

Der Begriff des Algorithmus ist einer der grundlegenden Begriffe der Mathematik. Er ist intuitiv gegeben und gewöhnlich versteht man darunter ein allgemeines Verfahren zur Lösung einer Klasse von Problemen. Dabei soll dieses Verfahren durch eine eindeutige Vorschrift so bis in alle Einzelheiten festgelgt sein, daß für seine Anwendung kein ``Geist'' erforderlich ist. Klassische Beispiele hierfür sind der Euklidische Algorithmus und das Gaußsche Eliminationsverfahren.
Schon von den Arabern sind, unter dem Einfluß 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ück, der durch sein (später als ``liber algorithmi'' zitiertes) Buch über die Behandlung algebraischer Gleichungen wesentlich zur Verbreitung der damals entstandenen Rechenmethoden beigetragen hat.
Die von den Arabern eingeführten mathematischen Methoden haben den Spanier Raymundus Lullus (ca. 1235-1315) angeregt zu seiner berühmten ``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ßen Einfluß auf die Nachwelt: noch zweihundert Jahre später veröffentlichte 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ösung zugänglich seien, wurde von berühmten Mathematikern geteilt. So seien hier Descartes, Leibniz und Hilbert als Repräsentanten genannt.
Descartes entwickelte die analytische Geometrie in der Absicht, die Geometrie algebraischen Rechenmethoden zugänglich zu machen. Auch von Leibniz ist bekannt, daß er sich sehr um die Entwicklung von Algorithmen bemüht hat und daß ihm eine allumfassende Methode, jedes Problem durch ``Rechnen'' zu lösen, vorschwebte. Er betont, daß er von Lullus beeinflußt sei, jedoch entwickelte er präzisere Vorstellungen von diesem Begriff. Er unternahm wohl als erster den Versuch, für 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ösung bestimmter Probleme.
Auch die Tatsache, daß schon im vorigen Jahrhundert für gewisse Probleme Unlösbarkeitsbeweise geführt worden waren, z.B. für Konstruktionen mit Zirkel und Lineal, Auflösbarkeit algebraischer Gleichungen mit Hilfe von Radikalen, beeinflußte die Mathematiker nicht in ihrem Glauben an die prinzipielle Lösbarkeit aller mathematischen Probleme, denn diese Beweise zeigten nur die Undurchführbarkeit einer gewissen Aufgabe mit bestimmten Hilfsmitteln (Zirkel und Lineal, Radikale), aber nicht die generelle Unlösbarkeit. Bei den späteren Unlösbarkeitsbeweisen ist das etwas anderes. Denn, wie Emil Post es formulierte, sind diese Beweise zwar ebenfalls Beweise der Unlösbarkeit einer Aufgabe mit gewissen Hilfsmitteln, jedoch scheint es hier so zu sein, daß diese Hilfsmittel die einzigen sind, die dem Menschen zur Lösung dieser Aufgabe zur Verfügung stehen. Diese Beweise zeigen nämlich, daß es mathematische Probleme gibt, für die es keinen Algorithmus zu ihrer Lösung geben kann.
Der in einer solchen Aussage vorkommende Begriff des Algorithmus muß natürlich exakt definiert sein und man könnte leicht meinen, eine strenge mathematische Definition wäre vielleicht zu eng, den intuitiven Begriff des Algorithmus zu fassen, es hat sich jedoch erwiesen, daß alle bisherigen verschiedenen Ansätze zu demselben Begriff geführt haben.
Der Wunsch, Algorithmen zur Lösung möglichst vieler mathematischer Probleme zu haben, führte natürlich dazu, daß man immer allgemeinere Algorithmen zu finden suchte. Das legte es nahe, solche allgemeinen Verfahren im Bereich der Logik zu suchen. Dort hatte man Kalküle entwickelt, die es gestatten, große Teile der Mathematik mit Hilfe eines solchen Kalküls 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öglicht, alle mathematischen Sätze 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ösen, begann die eigentliche Theorie der Algorithmen, der Begriff des Algorithmus wurde präzis definiert.
Sowohl historisch als auch in logischer Hinsicht ist das Problem der Präzisierung des Algorithmenbegriffs eng verknüpft mit der Präzisierung des Begriffs der berechenbaren Funktion. Die logische Verbindung in einer Richtung ist anschaulich klar: damit eine Funktion berechenbar ist, muß es einen Algorithmus geben, mit dessen Hilfe man für jedes Argument den zugehörigen Funktionswert ausrechnen kann. Umgekehrt kann man mit der Gödelisierung den Begriff des Algorithmus zurückführen auf den Begriff der berechenbaren Funktion. Die historische Verbindung liegt darin, daß die ersten Versuche, den Algorithmusbegriff zu präzisieren, 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ändige Funktionenklasse, als Begriff, wurden diese Funktionen erst 1931 von Kurt Gödel in seiner epochemachenden Arbeit eingeführt. (Schon 1928 hatte W. Ackermann ein Beispiel für eine offensichtlich berechenbare Funktion angegeben, die nicht primitiv-rekursiv ist.) Das war der Anlaß, eine allgemeinere Definition der Berechenbarkeit zu suchen, un 1934 entwickelten J. Herbrand und K. Gödel das Konzept der allgemein-rekursiven Funktion. Als Gödel diesen Begriff nach einem Vorschlag von Herbrand einführte, war er noch nicht davon überzeugt, damit den allgemeinen Begriff der berechenbaren Funktion gefunden zu haben. Erst 1936, als A. Church und S.C. Kleene eine völlig andere Präzisierung des Berechenbarkeitsbegriffes gefunden hatten (die l -Definierbarkeit) und sie in Zusammenarbeit mit J.B. Rosser die Äquivalenz dieses Begriffes mit dem von Herbrand und Gödel nachweisen konnten, sprach Church seine berühmte These aus: ``Der intuitiv gegebene, allgemein gebräuchliche Begriff der berechenbaren arithmetischen Funktion ist identisch mit dem exakt definierten Begriff der allgemein-rekursiven Funktion''. Diese These wurde durch viele spätere Ergebnisse immer mehr gestärkt, so daß heute ihre Gültigkeit allgemein angenommen wird. Es ist klar, daß sie nicht bewiesen werden kann, sie ist jedoch sozusagen ``experimentell'' bestätigt worden: jede bisher bekannte berechenbare Funktion erwies sich als allgemein-rekursiv, und alle Präzisierungen des Berechenbarkeitsbegriffs sind dem der allgemein rekursiven Funktion äquivalent. Da sich herausstellte, daß man auch arithmetische Funktionen zu betrachten hatte, die wie die allgemein-rekursiven Funktionen erklärt waren, jedoch nur mit einer Teilmenge der natürlichen Zahlen als Definitionsbereich, führte 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ührt. Dieser Begriff ermöglicht einen sehr natürlichen und einfachen Zugang zu einer exakten Definition der berechenbaren Funktion und des Algorithmus. Fast gleichzeitig mit Turing und unabhängig von ihm veröffentlichte E. Post 1937 einen ganz ähnlichen Vorschlag zur Präzisierung des Berechenbarkeitsbegriffs, und oft werden Turingmaschinen heute in der Postschen Weise beschrieben. Da es ganz plausibel ist, daß jede berechenbare Funktion mit einer Turingmaschine berechnet werden kann, sprach Turing die später als Turingsche These bezeichnete These aus, daß die Begriffe der mit einer Turingmaschine berechenbaren Funktion und der im gewöhnlichen Sinne berechenbaren Funktion äquivalent sind. Gerade deshalb war es von Bedeutung, daß Turing 1937 die Gleichwertigkeit seines Berechenbarkeitsbegriffes und der l -Definierbarkeit von Church nachweisen konnte. Somit waren Churchsche und Turingsche These identisch.
Man hatte nun für den Begriff der berechenbaren Funktion drei verschiedene Präzisierungen gefunden und ihre Äquivalenz nachgewiesen. Dabei hat der Begriff der Turing-Berechenbarkeit noch eine besondere Bedeutung. Er liefert nämlich eine Definition der mechanischen Berechenbarkeit. Das erste Problem der klassischen Mathematik, dessen Unlösbarkeit nachgewiesen wurde, ist ein Problem von A. Thue (1914) aus der Theorie der Halbgruppen. Seine Unlösbarkeit wurde gleichzeitig, aber unabhängig von E. Post und A.A. Markov 1947 bewiesen. Aus seiner Unlösbarkeit läßt sich die Unlösbarkeit einer Reihe weiterer, z.T. sehr bedeutender und berühmter Probleme der Mathematik folgern, wie z.B. die Unlösbarkeit des Wortproblems der Gruppentheorie oder das Entscheidungsproblem der Prädikatenlogik.
(Siehe Brauer, Ebbinghaus, Boche' nski)

Turingmaschinen

Bem:
Kon: 0 Î N
Def: Unter einem Alphabet cal A verstehen wir eine nichtleere Menge.
displaystyle È n Î N {f|f:{1,...,n} ® cal A}    sei die Menge W( A) aller Wörter über dem Alphabet cal A.
Kon: Sei cal A ein Alphabet, dann bezeichnen wir das leere Wort: Æ ® cal A mit Diamond .
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 Turingmaschine M über A ist gegeben durch eine 4-spaltige und ( m+1) ( n+1) -reihige Matrix (m Î N ) der Form:
[
q 0 a 0 v 1 q' 1
: : : :
q 0 a n v n+1 q' n+1
q 1 a 0 v n+2 q' n+2
: : : :
q 1 a n v 2n+2 q' 2n+2
: : : :
: : : :
q m a 0 v mn+m+1 q' mn+m+1
: : : :
q m a n v ( m+1) ( n+1) q' ( m+1) ( n+1)
]
Dabei seien q 0 ,...,q m verschiedene natürliche Zahlen größer Null sowie q' j Î {q 0 ,...,q m } und v j Î {a 0 ,...,a n ,r,l,s} für j Î {1,...,( m+1) ( n+1) }.
Bem: Zu jeder Turingmaschine über einem beliebigen endlichem Alphabet gibt es eine Turingmaschine über dem Alphabet {|} die dasselbe leistet.

Das Halteproblem für Turingmaschinen

Einführendes

Wir definieren für jede Turingmaschine T über cal A und jedem Wort w über cal A das Prädikat E durch: E( T) := ``T angesetzt hinter w stoppt''. Das Halteproblem besteht in der Frage, ob E ein entscheidbares Prädikat für Turingmaschinen ist.
Bem:
Kon: Wir betrachten im folgenden nur solche Turingmaschinen, deren Alphabet ein endliches Anfangsstück des festen unendlichen Alphabets {a 1 ,a 2 ,a 3 ,...} ist. (Dies bedeutet keine echte Einschränkung!) Weiterhin schreiben wir | für a 1 und * für das leere Symbol.
Def: p:N ñ® N sei die Primzahlfunktion, d.h. die Abbildung, die jeder natürlichen Zahl n die ( n+1) -te Primzahl zuordnet.
Def: M sei eine Turingmaschine über einem n-elementigen Alphabet cal A={a 1 ,...,a n } mit m Zuständen q 0 ,...,q m , a 0 sei das leere Symbol. Durch ( l,r,s,a 0 ,...,a n ) wird {1,...,n+4} bijektiv auf {l,r,s,a 0 ,...,a n } abgebildet. Die zu M gehörige Matrix ist durch Angabe der ihrer beiden letzten Spalten und n eindeutig bestimmt. In den beiden letzten Spalten, die eine ( ( n+1) ( m+1) ) C 2 Matrix ( c i,j ) 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 Õ i=1 ( n+1) ( m+1) p i+1 2 c i,1 ( 2c i,2 +1) , t heiße die Gödelnummer von M.
Bem: Die obige Abbildung ist injektiv und berechenbar.
Def: Eine Menge B von Worten über einem Alphabet cal A heißt entscheidbar, falls es eine Turingmaschine M über cal A gibt, so daß M angesetzt hinter ein Wort w genau dann auf | stehenbleibt, falls w Î B, und M angesetzt hinter w genau dann auf * stehenbleibt, falls wnot Î B.
Bem: Es ist entscheidbar, ob eine beliebige natürliche Zahl n die Gödelnummer einer Turingmaschinen ist oder nicht.
Def: Unter dem Maschinenwort w M einer Turingmaschine M, verstehen wir das t-tupel ( |,|,|,...,|) , wobei t die Gödelnummer von M ist.
Def: Eine Eigenschaft E von Turingmaschinen heißt entscheidbar, wenn entscheidbar ist, ob die zu einem beliebigen Maschinenwort gehörige Turingmaschine die Eigenschaft E hat.
Bem: Eine Eigenschaft E von Turingmaschinen ist genau dann entscheidbar, wenn für eine beliebiges Wort über {|} entscheidbar ist, ob es ein Maschinenwort einer Turingmaschine ist, welche die Eigenschaft E hat.
Lemma: Es ist nicht entscheidbar, ob eine beliebige Turingmaschine M, angesetzt hinter w M , auf * stoppt.
Bew: Angenommen es gebe eine Turingmaschine T, die für 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
Lemma: Es ist nicht entscheidbar, ob eine beliebige Turingmaschine M, angesetzt hinter w M , stoppt.
Bew: Angenomen es gebe eine Turingmaschine T, die für 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ält . Widerspruch zum vorherigen Lemma! qed
Lemma: Es ist nicht entscheidbar, ob eine beliebige Turingmaschine M, angesetzt auf das leere Band, stoppt.
Bew: Angenomen es gebe eine Turingmaschine T, die für alle Turingmaschinen M entscheiden kann, ob M, angesetzt auf das leere Band, stoppt. Dann konstruiere man sich eine Turingmaschine die zunächst w M kopiert und dann (universelle Turingmaschine) M simuliert. Widerspruch zum vorherigen Lemma! qed

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äß 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örige Tafel in geeigneter Weise als zusätzliche Information auf das Band gibt. Wir codieren also die Tafel und die Bandinschrift in zwei Wörtern und interpretieren die codierten Anweisungen für die codierte Bandinschrift.
Bem:
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.

Die Unlösbarkeit des Wortproblems für Semi-Thue-Systeme und Thue-Systeme

Grundlegende Definitionen und Bemerkungen

Bem:
Def: Gegeben sei ein n-elementiges Alphabet cal A. Auf W( cal A) definieren wir die zweistellige Verknüpfung · :
Für w 1 ,w 2 Î W( cal A) mit w 1 :{1,...,l} ® cal A und w 2 :{1,...,m} ® cal A für geignete l,m Î N sei
" i Î {1,...,l+m}   ( w 1 · w 2 ) ( i) := {
w 1 ( i) falls i £ m
w 2 ( i) sonst
.
Die Verknüpfung · nennt man auch Verkettung.
Bem: Sei cal A ein Alphabet. Dann bildet W( cal A) zusammen mit der Verkettung ein Monoid.
Kon: Das Verknüpfungszeichen der Verkettung wird häufig weggelassen.
Def: Sei cal A ein endliches Alphabet und cal S eine endliche und nicht leere Menge von geordneten Paaren von Worten aus W( cal A) . Dann heißt cal S Semi-Thue-System über cal A und die Elemente von cal S werden definierende Relationen genannt.
Auf W( cal A) wird mithilfe von cal S das zweistelliges Prädikat ® cal S erklärt:
® cal S ( w 1 ,w 2 ) := w 1 ® cal S w 2 := $ ( d 1 ,d 2 ) Î cal S $ u,v Î W( cal A) : ( w 1 =ud 1 v Ù w 2 = ud 2 v)
Man sagt dann auch, w 1 sei im Hinblick auf cal S unmittelbar überführbar in w 2 .
Def: Sei cal S ein Semi-Thue-System über cal A, dann wird auf W( cal A) mithilfe von cal S das zweistelliges Prädikat ~> cal S erklärt:
displaystyle ~> cal S ( w 1 ,w 2 ) := w 1 ~> cal S w 2 := $ n Î N $ u 0 ,...,u n Î W( cal A) : ( w 1 = u 0 Ù bigwedge i=1 n u i-1 ® cal S u i Ù u n = w 2 )
Man sagt dann auch, w 1 sei im Hinblick auf cal S überführbar in w 2 .
Bem: Sei cal S ein Semi-Thue-System über cal A, dann ist ~> cal S reflexiv und transitiv und es gilt:
 " w 1 ,w 2 ,u 1 ,u 2 Î W( a) : ( w 1 ~> cal S w 2 Ù u 1 ~> cal S u 2 ) Þ w 1 u 1 ~> cal S w 2 u 2 .
Bew: Die Reflexivität ergibt sich mit n=0 aus der Definition, die Transitivität durch Hintereinanderschreibung der beiden Ketten. Die letzte Aussage erhält man durch Nachweis von w 1 u 1 ~> cal S w 2 u 1 und w 2 u 1 ~> cal S w 2 u 2 mit der Transitivität.
Def: Sei cal S ein Semi-Thue-System über cal A und sei ( d 1 ,d 2 ) Î cal S. Dann heißt ( d 2 ,d 1 ) die inverse Regel zu ( d 1 ,d 2 ) .
Def: Sei cal S ein Semi-Thue-System über cal A und es gelte cal S = { ( d 2 ,d 1 ) |( d 1 ,d 2 ) Î cal S}, dann heißt cal S ein Thue-System.
Bem: Für ein Thue-System ist ® eine verträgliche Äquivalenzrelation, so daß die Faktorhalbgruppe gebildet werden kann.
Def: Sei cal S ein Thue-System über cal A und es gebe eine Abbildung s :cal A ® cal A mit der Eigenschaft s ° s = id cal A . Außerdem gelte {( a, s ( a) ) |a Î cal A} Í cal S. Dann heißt cal S zusammen mit s ein Gruppensystem über cal A. Das Wortproblem für ein Semi-Thue-System cal S ist das Problem, einen Algorithmus zu finden, der für beliebige Worte w,w' in endlich vielen Schritten entscheidet, ob w ® cal S w'.
Das allgemeine Wortproblem für Semi-Thue-Systeme ist die Frage nach einem Algorithmus, mit dem man für beliebige vorgegebene Semi-Thue-Systeme das Wortproblem lösen kann.

Unlösbarkeit des Wortproblems

Wir wollen nun zeigen, daß das allgemeine Wortproblem für Semi-Thue-Systme unlösbar ist. Dazu betrachten wir die zu eine Turingmaschine zugehörige Menge von Konfigurationsworten über einem geeigneten Alphabet und definieren ® durch den Begriff der Folgekonfiguration. Dann schließen wir von der Unlösbarkeit des Halteproblems auf die Unlösbarkeit des Wortproblems für Semi-Thue-Systeme.
Bem:
Def: M sei eine Turingmaschine über dem n-elementigen Alphabet cal A 0 ={a 1 ,...,a n }. M habe die Zustände 0,...,m ( m Î N ) , 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} ( m+n+6) -elementig, Großbuchstaben sollen die zu einem Symbol gehörigen Wörter bezeichnen (z.B: S:{1} ® cal A: 1 ñ® s). Das der Konfiguration K=( a,B,c) von M zugeordnete Konfigurationswort w K Î W( cal A) wird wie folgt ermittelt: Aus dem so bestimmten Konfigurationswort läßt sich die ursprüngliche Konfiguration (bis auf Parallelverschiebung des Rechenbandes) ablesen.
Wir konstruieren jetzt ein Semi-Thue-System cal S( M) über cal A wie folgt: Jeder Zeile ( i,a j ,v,k) von M wird eine oder mehrere Regeln von cal S ( M) zugeordnet. Die Regeln aus (d) dienen dazu, Endkonfigurationen in S zu überführen. Falls man das Wortproblem für Thue-Systeme nicht als unlösbar nachweisen will, genügen in (d) etwas kürzere Regeln, außerdem benötigt man dann auch die Symbole r und r' nicht mehr: Einer Zeile ( i,a i ,s,k) werden die definierenden Regeln
( Q i A j ,S)
(d')      ( A u S,S) für u=0,...,n
( SA t ,S) für t=1,...,n

zugeordnet. Dabei werden Endkonfigurationen in ESE überführt.

Wir definieren w * :=S und zeigen, daß folgendes gilt: Bem:
Satz: Bem:
(1) Ist K' eine Folgekonfiguration von K, so gilt w K ® cal S w K' .
(2) Ist K' eine Folgekonfiguration von K und gilt w K ® cal S w, so ist w=w K' .
(3) Ist K eine Endkonfiguration, so gilt w K ® cal S w * .
(4) w * ist kein Konfigurationswort.
Bew: Bem:
(1) Ergibt sich direkt aus den definierenden Regeln (a),(b),(b'), (c),(c').
(2) Wir nennen ein Wort aus W( cal A) ein Normalwort, wenn es genau einen der Buchstaben Q 0 ,...,Q m ,R,R',S enthält. Es gilt: Bem:
(5) Für jede Konfiguration K von M ist w K ein Normalwort.
(6) Ist w Î W( cal A) ein Normalwort und gilt für ein weiteres w' Î W( cal A) w ® cal S( M) w', so ist w' eindeutig bestimmt, denn auf jedes Normalwort kann höchstens eine der Regeln (a),(b),(b'),(c),(c'),(d) angewandt werden. Aus (5),(6) und (1) folgt (2).
(3) Die definierenden Regeln von (d) sorgen dafür, daß für jede Endkonfiguration K das Wort w K in w * überführt 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ält man nach mehrmaliger Anwendung schließlich 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ünfte Regel führt letztendlich auf S.
(4) Jedes Konfigurationswort enthält ein Wort Q k , also ist w * =S kein Konfigurationswort. Bem:
Lemma: M, angesetzt auf B in a, bleibt genau dann nach endlich vielen Schritten stehen, wenn für K=( a,B,c 0 ) gilt: w K ~> cal S( M) w * .
Bew: Bem:
`` Þ '': 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 ~> cal S( M) w K p und nach (3) w K p ~> cal S( M) w * , also (wegen der Transitivität) w K ~> cal S( M) w * .
`` Ü '': Es gelte w K ~> cal S( M) w * , dann gibt es eine Kette w K =w 0 ® cal S( M) w 2 ® cal S( M) ... ® cal S( M) w p ® cal S( M) w * . Angenommen M stoppt nicht nach endlich vielen Schritten, dann gibt es zu jedem i Î N eine i-te Konfiguration K i . Wir beweisen nun mit vollständiger Induktion, daß gilt: " i Î {0,...,p}: w K i =w K . II
I K 0 =K Þ w K 0 =w K
II Sei für 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 ® cal S( M) w K i+1 . Nach (2) folgt nun w K i =w i . Nun ist aber nach (4) w p =w * kein Konfigurationswort. Widerspruch. qed Bem:
Satz: Das allgemeine Wortproblem für Semi-Thue-Systeme ist unlösbar.
Bew: Wäre das allgemeine Wortproblem für Semi-Thue-Systeme lösbar, so könnte 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äre aber das Halteproblem lösbar. Widerspruch! qed
Satz: Sei U eine universelle Turingmaschine. Dann ist das Wortproblem für das Semi-Thue-System cal S( U) unlösbar.
Bew: Wenn das Wortproblem für cal S( U) lösbar wäre, so könnte man entscheiden ob U, angesetzt hinter ein beliebiges Wort, nach endlich vielen Schritten stehenbleibt. Dies ist jedoch für eine universelle Turingmaschine nicht möglich. Widerspruch! qed
Bem:
Def: Die Erweiterung von cal S( M) durch Hinzufügen der inversen definierenden Regeln zu einem Thue-System nennen wir cal T( M) .
Bem: Bem:
(7) Sei für w,w' Î W( cal A) ein Normalwort und w ® cal S( M) w' oder w' ® cal S( M) w so ist auch w' ein Normalwort, denn in jeder Regel von cal S( M) tritt in beiden Komponenten genau einer der Buchstaben Q 0 ,...,Q m ,R,R',S auf.
(8) Es gibt kein w Î W( cal S) , so daß w * ® cal S( M) w, denn auf w * ist keine definierende Regel von cal S( M) anwendbar.
Lemma: Für jedes Konfigurationswort w K gilt: w K ~> cal T( M) w * Û w K ~> cal S( M) w * .
Bew: Wir brauchen nur `` Þ '' zu zeigen.
Angenommen es gebe eine Konfiguration K für die gilt: w K ~> cal T( M) w * Ù Ø ( w K ~> cal S( M) w * ) . Dann gibt es eine Kette w K =w 0 ~> cal T( M) w 1 ~> cal T( M) ... ~> cal T( M) w p =w * . Nach (5) und (7) sind alle Worte w 0 ,...,w p Normalworte. Es gibt n.V. einen Index i<p für den gilt: w i+1 ~> cal S( M) w * aber nicht w i ~> cal S( M) w * . Die definierende Regel R aus cal T( M) , welche w i unmittelbar in w i+1 überführt, kann nicht in cal S( M) liegen, da sonst w i ~> cal S( M) w * folgen würde. Also liegt die zu R inverse Regel in cal S( M) und somit gilt: gilt: w i+1 ~> cal S( M) w i . Aus w i+1 ~> cal S( M) w * folgt die Existenz eines v Î W( cal A) mit w i+1 ® cal S( M) v. Es ist v not =w * , denn sonst würde w * =v ® cal S( M) w i im Widerspruch zu (8) folgen. Nun folgt aus w i+1 ~> cal S( M) w i und w i+1 ® cal S( M) v mit (6), daß v=w i . Daraus können wir jetzt w i ® cal S( M) w * schließen, da v ® cal S( M) w * . Widerspruch! qed
Satz: Das allgemeine Wortproblem für Thue-Systeme ist unlösbar und das Wortproblem eines einer universellen Turingmaschine zugeordneten Thue-Systems ist unlösbar.
Bew: Dieser Satz folgt direkt aus dem vorherigen Lemma und den beiden letzten Sätzen.
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. ( Hotz Einleitung)

Wir haben nun ein Thue-System mit unlösbarem Wortproblem konstruiert, ohne uns überhaupt darum zu kümmern, als wie kompliziert sich dieser Kalkül erweist. Man kann in einer ersten Approximation annehmen, daß die Kompliziertheit durch die Anzahl der Elemente des Alphabets und die Anzahl der definierenden Relationen charakterisiert wird. Sehr einfache Überlegungen zeigen, daß zu einem m-elementigen Thue-System über einem n-elementigen Alphabet mit unlösbarem Wortproblem auch ein m-elementiges Thue-System über einem 2-elementigen Alphabet mit unlösbarem Wortproblem existiert. Es entsteht die Aufgabe, ein Thue-System mit unlösbarem Wortproblem und der kleinsten Anzahl definierender Relationen zu finden. Es gibt Gründe anzunehmen, daß Thue-Systeme mit genau einer definierenden Relation ein lösbares Wortproblem haben. Andererseits wurde von G.S. Cejtin gezeigt, daß folgendes Thue-System cal T über dem Alphabet {a,b,c,d,e} ein unlösbares Wortproblem hat: cal H:={( ac,ca) ,( ad,da) ,( bc,cb) ,( bd,db) ,( eca,ce) , ( edb,de) ,( cca,ccae) } cal T entstehe aus cal H durch Hinzufügen der inversen Relationen. Ein Thue-System mit unlösbarem Wortproblem und weniger als 7 definierenden Relationen ist einstweilen (1974?) unbekannt. ( Malcev p. 229)


Novikov 1952, 1955 und unabhängig voneinander Boone und Britton 1958 zeigten, daß Dehn's Wortproblem im allgemeinen unlösbar ist. Außerdem stellten sie endliche Repräsentationen von Gruppen vor, für die es keinen Algorithmus gibt der für 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ß das Wortproblem in Halbgruppen mit Kürzungsregel im allgemeinen unlösbar ist. Zuerst benutzte Rabin 1958 und später Baumslag, Boone und B. H. Neumann, die Entdeckungen Novikovs dazu, praktisch alle Probleme die endliche Repräsentationen von Gruppen betreffen, als im allgemeinen unlösbar nachzuweisen.

Literaturverzeichnis

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


Michael Meyling