Was können Computer nicht?

Alle bekannten Computerbauweisen (auch Quantencomputer) können nur berechnen, was eine Turingmaschine mit beliebig viel Zeit und Speicher berechnen könnte. Doch Turing bewies, dass einige Probleme unlösbar sind, also mit Turingmaschinen nicht berechenbar sind - und daher auch mit jedem Computer. Das zeigte er mit einem Problem über Turingmaschinen selbst, das man Halteproblem nennt.

Das Halteproblem

Wann wird eine Turingmaschine anhalten? Wenn sie nur einen Zustand (Zustand o) hat, dann braucht sie nur zwei Regeln: Was sie tun muss, wenn sie eine o oder eine i liest. Auf verschiedene Weisen können diese Regeln zu verschiedenen Ergebnissen führen, je nachdem, wie die Regel für i formuliert ist:

  • • Die o-Regel verlangt, o unverändert zu lassen und einen Schritt nach rechts zu gehen, bis eine Ziffer i gefunden wird, und dann anzuhalten. Die Maschine hält und gibt das Ergebnis aus.
  • • Aber eine Turingmaschine könnte sich in einer endlosen Schleife befinden: Wählt man die Regel »Wenn i gelesen wird, schreibe i und gehe nach links«, dann würde die Maschine zur vorherigen o zurückgehen, dann beim nächsten Ticken der Uhr wieder (nach der o-Regel) zur i und diese beiden Schritte endlos wiederholen.
  • • Es ist auch einfach, eine Turingmaschine zu definieren, die niemals anhalten wird. Ändert man die i-Regel zu »Wenn i gelesen wird, schreibe o und gehe nach links«, dann geht die Maschine zur vorherigen o zurück und dann wieder nach vorwärts nach rechts, aber diesmal steht dort auch eine o, und sie geht weiter nach rechts bis zur nächsten i. Die Maschine wird alle Ziffern i in o umwandeln und für immer nach rechts im Unendlichen verschwinden.

Maschine H

Alan Turing selbst fragte: Gibt es einen Algorithmus, der, wenn man ihm das Programm einer beliebigen Turingmaschine und deren Eingabedaten gibt, die Antwort o ausgibt, falls diese Maschine niemals anhält und eine Antwort gibt?

Angenommen, ein solcher Algorithmus existiert - dann gibt es eine Turingmaschine, die ihn ausführt. Außerdem gäbe es eine Maschine, die testen könnte, ob eine beliebige Turingmaschine nicht anhält, wenn sie ihr eigenes Programm als Eingabe erhält. Nennen wir diese Maschine H und geben Daten ein, mit denen H dann und nur dann anhält, wenn die Eingabedaten dem Programm einer Turingmaschine entsprechen, die nicht anhält, wenn ihre Eingabe ihr eigenes Programm ist.

Was passiert nun, wenn wir H sein eigenes Programm geben?

Wenn es anhält, dann ist es ein Beispiel für eine Turingmaschine, die anhält, wenn sie ihr eigenes Programm als Eingabe erhält - aber H war doch so konstruiert, dass es nicht anhalten soll, wenn es das Programm einer solchen Maschine als Eingabe hat!

Wenn H aber nicht anhält, dann ist H eine Maschine, die mit ihrem eigenen Programm als Eingabedaten nicht anhält. Aber H sollte mit dem

H-Programm anhalten, weil es gerade dafür gebaut war, solche Maschinen zu erkennen.

In beiden Fällen kommt es zum Widerspruch. Eine unmögliche Situation wie diese sagt Mathematikern, dass ihre Annahmen falsch waren. Die Konstruktion der imaginären Turingmaschine H, die überhaupt nicht existieren kann, war also sehr schlau. Sie beweist, dass es keine Turingmaschine geben kann, die berechnen kann, ob jede beliebige Turingmaschine mit jeder beliebigen Eingabe nicht anhält. Und wenn diese Frage von einer Turingmaschine nicht entschieden werden kann, dann ist sie auf jedem beliebigen heute vorstellbaren Computer unberechenbar.

Einfach gesagt: Kein Computer kann dieses Problem lösen!

Unendliche Zahlen

Die Anzahl möglicher Programme und Turingmaschinen ist unendlich, aber weil man jedes Programm in eine einzige riesige Binärzahl umwandeln kann, nennen Mathematiker die Menge aller möglichen Programme »abzählbar unendlich«, weil man sie, der Größe nach geordnet, auflisten kann.

Doch es gibt viel größere Unendlichkeiten, etwa die unendlich vielen Dezimalzahlen mit unendlich vielen Dezimalstellen - diese Menge nennt man die »reellen Zahlen«. Es gibt reelle Zahlen, deren Ziffern nicht berechnet werden können.

Beispielsweise kann die Zahl Pi (die Kreiszahl, die du zur Berechnung des Umfangs eines Kreises brauchst und die du vielleicht als ungefähr 3,142 kennst) prinzipiell auf beliebig viele Dezimalstellen genau von einem Computer berechnet werden. Die ersten Stellen sind 3,141592653

und ein Computer hat einige Billionen Stellen berechnet. Die meisten reellen Zahlen können aber nicht auf diese Weise erzeugt werden: Sie sind grundsätzlich unberechenbar. Auch ein Computer wäre damit überfordert!

Die Zukunft

Einige Theoretiker spekulieren, dass zukünftige neue Arten von Computern mit uns noch unbekannter Physik mehr berechnen können als Turingmaschinen und dass sich das menschliche Gehirn (der ursprüngliche »Computer«) als eine solche noch unbekannte Computerart heraus stellen könnte.

Es gibt keine Einigkeit darüber, ob das menschliche Gehirn durch eine hinreichend komplizierte Turingmaschine beschrieben werden kann.

 
Quelle
< Zurück   INHALT   Quelle   Weiter >