Das Wort-Problem und algorithmische (Un)entscheidbarkeit.

Letzte Woche hatten wir ja im Zusammenhang mit Abbildungsklassengruppen von Flächen (d.h. der Gruppe der stetigen und stetig umkehrbaren Abbildungen f:S–>S einer Fläche S) die Frage nach der ‘Nützlichkeit’ von Gruppen-Präsentationen aufgeworfen.

Gruppen-Präsentationen

Eine Präsentation einer Gruppe besteht aus einer Angabe von ‘erzeugenden’ Elementen der Gruppe (d.h. jedes andere Gruppenelement entsteht durch Multiplikationen aus diesen Erzeugern) und ‘Relationen’, also Gleichungen zwischen Produkten von Erzeugern.

Ein einfaches Beispiel wäre Z², die Gruppe der Paare ganzer Zahlen, mit 2 Erzeugern a=(1,0) und b=(0,1), und einer Relation a+b=b+a.

Auch für die Abbildungsklassengruppen von Flächen hatten wir letzte Woche Präsentationen (mit Dehn-Twists als erzeugenden Elementen) angegeben, die freilich viel komplizierter aussahen.

Wie nützlich sind solche Präsentationen? Wenn ich zwei Gruppenelemente als Produkte von Erzeugern dargestellt habe – kann ich entscheiden, ob es sich um unterschiedliche oder gleiche Elemente handelt? Im Fall von Z² ist das offensichtlich nicht schwer – man kann aus der angegebenen Relation leicht herleiten, daß, zum Beispiel, a+a+a+b+b=a+b+a+b+a ist, und man kann auch leicht beweisen, daß zum Beispiel a+a+a+b+b und a+a+b unterschiedliche Elemente sind.

In den Abbildungsklassengruppen ist es sicher nicht so offensichtlich zu entscheiden, wann Produkte von Dehn-Twists das selbe Gruppen-Element geben.

Algorithmische Unentscheidbarkeit

Das Problem, aus einer gegebenen Gruppen-Präsentation heraus zu entscheiden, wann zwei Gruppen-Elemente gleich sind, heißt das Wort-Problem und man weiß tatsächlich schon seit langem (seit 1958), daß das Wort-Problem nicht für beliebige Gruppen algorithmisch lösbar ist.

In gewisser Weise gehört diese algorithmische Unentscheidbarkeit sicher in eine Reihe mit z.B. dem Gödelschen Unvollständigkeitssatz und anderen Unbeweisbarkeitsphänomenen wie sie in Ruelle 12 diskutiert werden.

Glücklicherweise ist mit diesem Beweis der algorithmischen Unlösbarkeit des Wort-Problems für beliebige Gruppen die Geschichte aber noch nicht zu Ende.

Einzelfälle

Denn auch wenn es (bewiesenermaßen) keine solchen Algorithmen für alle Gruppen geben kann, gibt es sie im Einzelfall häufig doch.

Das erste Beispiel eines solchen Algorithmus für spezielle Gruppen hatte schon Max Dehn 1911 gefunden, nämlich für die Fundamentalgruppen von Flächen (TvF 31) – dabei benutzte er wesentlich die hyperbolische Geometrie der Flächen: geschlossene Flächen (mit Ausnahme der Sphäre und des Torus, deren Fundamentalgruppen aber leicht zu untersuchen sind) haben ja eine hyperbolische Metrik (TvF 69) und die Eigenschaften dieser ‘negativ gekrümmten’ Metrik benutzte Dehn bei der Konstruktion seines Algorithmus.

75 Jahre später wurden diese Ideen von Gromov aufgegriffen, der eine allgemeine Theorie der hyperbolischen Gruppen (‘negativ gekrümmten Gruppen’) entwickelte, für die man insbesondere das Wort-Problem algorithmisch lösen kann.

Sehr viele Gruppen sind hyperbolisch (in gewisser Weise sind fast alle Gruppen hyperbolisch) – die uns hier eigentlich interessierenden Abbildungsklassengruppen von Flächen allerdings nicht.
Ein Kriterium, mit dem man beweist, daß eine Gruppe nicht hyperbolisch ist, ist die Existenz von Untergruppen isomorph zu Z². In den Abbildungsklassengruppen gibt es aber viele Untergruppen isomorph zu Z²: man nehme zwei disjunkte Kurven auf der Fläche, dann kommutieren die Dehn-Twists an den Kurven, die von den beiden Dehn-Twists erzeugte Untergruppe ist also isomorph zu Z².

Es gibt aber eine noch allgemeinere Klasse von Gruppen, für die sich das Wort-Problem algorithmisch lösen läßt: die sogenannten automatischen Gruppen. Das sind, per Definition, Gruppen, die sich durch endliche Automaten beschreiben lassen, eine lesbare Einführung ist dieser Artikel von Farb.

Alle hyperbolischen Gruppen sind automatisch, es gibt aber noch mehr automatische Gruppen: insbesondere hat Lee Mosher 1995 bewiesen, daß die Abbildungsklassengruppen von Flächen automatisch sind. Man kann also doch algorithmisch entscheiden, ob verschiedene Hintereinanderausführungen von Dehn-Twists dieselbe Selbstabbildung der Fläche ergeben.

Teil 1, Teil 2, Teil 3, Teil 4, Teil 5, Teil 6, Teil 7 , Teil 8, Teil 9 , Teil 10 ,Teil 11, Teil 12, Teil 13, Teil 14, Teil 15, Teil 16, Teil 17, Teil 18, Teil 19, Teil 20, Teil 21, Teil 22, Teil 23, Teil 24, Teil 25, Teil 26, Teil 27, Teil 28, Teil 29, Teil 30, Teil 31, Teil 32, Teil 33, Teil 34, Teil 35, Teil 36, Teil 37, Teil 38, Teil 39, Teil 40, Teil 41, Teil 42, Teil 43, Teil 44, Teil 45, Teil 46, Teil 47, Teil 48, Teil 49, Teil 50, Teil 51, Teil 52, Teil 53, Teil 54, Teil 55, Teil 56, Teil 57, Teil 58, Teil 59, Teil 60, Teil 61, Teil 62, Teil 63, Teil 64, Teil 65, Teil 66, Teil 67, Teil 68, Teil 69, Teil 70, Teil 71, Teil 72, Teil 73, Teil 74, Teil 75, Teil 76, Teil 77, Teil 78, Teil 79, Teil 80, Teil 81, Teil 82, Teil 83, Teil 84, Teil 85, Teil 86, Teil 87, Teil 88, Teil 89, Teil 90, Teil 91, Teil 92, Teil 93, Teil 94, Teil 95, Teil 96, Teil 97, Teil 98, Teil 99, Teil 100, Teil 101, Teil 102, Teil 103, Teil 104, Teil 105, Teil 106, Teil 107, Teil 108, Teil 109, Teil 110, Teil 111, Teil 112, Teil 113, Teil 114, Teil 115, Teil 116, Teil 117, Teil 118, Teil 119, Teil 120, Teil 121, Teil 122, Teil 123, Teil 124, Teil 125, Teil 126, Teil 127, Teil 128, Teil 129, Teil 130, Teil 131, Teil 132, Teil 133, Teil 134, Teil 135, Teil 136, Teil 137