Das Halteproblem

Zum Abitur und im Semester davor schreiben die Schüler in Informatik Computerprogramme in einer Assembler-Programmiersprache. Die besteht zwar aus ganz einfachen Einzelschritten, aber genau das führt dazu, dass das ganze Programm etwas unübersichtlich ist und man nicht auf den ersten Blick sieht, was es genau tut. Wenn ich die Schülerprogramme also bewerten will, muss ich sie abtippen und laufen lassen, und dann sehe ich, ob am Schluss das richtige Ergebnis herauskommt. Wenn ja: volle Punktzahl, wenn nein: puh. Dann muss ich das Programm Schritt für Schritt nachvollziehen, um herauszufinden, wo das Problem ist – wo sich zum Beispiel eine Endlosschleife verbirgt, so dass das Programm nie aufhört zu laufen.

In dieser Situation wünschte ich mir ein Programm, das diese Arbeit automatisch für mich erledigt. Ich würde es mit den Schülerprogrammen füttern, und es würde mir danach sagen „ja, das Problem kommt früher oder später an ein Ende“ oder „nein, das Programm wird in eine Endlosschleife geraten und nie aufhören.“

Die Frage, ob es so ein Programm gibt, heißt Halteproblem der Informatik. Und das Halteproblem ist allgemein nicht lösbar – es kann so ein Programm nicht geben, egal wie gut Computer noch werden. (Für spezielle Sonderfälle, etwa Programme, die sich an bestimmte Vorgaben halten, ist es oft lösbar. Aber eben nicht, wenn es um beliebige Programme geht.)

Der Beweis folgt.

Teil 1: Was ein Computerprogramm ist.

Ein Computerprogramm kann man sich als ein Frage-Antwort-Maschinchen vorstellen, in das man zum Beispiel eine Zahl eingibt, dann rechnet das Maschinchen, um am Schluss macht es „Ping!“ und eine Zahl kommt als Antwort heraus. Da gibt es zum Beispiel das Verdoppelungsmaschinchen:

verdoppeln(eines eingangswertes):
  ergebnis: eingangswert mal 2

Das funktioniert natürlich nicht nur mit Zahlen, sondern auch mit Text. Lehrer träumen ja von einem Korrektur- und Benotungsmaschinchen:

benoten(eines aufsatzes):
  [rechnen, rechnen, rechnen]
  ergebnis: note

Die praktische Schwierigkeit liegt dabei in dem Schritt, den ich weggelassen habe: das mit dem Rechnen. Um das geht es hier aber gar nicht. Wie der Computer vorgeht, um zum gewünschten Ergebnis zu kommen, interessiert uns im Moment nicht. Wichtig ist nur, dass ein Programm zum Berechnen eine Wiederholungsschleife ausführen kann, dass ein Programmteil also immer und immer wiederholt wird, bis eine bestimmte Bedingung (die Wiederholbedingung) nicht mehr gilt. Bei den meisten üblichen Berechnungen kann man vorher sagen, wie oft das höchstens der Fall sein wird, bei anderen Berechnungen ist das schwieriger.

Um das zu veranschaulichen, verwende ich drei Beispielprogramme, auf die ich auch später zurückkommen werde. Die Programme sind countdown (von einer beliebigen Startzahl aus), endlosdrucken (eines beliebigen Starttextes) und ausdrucken(eines beliebigen Starttextes).

Mein erstes Programm ist eigentlich nur ein kleines Hilfsprogramm:

Ausdruckprogramm

ausdrucken(eines Textes):
  druckt den Text aus

Jetzt die anderen Progrämmchen:

Countdownprogramm

countdown(von einer Zahl aus):
  wiederhole solange zahl>0:
    ausdrucken(der zahl)
    um_eins_verringern(die zahl)

Man sieht sehr schnell, wie lange dieses Countdown-Programm braucht, bis es fertig ist: Wenn ich mit der Zahl 5 anfange, sind es 5 Durchgänge durch die Schleife, mit jeweils sinkender Zahl (5-4-3-2-1).

Merke: Dieses Programm kommt immer früher oder später zu einem Ende, egal mit welcher Startzahl ich anfange.

Endlosdrucker

endlosdrucken(eines Textes):
  wiederhole solange Textlänge größer als -1:
    ausdrucken(des Textes)

Man sieht schnell, dass dieses Programm nie zu einem Ende kommt. Es wird immer wieder den gleichen Text ausdrucken.

Merke: Dieses Programm kommt nie zu einem Ende, egal mit welchem Starttext ich anfange.

Und der Vollständigkeit halber: Es gibt natürlich auch viele Programme, bei denen es vom Startwert abhängt, ob das Programm ewig läuft oder nicht. Hier ein ganz simples Beispiel:

manchmalprogramm(text):
  wiederhole solange Textlänge > 5:
    ausdrucken(text)

Das Programm druckt den Eingabetext immer und immer wieder aus und hört nie auf – es sei denn, der Eingabetext ist kürzer als 5 Zeichen lang. Dann tut das Programm gar nichts.

Wir merken uns:

  1. Manche Programme terminieren (kommen zu einem Ende), andere nicht (sind in einer Endlosschleife gefangen).
  2. Ob sie das eine oder andere tun, hängt auch von den Eingabewerten ab, mit denen das Programm aufgerufen wird.
  3. Bei einfachen Programmen sieht man sehr schnell, wann sie terminieren oder nicht.
  4. Bei komplizierten Programmen geht das nicht so einfach, oder gar nicht.

Teil 2: Noch ein Beispiel, warum es schön wäre, wenn das Halteproblem lösbar wäre.

Es gibt mathematische Probleme, bei denen weiß man die Lösung nicht. Man weiß nicht einmal, ob es eine Lösung gibt. Etwa bei der wiederholten Anwendung der Collatz-Funktion. Die geht so: Beginne mit einer natürlichen Zahl. Wenn sie gerade ist, halbiere sie; wenn sie ungerade ist, multipliziere sie mit 3 und addiere 1. Wiederhole das mit der neuen Zahlen, die du erhalten hast – und dann immer weiter.

  • Wenn man mit 5 beginnt, erhält man folgende Reihe: 5-16-8-4-2-1 (und bei der 1 hört man dann auf, weil es dann mit der 4 weitergeht).
  • Wenn man mit 3 beginnt, erhält man folgende Reihe: 3-10-5-16-8-4-2-1 (und bei der 1 hört man dann auf).
  • Wenn man mit 7 beginnt, erhält man folgende Reihe: 7-22-11-34… …4-2-1 (und bei der 1 hört man dann auf).

Landet man bei jeder Zahl früher oder später bei 4-2-1? Das wird vermutet, bewiesen ist aber noch gar nichts. Eine Alternative wäre zum Beispiel ein anderer Zyklus als 4-2-1-4-2-1…, in den man gerät. Oder die Zahlen werden im Prinzip immer größer, ohne sich je exakt zu wiederholen, könnte auch sein.

Man kann leicht ein Programm schreiben, das der Reihe nach für alle natürlichen Zahlen ausprobiert, ob sie bei 1 landen oder in einem anderen Zyklus. Das Programm terminiert, sobald eine Zahl gefunden ist, die nicht bei 1 landet (sondern in einem anderen Zyklus), ansonsten probiert es halt der Reihe nach alle Zahlen aus.

collatz_conjecture
xkcd webcomic – immer wieder lesenswert

Wenn das Programm läuft, sitzt man vor dem Rechner und wartet, ob es eine Antwort ausspuckt. Und wartet. Und wartet. Möglicherweise wartet man ewig, wenn es so eine Zahl nicht gibt. Oder man wartet einfach noch nicht lange genug, weil es doch eine solche Zahl gibt. Da wäre es doch schön, wenn man sein hypothetischen Überprüfungsprogramm mit dem Collatz-Programm füttern könnte, damit das dann entscheidet, ob das Collatz-Programm irgendwann mal anhalten wird oder nicht.

(Siehe dazu auch die Sache mit der Medizinerparty.)

Teil 3: Der Beweis.

(1) Nehmen wir an, es gäbe so ein Checkerprogramm. Man würde es füttern mit zwei Informationen, nämlich dem Programm, das es testen soll, und dem Startwert, mit dem das Programm laufen soll. Wir haben ja oben gesehen, dass es vom Startwert abhängen kann, ob ein Programm anhält oder nicht.

Es hätte dann ungefähr folgende Form:

anhaltechecker (eingabeprogramm, eingabewerte):
  [rechnen, rechnen, rechnen]
  wenn das Programm mit diesen Startwerten anhalten wird:
    ausgeben ("Ja, wird anhalten!")  
    ergebnis: wahr
  sonst:
    ausgeben ("Nein, terminiert nicht.")
    ergebnis: falsch

Wenn ich es aufrufe :

anhaltechecker (countdownprogramm, 10)

– dann wird es mir ausgeben: „Ja, wird anhalten!“, weil das Countdownprogramm ja tatsächlich anhält, wenn man es mit einer 10 als Argument aufruft, wie bei jeder anderen natürlichen Zahl auch.

Und wenn ich es aufrufe:

anhaltechecker (endlosdrucken, "Hallo Susi")

– dann wird es mir ausgeben: „Nein, terminiert nicht.“, weil das Endlosprogramm ja tatsächlich nie fertig wird, sondern immer nur den Eingabetext ausdruckt.

Und wenn ich es aufrufe:

anhaltechecker (ausdrucken, ausdrucken)

– dann wird es mir ausgeben: „Ja, wird anhalten!“, weil mein Ausdruckprogramm natürlich einen längeren Text ausdrucken kann und dann fertig ist, auch wenn der längerere Text ein Computerprogramm ist, und sei es zufälligerweise auch der eigene Programmcode.

(2) Nehmen wir jetzt folgendes fieses kleines Programm:

fiesling(eingabeprogramm):
  solange anhaltechecker(eingabeprogramm, eingabeprogramm) sagt, dass angehalten wird:
    nichtstun
  danach:
    ausgeben("Fertig.")

Das tatsächlich ganz leicht zu schreibende Fieslingsprogramm nimmt ein Programm als Eingabewert, und leitet es weiter an unser hypothetisches Anhaltechecker-Programm. Das soll das testen, und zwar mit dem zu überprüfenden Programm als Eingabeargument seiner selbst. Das ist der Knackpunkt. Wenn wir zum Beispiel aufrufen:

fiesling(ausdruckprogramm)

Dann wird zuerst anhaltechecker(ausdruckprogramm,ausdruckprogramm) aufgerufen, und solange das zu einem Ende kommt (was es tut, siehe oben), kommt das Fieslingsprogramm genau nicht zu einem Ende. So ein dummes Programm.

Wenn ich es dagegen aufrufen würde:

fiesling(endlosprogramm)

Dann würde zuerst anhaltechecker(endlosprogramm, endlosprogramm) aufgerufen werden, und da (das Endlosdruckprogramm) nicht zu einem Ende kommt (sondern nur endlos den Programmtext ausdrucken würde), würde mein Fieslingsprogramm das eben schon tun und ausgeben: „Fertig.“

(3) Das Zusammenbauen.

Was passiert, wenn ich aufrufe:

fiesling(fiesling)

Das war’s dann eigentlich. Das Fieslingsprogramm würde seinerseits aufrufen anhaltechecker(fiesling,fiesling), und wenn das ausgibt, dass fiesling(fiesling) anhält, würde es nicht anhalten. Und wenn es ausgibt, dass es nicht anhält, würde es anhalten. Das ist ein nicht auflösbarer Widerspruch. Absurd. Also muss eine unserer Prämissen falsch sein, und das kann nur die sein, dass es so ein Programm wie den Anhaltechecker geben kann. Also kann es so ein Programm nicht geben.

Ich habe ein paarmal versucht, das einfacher zu fassen. Herausgekommen ist das, was herausgekommen ist.

5 Gedanken zu “Das Halteproblem

  1. Sehr gute Beschreibung – das war bestimmt nicht einfach…

    Im letzten Satz von Abschnitt (2) würde ich noch klarstellen, dass es das endlosprogramm ist, welches nicht zu einem Ende kommt (nicht der anhaltechecker).

  2. Deine Version ist präzise und schön kurz und hilft mir beim Verstehen. Ich hoffe halt, möglicherweise vergebens, dass das hier irgendwann mal für Laien interessant wird… :-)

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind markiert *