Zum Verständnis noch ein kurzes Beispiel. Nehmen wir an, wir wollen eine Turingmaschine beschreiben, welche zwei Bits miteinander addieren kann, und zwar unter Beachtung eines eventuellen Übertrags (wir erinnern uns). Wir definieren also eine Turingmaschine mit den folgenden Eigenschaften, wobei wir annehmen, dass die beiden zu addierenden Bits als Eingabewort auf dem Band der Turingmaschine nebeneinander liegen:
- Q = { start, a, b, c, d, e, f, g, end }
- Γ = { 0, 1 }
- Σ = { 0, 1 }
- b = 0
- δ: siehe unten
- q0 = a
- qf = end
Für die Überführungsfunktion δ wollen wir die folgende Tabelle definieren:
| aktueller Zustand |
aktuelles Zeichen |
→ | neuer Zustand |
neues Zeichen |
Richtung |
|---|---|---|---|---|---|
| start | 0 | → | a | 0 | R |
| start | 1 | → | b | 1 | R |
| a | 0 | → | c | 0 | R |
| a | 1 | → | d | 1 | R |
| b | 0 | → | d | 0 | R |
| b | 1 | → | e | 1 | R |
| c | – | → | f | 0 | R |
| d | – | → | g | 0 | R |
| e | – | → | f | 1 | R |
| f | – | → | end | 0 | 0 |
| g | – | → | end | 1 | 0 |
Für wen die Tabelle jetzt noch nicht wirklich verständlich ist, ein konkretes Anwendungsbeispiel (ohne Tabelle, sondern im Wortlaut). Nehmen wir an, wir wollen die beiden Bits “0” und “1” miteinander addieren; wir wir wissen, wäre das Ergebnis hierfür “01”. Auf dem Band der Turingmaschine befinden sich zu Beginn also die beiden Bits “0” und “1” in benachbarten Zellen; der Schreib-/Lesekopf befindet sich auf der “0” und die Maschine befindet sich im Zustand “start”. Nun beginnt die Verarbeitung; laut der Tabelle müssen wir entsprechend der ersten Zeile handeln, da wir im Zustand “start” sind und eine “0” auf dem Band lesen. Die Maschine geht also in den Zustand “a” über, schreibt eine “0” auf’s Band (ändert damit also nichts) und bewegt den Schreib-/Lesekopf um eine Position nach rechts (wo die “1” der Eingabe steht). Nun befindet sie sich im Zustand “a” und liest die “1” auf dem Band (entspricht der 4. Zeile der Tabelle); sie geht also in den Zustand “d” über, schreibt eine “1” auf das Band (ändert also nichts) und bewegt den Schreib-/Lesekopf wieder eine Stelle nach rechts. In Zustand “d” spielt es keine Rolle, welches Zeichen gelesen wird (tatsächlich steht an dieser Stelle auch noch keine relevante Information); die Maschine schreibt in jedem Fall eine “0” auf das Band, wechselt in den Zustand “g” und bewegt den Schreib-/Lesekopf eine Stelle nach rechts. Im Zustand “g” wird nun wieder unabhängig vom aktuellen Zeichen eine “1” geschrieben und in den Endzustand “end” gewechselt, in welchem nichts weiter passiert. Auf dem Band finden sich nun also von links nach rechts die Zeichen “0”, “1” (das war die Eingabe), “0”, “1” (das ist das Ergebnis).
So, damit wissen wir, was eine Turingmaschine nun eigentlich ist und wie sie arbeitet. Man sieht auch, dass sie nicht wirklich effizient ist, da die Lösung größerer Probleme sehr viele Zustände erfordern würde. Für die theoretische Informatik spielt das allerdings keine Rolle, da sie mit der Turingmaschine lediglich Probleme abstrakt, das heißt ohne einen detaillierten Lösungsweg beschreiben möchte. Insbesondere geht es auch darum, ob sich ein Problem überhaupt lösen lässt und wenn ja, wie lange es dauern würde – aber das sind Betrachtungen zur Berechenbarkeit und Komplexität, welche ich in einem anderen Artikel handhaben möchte. Hier soll dagegen noch die Frage von Leser Michael beantwortet werden; er möchte wissen, was der Begriff “Turing-Vollständigkeit” genau bedeutet und wie man zeigt, dass etwas Turing-vollständig ist. Zum Glück lässt sich das ziemlich leicht erklären.
Eine konkret definierte Turing-Maschine berechnet ja im Grunde eine Funktion, welche einen Eingabeparameter – die Problemstellung – auf eine Ausgabe – die Lösung des Problems – abbildet. Der Begriff “Turing-Vollständigkeit” wird meist auf Programmiersprachen angewandt und bedeutet nun, dass die Programmiersprache all die Funktionen berechnen können muss, welche eine Turing-Maschine auch berechnen kann (wenn man die Forderung nach unendlich viel Speicher in der Entsprechung des unendlich langen Bandes einmal außen vor lässt). Konkret heißt das: wenn jedes Problem, dass mit der Turing-Maschine gelöst werden kann, auch mit einer Programmiersprache lösbar ist, so ist die Sprache Turing-vollständig. Man weiß von einer Turing-vollständigen Sprache also, dass mit ihrer Hilfe alle Probleme gelöst werden können, die auch mit anderen Turing-vollständigen Sprachen lösbar sind. Der Begriff lässt sich aber nicht nur auf Programmiersprachen, sondern auf ganze Systeme (wobei ein System praktisch alles sein kann) anwenden; insbesondere können auch Computerarchitekturen Turing-vollständig sein. So ist etwa von der von-Neumann-Architektur (die Architektur, die unseren heutigen Computern zugrunde liegt) bekannt, dass sie Turing-vollständig ist. Man kann also auch sagen, dass mit einer Turing-vollständigen Sprache alle Probleme beschrieben und gelöst werden können, die ein normaler Computer überhaupt lösen kann. Umgekehrt gilt natürlich, dass eine nicht-Turing-vollständige Sprache eben nicht alle Probleme lösen kann (bekannte Beispiele hierfür sind reguläre Ausdrücke und Zellenformeln in Tabellenkalkulationen). Um zu zeigen, dass ein System Turing-vollständig ist, reicht es übrigens zu zeigen, dass man mit diesem System jede beliebige Turingmaschine emulieren kann.
Kommentare (20)