Die fleißigen Biber der Informatik

Welches Adjektiv beschreibt einen Informatiker am besten? „Informatiker sind faul“ — meinte letztens ein guter Freund (seinerseits ebenfalls Informatiker) zu mir. Was er damit sagen wollte? In erster Linie, dass Informatiker lieber einem Computer beibringen, ein Problem zu lösen, als es selbst zu lösen. Da stellt sich die Frage: Kann man alle Probleme mit dem Computer lösen?

Comic von xkcd (CC BY-NC 2.5)

Um diese Frage zu beantworten gibt es in der Informatik das Konzept der Berechenbarkeit. Ein Problem ist dann berechenbar (also von einem Computer lösbar), wenn man dafür einen Algorithmus schreiben kann. Um zu testen, ob ein Problem berechenbar ist, gibt es verschiedene Modelle. Eines davon ist die Turing-Maschine, von der ich euch hier schon berichtet habe. Turing-Maschinen sind nicht real existierend, sondern ein Konzept, welches man sich folgendermaßen vorstellen kann: man hat ein unendlich langes Tape oder einen unendlich langen Streifen Papier, der in aneinandergereihte, einzelne Felder unterteilt ist. Außerdem hat die Maschine einen Lese-/Schreibkopf, den man entlang des Bandes bewegen kann. Eine Turing-Maschine hat drei Funktionen: Lesen, Schreiben und den Kopf bewegen.

Für jedes Problem, das berechenbar ist, kann man sich eine solche Maschine ausdenken, die nur durch diese drei Funktionen das Problem lösen kann und irgendwann anhält. Der Kopf kann dabei verschiedene Zustände annehmen. Für jeden Zustand gibt es eine Anweisung, was die Maschine als nächstes tut. Diese Anweisung besteht aus „Lesen, Schreiben, Kopf-Bewegen, Zustand ändern“. Zu Beginn ist das Band mit Nullen gefüllt. Eine mögliche Anweisung für Zustand 1 wäre „wenn eine Null auf dem Band steht, schreibe eine Eins, rücke ein Feld nach rechts, gehe in Zustand 2“. Die Beschreibung dieser Zustände und der durchzuführenden Aktionen, entspricht dem Algorithmus zur Lösung des Problems. Wichtig ist dabei, dass es einen Haltezustand gibt, in den die Maschine irgendwann läuft.

Eine Turing-Maschine für den fleißigsten Biber mit zwei Zuständen. Die Maschine schreibt vier Einsen.

Der fleißige Biber

Stellen wir uns jetzt eine Turing-Maschine vor, die folgendes Problem lösen soll, schreibe maximal viele Einsen auf das Band und stoppe dann. Hätte diese Maschine nur einen Zustand, könnte sie nur eine einzige Eins schreiben. Dieser Zustand wäre zum Beispiel: „wenn eine Null auf dem Band steht, schreibe eine Eins, rücke ein Feld nach rechts, halte an“. Würde die Maschine wieder in den selben Zustand gehen, statt anzuhalten, würde sie unendlich viele Einsen auf das Band schreiben und niemals anhalten. Eine Turing-Maschine mit zwei Zuständen kann maximal vier Einsen auf das Band schreiben, eine mit drei Zuständen maximal sechs Einsen.

Die beschriebenen Turing-Maschinen heißen fleißige Biber. Warum? Man will sozusagen die fleißigste Turing-Maschine finden, also die, die die meisten Einsen schreibt, bevor sie anhält. Könnte man sich jetzt eine Turing-Maschine ausdenken, die berechnet, wie viele Einsen der fleißigste Biber für n Zustände schreibt? Nein, leider kann man das nicht. Warum? Wir müssten uns zuerst alle Turing-Maschinen mit n Zuständen überlegen und dann alle durchtesten, wie viele Einsen sie schreiben, um den fleißigsten Biber zu finden. Das Problem ist: Solange der Biber Einsen schreibt, woher sollen wir wissen, ob er noch anhalten wird oder niemals stoppt?

Das Halteproblem

Kann man überhaupt feststellen, ob ein Algorithmus jemals stoppt? Ist das Problem „Hält der Algorithmus X auf Eingabe Y“ berechenbar? Kann man einen Über-Algorithmus schreiben, der für alle möglichen Algorithmen und beliebige Eingaben bestimmt, ob der Algorithmus stoppt? Wie müsste ein solcher Über-Algorithmus aussehen? Nein, kann man nicht. Bewiesen hat das Alan Turing mittels seiner Turing-Maschinen und schön nachvollziehen lässt sich das anhand eines Widerspruchs.

Was bedeutet das praktisch? Es gibt also Probleme, deren Lösungen sogar wohl definiert sind (zum Beispiel die maximale Anzahl an Einsen, die der fleißigste Biber schreibt), die man aber mit dem Computer nicht berechnen kann. Und zwar mit keinem Computer, auch keinem, der vielleicht in der Zukunft entwickelt wird (vorausgesetzt er liest und schriebt Zeichen auf einem Speicher). Immerhin weiß der faule Informatiker dann, dass er es auch gar nicht erst versuchen muss. Aber selbst wenn ein Problem algorithmisch lösbar (also berechenbar) ist, ist es in erster Linie theoretisch lösbar. Algorithmisch lösbar bedeutet aber noch längst nicht, dass das Problem auch „praktisch lösbar“ ist. Aber dazu erzähle ich euch ein andermal mehr.

Beitrag auf ScienceBlogs lesen.