Zulassungsarbeit

1. Konstruktion endlich Präsentierbarer Gruppen mit unlösbarem Wortproblem anhand Simpson.
2. Interpretation einer HNN-Erweiterung als Loop anhand der Bass-Serre Theorie

Abstract

Das Wortproblem einer Gruppe $G=\text{wink}S\mid R$ ist die Frage, ob ein Wort aus dem Alphabet der Erzeuger $S$ die Identität ist. Das Wortproblem bei einer Formalen Sprache ist die Frage, ob ein Wort eines Alphabets $\Sigma$ in einer Formalen Sprache enthalten ist.

Das letztere Wortproblem ist in der Informatik gut erforscht. 19xx zeigte xxx, dass Typ-2 immer ein Lösbares Wortproblem haben. Man kann also in endlicher Zeit durch einen Algorithmus feststellen, ob ein Wort in einer Kontextfreien Sprache enthalten ist. 19xx zeigte xxx, dass Typ-0 Sprachen ein unlösbares Wortproblem haben. Demnach gibt es durch Grammatiken oder Turingmaschinen erzeugte Typ-0 Sprachen, bei denen es unmöglich ist festzustellen, ob ein bestimmtes Wort in der Sprache enthalten ist.

Die beiden Fragestellung sehen ziemlich ähnlich aus. Das wirft die Frage auf, ob man genannte Befunde aus der Informatik nutzen kann, um die Existenz einer Gruppe zu zeigen, die ein unlösbares Wortproblem hat.

In der folgenden Arbeit soll, gemäß dieser Analogie, eine leicht verständliche Anleitung gezeigt werden, mit der man eine Turingmaschine mit unlösbarem Wortproblem in eine Gruppe überführen kann, sodass die Eigenschaft des “Unlösbaren Wortproblems” erhalten bleibt.

Zusammenfassung

Der Beweis folgt dem Paper von Stephen G. Simpson. Wir werden erst eine Variation der Turingaschine definieren: Die Modulare Maschine. Dessen abstraktere Natur ermöglicht es später, Konfigurationen und Rechenschritte der Turingmaschine leichter algebraisch handzuhaben.

Ziel ist, eine Modulare Maschine mit unlösbarem Wortproblem in eine Gruppe mit ebenfalls unlösbarem Wortproblem umzuwandeln. Dazu definieren wir eine Gruppe, die für jede Konfiguration der Modularen Maschine eine Untergruppe besitzt. Diese Untergruppen sollen nicht zueinander konjugiert sein. Indem wir die Untergruppen durch HNN-Erweiterung konjugieren, bilden wir Verbindungen zwischen den Untergruppen. Diese erlauben uns Konfigurationsübergänge der Modularen Maschine in die Gruppe zu kodieren. Zuletzt wird gezeigt, dass die dadurch erhaltene Gruppe tatsächlich das “Wortproblem” der Maschine erhält, woraus folgt, dass es Gruppen mit unlösbarem Wortproblem gibt.

Um eine Intuition für HNN-Erweiterungen zu gewinnen, wird die Bass-Serre Theorie herangezogen. Es wird gezeigt, dass der Quotient einer Gruppenoperation auf einem Baum genau dann ein Loop ist, wenn die operierende Gruppe eine HNN-Erweiterung ist.

Es wird angenommen, dass der Lese Vorwissen zu Turingmaschinen und Freien Gruppen+Produkten hat

Kurze Definition Turingmaschine

Es wird davon ausgegangen, dass der Leser mit Turingmaschinen vertraut ist. Nichtsdestotrotz führen wir einige Begriffe ein. Damit sollen später Ähnlichkeiten zwischen der Turingmaschine und der Modularen Maschine ersichtlich gemacht werden.

Wir definieren Turingmaschinen nach (Turing (1936) in The Undecidable) als eine Menge von Konfigurationsübergängen der Form $(q_r,a_i,a_j,q_s,D)$ mit $q_r,q_s\in Q,a_i,a_j\in \Sigma ,D\in \{L,R\}$ Jeder Konfigurationsübergang gibt das Verhalten der Turingmaschine für eine bestimmte Konfiguration vor: Befindet sich eine Turingmaschine im Zustand $q_r$ und ließt das Zeichen $a_i$ auf dem Band, so soll sie das Zeichen $q_j$ auf das Band schreiben, in den Zustand $q_s$ wechseln und das Band entweder nach links oder nach rechts verschieben. Eine Konfiguration $(...u_2{u}_{1}qa{v}_1{v}_2...)$ umfasst die Information des Bandes $...u_2{u}_{1}a{v}_1{v}_2...$, die aktuelle Position auf dem Band und den aktuellen Zustand der Maschine $q$.

Gibt es für eine Konfiguration keinen anwendbaren Übergang, nennen wir die Konfiguration terminal. Ist eine Konfiguration nicht terminal, so soll es nur einen anwendbaren Konfigurationsübergang geben. Wir fordern also, für alle $q_r,a_i$, dass es maximal ein $(q_r,a_i,a_j,q_s,D)$ gibt.

Kurze Definition Turingmaschine

Es wird davon ausgegangen, dass der Leser mit Turingmaschinen vertraut ist. Nichtsdestotrotz führen wir einige Begriffe ein. Damit sollen später Ähnlichkeiten zwischen der Turingmaschine und der Modularen Maschine ersichtlich gemacht werden.

Wir definieren Turingmaschinen nach (Turing (1936) in The Undecidable) als eine Menge von Konfigurationsübergängen der Form $(q_r,a_i,a_j,q_s,D)$ mit $q_r,q_s\in Q,a_i,a_j\in \Sigma ,D\in \{L,R\}$ Jeder Konfigurationsübergang gibt das Verhalten der Turingmaschine für eine bestimmte Konfiguration vor: Befindet sich eine Turingmaschine im Zustand $q_r$ und ließt das Zeichen $a_i$ auf dem Band, so soll sie das Zeichen $q_j$ auf das Band schreiben, in den Zustand $q_s$ wechseln und das Band entweder nach links oder nach rechts verschieben. Eine Konfiguration $(...u_2{u}_{1}qa{v}_1{v}_2...)$ umfasst die Information des Bandes $...u_2{u}_{1}a{v}_1{v}_2...$, die aktuelle Position auf dem Band und den aktuellen Zustand der Maschine $q$.

Gibt es für eine Konfiguration keinen anwendbaren Übergang, nennen wir die Konfiguration terminal. Ist eine Konfiguration nicht terminal, so soll es nur einen anwendbaren Konfigurationsübergang geben. Wir fordern also, für alle $q_r,a_i$, dass es maximal ein $(q_r,a_i,a_j,q_s,D)$ gibt. **

Definition Modular Machine Eine Modulare Maschine ergibt sich durch Abstraktion einer Turingmaschine. Das Alphabet wird durch die Zahlen $0,1,...,n$ und die Menge der Zustände durch die Zahlen $n+1,...,m-1$ identifiziert. $0$ ist hierbei das leere Feld (Blank).

Eine Konfiguration einer Modularen Maschine kann analog zur vorherigen Definition durch ein $4$-Tupel $(u,a,q,v)$ beschrieben werden. Hierbei bezeichnen $u={\sum }_{i=0}^{\infty }{u}_1{m}^i\in \mathbb{N}$ bzw. $v={\sum }_{i=0}^{\infty }{u}_1{m}^i\in \mathbb{N}$ den Teil des Bandes links bzw. rechts des Zeigers, kodiert als $m$-äre Zahl. $a\in \{0,...,n\},q\in \{n+1,...,m-1\}$ beschreiben das aktuelle Zeichen des Bandes sowie den aktuellen Zustand der Maschine.

Abbildung zur Klarifikation des Bandes als märe Zahl

$(u,a,q,v)$ kann weiter in ein $2$-Tupel $(um+a,vm+q)\in {\mathbb{N}}^2$ oder $(um+q,vm+a)\in {\mathbb{N}}^2$ verkürzt werden. Welche der $2$-Tupelschreibweisen wir später nutzen wird damit zusammenhängen in welche Richtung das Band durch eine Konfigurationsänderung bewegt werden soll. Das wird im Folgenden einige Rechnungen zu erleichtern. Wir brauchen uns nicht für eine Schreibweise zu entscheiden, da man aufgrund $a<q$ rekonstruieren kann, ob der linke oder rechte Teil den aktuellen Zustand beschreibt.

Ein Konfigurationsübergang besteht aus dem gelesenen und zu schreibenden Zeichen $a,a^{\prime }\in \{0,...,n\}$, aus dem aktuellen und neuem Zustand $q,q^{\prime }\in \{n+1,...,m-1\}$ und aus der Bewegungsrichtung des Bandes $D\in \{L,R\}$. Indem wir $a^{\prime },q^{\prime }$ zu $c=a^{\prime }m+q^{\prime }$ zusammenfassen, lässt sich eine Konfiguration als $4$-Tupel $(q,a,c,D)$ darstellen.

Die Anwendung eines Konfigurationsübergangs $(q,a,a^{\prime },q^{\prime },L)$ auf die Konfiguration $(\alpha ,\beta )=(um+q,vm+a)$ ergibt die neue Konfiguration $(u{m}^2+a^{\prime }m+q,v)$. Siehe Abbildung:

Abbildung, um Linksbewegung zu zeigen

Genau ergibt die Anwendung eines Konfigurationsübergangs $(qa{a}^{\prime }{q}^{\prime }R)$ auf die Konfiguration $(\alpha ,\beta )=(um+a,vm+q)$ die neue Konfiguration $(u,v{m}^2+a^{\prime }m+q)$.

Wie bei der Turingmaschine bezeichnen wir eine Konfiguration, die man nicht in eine andere Konfiguration überführen kann als terminal. Ist eine Konfiguration nicht terminal, so soll es genau eine Überführung in eine andere Konfiguration geben.

Definition (Modulare Maschine): Eine Modulare Maschine besteht aus Zeichen-Zustandgröße $m\in \mathbb{N}$ sowie einer Menge von Konfigurationsübergängen der Form $(a,b,c^2,D)$ mit $0\le a,b<m$, $0\le c<m^2$, $D\in \{L,R\}$. Für jedes $a,b$ gibt es maximal ein $4$-Tupel, welches mit $a,b$ beginnt.

Es ist noch anzumerken, dass die Grenze zwischen Alphabet und Zuständen verschwimmt. oben benutze ich a, q für den Übergang aber unten a, b.

Sachen, die mal herauskopiert wurden

Kurze Definition Turingmaschine

Es wird davon ausgegangen, dass der Leser mit Turingmaschinen vertraut ist. Nichtsdestotrotz führen wir einige Begriffe ein. Damit sollen später Ähnlichkeiten zwischen der Turingmaschine und der Modularen Maschine ersichtlich gemacht werden.

Wir definieren Turingmaschinen nach (Turing (1936) in The Undecidable) als eine Menge von Konfigurationsübergängen der Form $(q_r,a_i,a_j,q_s,D)$ mit $q_r,q_s\in Q,a_i,a_j\in \Sigma ,D\in \{L,R\}$ Jeder Konfigurationsübergang gibt das Verhalten der Turingmaschine für eine bestimmte Konfiguration vor: Befindet sich eine Turingmaschine im Zustand $q_r$ und ließt das Zeichen $a_i$ auf dem Band, so soll sie das Zeichen $q_j$ auf das Band schreiben, in den Zustand $q_s$ wechseln und das Band entweder nach links oder nach rechts verschieben. Eine Konfiguration $(...u_2{u}_{1}qa{v}_1{v}_2...)$ umfasst die Information des Bandes $...u_2{u}_{1}a{v}_1{v}_2...$, die aktuelle Position auf dem Band und den aktuellen Zustand der Maschine $q$.

Gibt es für eine Konfiguration keinen anwendbaren Übergang, nennen wir die Konfiguration terminal. Ist eine Konfiguration nicht terminal, so soll es nur einen anwendbaren Konfigurationsübergang geben. Wir fordern also, für alle $q_r,a_i$, dass es maximal ein $(q_r,a_i,a_j,q_s,D)$ gibt.

Definition Modular Machine Eine Modulare Maschine ergibt sich durch Abstraktion einer Turingmaschine. Das Alphabet wird durch die Zahlen $0,1,...,n$ und die Menge der Zustände durch die Zahlen $n+1,...,m-1$ identifiziert. $0$ ist hierbei das leere Feld (Blank).

Eine Konfiguration einer Modularen Maschine kann analog zur vorherigen Definition durch ein $4$-Tupel $(u,a,q,v)$ beschrieben werden. Hierbei bezeichnen $u={\sum }_{i=0}^{\infty }{u}_1{m}^i\in \mathbb{N}$ bzw. $v={\sum }_{i=0}^{\infty }{u}_1{m}^i\in \mathbb{N}$ den Teil des Bandes links bzw. rechts des Zeigers, kodiert als $m$-äre Zahl. $a\in \{0,...,n\},q\in \{n+1,...,m-1\}$ beschreiben das aktuelle Zeichen des Bandes sowie den aktuellen Zustand der Maschine.

Abbildung zur Klarifikation des Bandes als märe Zahl

$(u,a,q,v)$ kann weiter in ein $2$-Tupel $(um+a,vm+q)\in {\mathbb{N}}^2$ oder $(um+q,vm+a)\in {\mathbb{N}}^2$ verkürzt werden. Welche der $2$-Tupelschreibweisen wir später nutzen wird damit zusammenhängen in welche Richtung das Band durch eine Konfigurationsänderung bewegt werden soll. Das wird im Folgenden einige Rechnungen zu erleichtern. Wir brauchen uns nicht für eine Schreibweise zu entscheiden, da man aufgrund $a<q$ rekonstruieren kann, ob der linke oder rechte Teil den aktuellen Zustand beschreibt.

Ein Konfigurationsübergang besteht aus dem gelesenen und zu schreibenden Zeichen $a,a^{\prime }\in \{0,...,n\}$, aus dem aktuellen und neuem Zustand $q,q^{\prime }\in \{n+1,...,m-1\}$ und aus der Bewegungsrichtung des Bandes $D\in \{L,R\}$. Indem wir $a^{\prime },q^{\prime }$ zu $c=a^{\prime }m+q^{\prime }$ zusammenfassen, lässt sich eine Konfiguration als $4$-Tupel $(q,a,c,D)$ darstellen.

Die Anwendung eines Konfigurationsübergangs $(q,a,a^{\prime },q^{\prime },L)$ auf die Konfiguration $(\alpha ,\beta )=(um+q,vm+a)$ ergibt die neue Konfiguration $(u{m}^2+a^{\prime }m+q,v)$. Siehe Abbildung:

Abbildung, um Linksbewegung zu zeigen

Genau ergibt die Anwendung eines Konfigurationsübergangs $(qa{a}^{\prime }{q}^{\prime }R)$ auf die Konfiguration $(\alpha ,\beta )=(um+a,vm+q)$ die neue Konfiguration $(u,v{m}^2+a^{\prime }m+q)$.

Wie bei der Turingmaschine bezeichnen wir eine Konfiguration, die man nicht in eine andere Konfiguration überführen kann als terminal. Ist eine Konfiguration nicht terminal, so soll es genau eine Überführung in eine andere Konfiguration geben.

Definition (Modulare Maschine): Eine Modulare Maschine besteht aus Zeichen-Zustan