Bisher habe ich Themen aus den Gebieten der Grundlagen-Informatik, der technischen Informatik, der (hardwarenahen) Programmierung und der Algorithmen besprochen; nicht erwähnt wurde aber (unter anderem) die theoretische Informatik; diesen Missstand möchte ich heute beseitigen und das Wunschthema von Leser Michael beantworten: er hat eine kurze Abhandlung über die Turing-Vollständigkeit erbeten. Nun denn, auf geht’s.
Um die Turing-Vollständigkeit zu klären, muss vorher ein neues Konzept eingeführt werden, welches auch ein zentraler Bestandteil der theoretischen Informatik ist: das der Turingmaschine (benannt nach Alan Turing). Eine Turingmaschine ist (entgegen ihrem Namen) ein rein hypothetisches Modell und keine echte Maschine; sie kann auch nicht nachgebaut werden – warum, werden wir gleich sehen. Das Konzept der Turingmaschine lässt sich sowohl informell als auch formell relativ gut beschreiben; der Einfachheit halber folgt hier zuerst die informelle Beschreibung und dann – damit es komplett ist – die formale.
Eine Turingmaschine besteht im Kern aus zwei wichtigen Elementen: einem in einzelne Zellen unterteilten Speicherband, bei welchem jede Zelle ein beliebiges Zeichen aus einer Menge definierter Zeichen speichern kann, und einem Schreib-/Lesekopf, der sich auf diesem Band nach rechts und links bewegen, den Inhalt einer Zelle lesen und mit einem neuen Inhalt überschreiben kann. Für das Speicherband wird angenommen, dass es unendlich lang ist – daher die Unmöglichkeit, eine derartige Maschine zu bauen. Die auf das Band schreibbaren Zeichen können beliebige Zeichen sein, die lediglich bei der Definition der Turingmaschine als Menge, dem sogenannten Alphabet, angegeben werden müssen. Ein immer schreibbares Zeichen ist das leere Zeichen (welches einfach “nichts” repräsentiert). Eine entsprechende grafische Darstellung einer Turingmaschine könnte etwa so aussehen (Quelle: Wikipedia):
Eine Turingmaschine arbeitet folgendermaßen: zu Beginn befindet sich auf dem Band eine zu verarbeitende Eingabe, das sogenannte Eingabewort, welches einfach aus einer Folge von Zeichen in aufeinanderfolgenden Zellen besteht (die möglichen Eingabezeichen sind eine Teilmenge des Alphabetes der Maschine); der Schreib-/Lesekopf befindet sich am Anfang des Eingabewortes. Im weiteren folgt eine feste Abfolge von Aktionen: der Schreib-/Lesekopf liest das Zeichen an seiner aktuellen Position, überschreibt es mit einem neuen Zeichen (welches auch das alte sein kann) und bewegt sich eine Stelle nach links oder rechts. Welches Zeichen geschrieben und in welche Richtung sich der Schreib-/Lesekopf bewegt, hängt vom internen Zustand der Turingmaschine ab. Der Zustand der Turingmaschine ist am besten vergleichbar mit dem Zustand eines technischen Gerätes, etwa eines Brotbackautomaten. Der kennt auch verschiedene Zustände, wie zum Beispiel “kneten”, “gehen lassen”, “backen” und ähnliches, zwischen denen er nach einem bestimmten Muster – dem Programm – wechselt. Eine Turingmaschine kann ganz analog verschiedene Zustände annehmen; abhängig vom aktuellen Zustand und dem aktuell gelesenen Zeichen wird dann wie bereits beschriebe ein neues Zeichen geschrieben und der Schreib-/Lesekopf nach rechts oder links bewegt. Gleichzeitig geht die Turingmaschine in einen neuen Zustand über (welcher auch dem alten entsprechen kann). Die Turingmaschine beginnt ihre Arbeit immer in einem Anfangszustand und endet, sobald ein vorher festgelegter Endzustand erreicht wird. Durch die Angabe, welches Zeichen bei einer bestimmten Eingabe geschrieben, wohin sich der Kopf bewegen und in welchen Zustand gewechselt werden soll, lässt sich ein beliebiges Verhalten der Maschine beschreiben. Bei geeigneter Wahl des Alphabetes kann man – mit einiger Vorstellungskraft – jedes beliebige Problem lösen (ein kleines Beispiel folgt nach der formalen Definition).
Ich hoffe, die Erklärung war jetzt einigermaßen verständlich, da nun die formale Definition der Maschine folgt. Eine Turingmaschine lässt sich als 7-Tupel, also als Zusammenschluss von 7 verschiedenen Elementen darstellen. Eine mögliche Darstellung sieht etwa so aus (bitte nicht ob der vielen seltsamen Zeichen erschrecken, eine Erklärung folgt gleich):
M = ( Q, Γ, Σ, b, δ, q0, qf )
Und hier die versprochene Erklärung der Zeichen:
- M: bezeichnet die Turingmaschine selber
- Q: die Menge aller Zustände; jedem Zustand wird ein Symbol oder eine Bezeichnung zugeordnet, damit er später eindeutig identifiziert werden kann
- Γ: das Alphabet aller möglichen Zeichen, die auf das Band geschrieben werden können
- Σ: das Alphabet der möglichen Eingabezeichen; es gilt Σ ⊆ Γ \ {b}
- b: das leere Zeichen; es gilt b ∈ Γ
- δ: die Überführungsfunktion; formal gilt: δ: ( Q \ { qf } ) × Γ → Q × Γ × { L, 0, R }
- q0: der Anfangszustand der Programmabarbeitung; es gilt q0 ∈ Q
- qf: der Endzustand, bei welchem die Programmabarbeitung abbricht; es gilt qf ∈ Q
Das einzige Mysterium dürfte eigentlich nur (für die Nichtmathematiker unter den Lesern) die Überführungsfunktion δ sein. Im Detail besagt sie aber nur, dass ein Tupel bestehend aus dem (aktuellen) Zustand und dem (aktuell gelesenen) Zeichen abgebildet werden soll auf ein Tupel bestehend aus einem Zustand (in welchen gewechselt werden soll), einem Zeichen (welches an der aktuellen Position geschrieben werden soll) und einer Richtung (in welche sich der Schreib-/Lesekopf bewegen soll).
Kommentare (20)