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):

i-0945cfa57335242b218d867b81c9c451-301px-Turingmaschine.svg.png

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).

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.

Und wer sich jetzt fragt, wozu man Turingmaschinen überhaupt benötigt: sie sind wie gesagt ein rein hypothetisches Konzept der theoretischen Informatik, welches dazu benutzt wird, verschiedene Eigenschaften von Problemen und Programmiersprachen zu diskutieren. Aber dazu schreibe ich in einem späteren Artikel noch etwas.

Kommentare (20)

  1. #1 rolak
    Oktober 12, 2011

    So exotisch Turing-Maschinen zu sein scheinen – die Beschäftigung mit ihnen kann durchaus spaßig sein. Sich einen 5-zuständigen fleißigen Biber zu erprobieren kann suchtgefährdend sein 😉

  2. #2 Sven Türpe
    Oktober 12, 2011
  3. #3 Marcus Frenkel
    Oktober 12, 2011

    @Sven Türpe
    Netter Link, danke. Auch wenn er meiner Aussage, dass Turingmaschinen nicht umsetzbar sind, etwas widerspricht. Aber man kann ja anführen, dass das im Link keine echte Turingmaschine ist. 😉

  4. #4 Timmorn
    Oktober 12, 2011

    Das Paper zur Turingmaschine wurde übrigens ersteinmal abgelehnt – mit einer großartigen Begründung:
    http://www.fang.ece.ufl.edu/reject.html

  5. #5 Stefan W.
    Oktober 12, 2011

    wir wir wissen, wäre das Ergebnis hierfür “10”.

    Korrekturen: **wie** wir wissen wäre das Ergebnis hierfür **”1″**.

    Beim Komma bin ich mir nicht sicher. Aber weil es auch später wiederholt wird, dass das Ergebnis der Addition von 0 und 1 10 sei, wo ich immer den Eindruck hatte, dass das das Ergebnis der Addition von 1 und 1 sei, frage ich nochmal nach – vielleicht habe ich es ja nicht verstanden.

  6. #6 Sven Türpe
    Oktober 12, 2011

    Noch ein Tipp für Bücherfreunde: The Annotated Turing geht Satz für Satz durch Turings Paper und ergänzt es um Erläuterungen, Beispiele und historische Betrachtungen.

  7. #7 schlappohr
    Oktober 12, 2011

    Im Studium haben wir die ganze Berechenbarkeitstheorie anhand der “mü”-Rekursion aufgezogen. Die Klasse dieser Funktionen ist äquivalent zur Klasse der Turing-berechenbaren Funktionen, kommt aber ohne das theoretische Modell einer Maschine aus, sondern basiert auf einer handvoll (ich glaube 3 oder 4) Grundfunktionen. Irgendwie fand ich die u-Rekursivität griffiger als Turingmaschinen, aber das ist vermutlich Geschmackssache 🙂

  8. #8 Marcus Frenkel
    Oktober 12, 2011

    @Stefan W.
    Danke für den Hinweis; natürlich kommt “01” heraus und nicht “10”. Man sollte doch keine Artikel schreiben, wenn man nebenher eigentlich ganz andere Dinge macht. Ich habe es im Artikel einmal ohne weitere Markierung korrigiert (man vergebe mir), damit die Tabellen nicht ganz so wüst aussehen.

  9. #9 Stefan W.
    Oktober 13, 2011

    Ich habe es im Artikel einmal ohne weitere Markierung korrigiert (man vergebe mir),

    Keine Ursache. Flüchtigkeitsfehler gross zu dokumentieren bringt m.E. wenig.

  10. #10 BreitSide
    Oktober 13, 2011

    xxx

  11. #11 Gustav
    Oktober 14, 2011

    Das Band muß betreffs der Länge doch nur die Bedingung erfüllen, dass der Lese/Schreibkopf bei einer Berechnung nicht an das Ende stößt.

    Nur um zu zeigen, dass eine Turingmaschine eben nicht alle Probleme lösen kann, sondern nur alle Probleme einer bestimmten Klasse von berechenbare Funktionen (Turing-Berechenbarkeit), brauche ich ein endloses Band.

    Diese Probleme sind aber nur ein “Anwendungsgebiet” der Turingmaschine. Wenn ich damit nur zeigen will, dass eine Turingmaschine eine (Turing-) berechenbare Funktion lösen kann, benötige ich doch kein endloses Band (es muß nur solange sein, dass die Berechnung ungehindert ausgeführt wird).

    Oder irre ich da?

  12. #12 Gustav
    Oktober 14, 2011

    Ach ja, The LEGO Turing Machine: http://www.youtube.com/watch?v=cYw2ewoO6c4

    😉

  13. #13 rolak
    Oktober 14, 2011

    Leider in D-Land wg A-Team gesperrt, da war der militärische Geheimdienst schneller, Gustav 😉
    Da hinten gibt es die ganzen Daten und zum clip-Anschauen reicht es schon, den Hintern bedeckt zu lassen.

  14. #14 Marcus Frenkel
    Oktober 14, 2011

    @Gustav
    Im Prinzip ist das richtig – für das Lösen eines bestimmten Problems muss das Band nur so lang sein, dass das Problem “draufpasst”. Allerdings gibt es ja auch Probleme, die nicht gelöst werden können, oder deren Lösung “unendlich lange” dauert – z.B. die Berechnung von Pi. Für derartige Probleme wird ein unendlich langes Band (und unendlich viel Zeit) benötigt; möchte man zudem eine universelle Turingmaschine konstruieren, muss man auch diese Probleme berücksichtigen und benötigt daher auch dafür ein unendlich langes Band. Daher wird im Allgemeinen gleich die Aussage getroffen, dass man für Turingmaschinen “an sich” ein unendlich langes Band braucht; aber ja, für spezielle Maschinen ist natürlich kein unendlich langes notwendig.

  15. #15 7tupel
    Oktober 14, 2011

    Da fühlt man sich doch gleich wieder in die Theorie Vorlesung an der Uni zurückversetzt 😉
    Für den einen oder anderen ist es vielleicht noch interessant zu wissen, dass man ausgehend von der “normalen” Turingmaschine auch welche konstruieren kann, die mehr als eine Spur auf dem Band haben, d.h. man kann mehrere Zeichen parallel lesen/schreiben. Und natürlich noch die Mehrbandmaschinen, die mehrere Bänder und Schreib-Lese Köpfe haben. Nicht zu vergessen die nicht-deterministischen Maschinen…
    Gibt es dazu später noch einen Artikel? Denke das wäre eine interessante Erweiterung für die meisten Leser.

  16. #16 Marcus Frenkel
    Oktober 14, 2011

    @7tupel
    Wenn mir jemand eine Mail mit seinen Wünschen schreibt (so dass ich sie gut sichtbar im Posteingang belassen kann), dann kommt da bestimmt noch einmal etwas. 😉

  17. #17 Stefan W.
    Oktober 14, 2011

    Allerdings gibt es ja auch Probleme, die nicht gelöst werden können, oder deren Lösung “unendlich lange” dauert – z.B. die Berechnung von Pi.

    Interessanter aber, im Zusammenhang mit Turing, sind doch die Probleme, bei denen man vorher nicht weiß, ob sie terminieren werden. Dass die Pi-Berechnung nicht terminieren wird, dass weiß man ja vorher.

  18. #18 Marcus Frenkel
    Oktober 14, 2011

    @Stefan W.
    Richtig. Die Pi-Berechnung war jetzt auch nur ein Beispiel, wobei sie sich insofern von vielen der nicht-endenden Probleme unterscheidet, als dass immerhin bekannt ist, dass es eine Lösung gibt. Bei vielen Problemen, wo vorher nicht bekannt ist, ob sie terminieren, weiß man ja auch gar nicht, ob überhaupt eine Lösung existiert.

  19. #19 engywuck
    Oktober 14, 2011

    @Timmorn: dass der Text hinter deinem Link eine Satire ist weisst du?

  20. #20 rolak
    Oktober 14, 2011