3 Das Halte-Problem

3.1 Wahr - Falsch - Unentscheidbar?
3.2 Ein wirklich nützliches Programm
3.3 Gibt es den ELCH-Test?
3.4 Was wäre wenn?

Zum vorigen Kapitel Zum Inhaltsverzeichnis Zum nächsten Kapitel


3.1 Wahr - Falsch - Unentscheidbar?

Im vorigen Kapitel haben wir eingesehen, dass es mehr Probleme gibt als wir Programme schreiben können. Die Frage ist, ob es tatsächlich Problem gibt, die sich zwar eindeutig formulieren lassen, von denen man aber wirklich sicher sein kann, dass sie niemals durch ein Programm entschieden werden können.

Abgesehen von mathematischen Scheinproblemen (wie z.B. der Frage nach der größten Primzahl) gibt es in der Tat eine Menge von Problemen, für die bisher noch keine Lösung bekannt ist. In vielen Fällen wissen wir auch nicht, ob wir jemals eine Lösung finden werden. In einem Gutteil der Literatur zur Problematik der Berechenbarkeit wird der berühmte "Fermat'sche Satz" als ein solches ungelöstes Problem angeführt:

Die Gleichung xn + yn = zn hat für kein natürliches n ³ 3 eine Lösung (x, y, z) aus ganzen Zahlen.

Fermat (1601-1665) formulierte diesen Satz, veröffentlichte aber keinen Beweis dazu. Er schrieb lediglich auf den Rand der Seite, auf der er den Satz notierte, die berühmt gewordene Bemerkung:
In den folgenden Jahrhunderten bissen sich zahlreiche Mathematiker an diesem "Fermat'schen Satz" die Zähne aus - ohne einen allgemeinen Beweis zu finden. Ebenso erfolglos jedoch verlief die Suche nach einem Gegenbeispiel. Somit galt der Satz lange als ein guter Kandidat für eine mathematisch klare Aussage, die sich weder beweisen noch widerlegen lässt - bis 1993 der Mathematiker Andrew Wiles einen Seminarvortrag im Isaak-Newton-College in Cambridge mit dem Beweis dieses Satzes beendete! Vorausgegangen waren sieben Jahre harter Arbeit in nahezu eremitischer Abgeschiedenheit, und es sollten vier weitere schwierige Jahre folgen, in denen noch einige kleinere Beweislücken geschlossen werden mussten. Aber 1997 wurde Wiles schließlich der Wolfskehl-Preis zuerkannt - ein Preis, der rund 90(!) Jahre zuvor ausschließlich für einen Beweis des Fermat'schen Satzes ausgesetzt worden war.

Seitdem gehört der "Satz von Fermat" nicht mehr in die Riege der ungelösten Probleme. Zuvor musste man annehmen, dass er möglicherweise unentscheidbar wäre. Der Beweis von Wiles hat ihn nun entschieden und zu einem wahren Satz gemacht. Aber so lange wir den Beweis noch nicht kannten, konnten wir nicht beurteilen, ob das Problem überhaupt entscheidbar ist.

Dass es in besonderen Fällen überhaupt möglich ist, die Unentscheidbarkeit eines Problems zu beweisen, ist schon erstaunlich. Wir wollen im Folgenden ein solches Problem beschreiben, von dem wir beweisen können, dass es nie gelöst werden kann!




3.2 Ein wirklich nützliches Programm

Haben Sie sich nicht auch schon häufig darüber geärgert, wenn ein Programm "hängt"? Man sagt dann: "es ist abgestürzt" oder "es reagiert nicht mehr". Wir wissen, dass das Programm in diesem Zustand heftig arbeitet: es rackert sich in einer Endlos-Schleife ab und kann sie nicht mehr verlassen! In der Anfangszeit der Computerei half in solchen Fällen nur noch der Griff zum Reset-Knopf, heute bietet das Betriebssystem die Möglichkeit, ein solches Programm gewaltsam zu beenden. Unangenehm bleibt die Situation trotzdem, verliert man doch in der Regel die zuletzt bearbeiteten Daten!

Warum hat nicht längst jemand ein Programm geschrieben, das ein beliebiges anderes Programm daraufhin untersucht, ob es irgend welche Endlos-Schleifen enthält oder nicht? Geben wir diesem Diagnose-Programm erst mal einen Namen: ELCH soll es heißen - eine Akronym für den neu-deutschen Programmnamen "Eternal Loop CHecker". Als Eingabe bekommt ELCH den Code eines beliebigen anderen Programms XYZ sowie die Eingabedaten DAT für XYZ. Als Ausgabe soll es nur "JA" oder "NEIN" liefern - nämlich die Antwort auf die Frage: "Hält das Programm XYZ bei der Eingabe des Datensatzes DAT an?" Wenn ELCH für XYZ bei irgend welchen Eingabedaten DAT die Antwort "NEIN" produziert, dann werfen wir XYZ auf den Müll und sehen uns nach einem besseren Programm um, das unseren ELCH-Test besteht und keine Endlosschleifen enthält.

Das Programm ELCH ist also eine "Halte-Tester" für alle (anderen) Programme und stellt somit eine Lösung des klassischen Halte-Problems dar:

Unter einem universellen Halte-Tester versteht man einen Algorithmus, der zu jedem beliebigen Programm XYZ und jedem beliebigen Datensatz DAT nach endlich vielen Schritten entscheidet, ob XYZ bei Eingabe von DAT anhält oder nicht.



Aufgaben:


  1. Besteht Windows den ELCH-Test?

    Fritzchen Pfiffig sagt: "Kein Windows-Programm würde den ELCH-Test bestehen, denn jedes Windows-Programm enthält eine Message-Loop, und das ist eine Endlos-Schleife!" Ist das wahr?

  2. Die größte Primzahl?

    Warum wird die Suche nach der größten Primzahl oben als "mathematisches Scheinproblem" bezeichnet?




3.3 Gibt es den ELCH-Test?

Das im vorigen Abschnitt entworfene Diagnose-Programm ELCH wäre ein Segen für die Computerwelt. Endlich wird man nicht mehr heimtückisch von "Hängern" in irgendwelchen Programmen überrascht. Man kann sich darauf verlassen, dass jedes Programm, das den ELCH-Test besteht, niemals "abstürzen" wird, sondern zuverlässig laufen wird, bis der Benutzer es beendet. Warum also schreibt niemand ein solches Programm? Sie ahnen es: weil es ein solches Programm nicht geben kann. Es gilt der folgende Satz:

Das Halte-Problem ist nicht entscheidbar, d.h. es gibt keinen Algorithmus, der nach endlich vielen Schritten entscheiden kann, ob ein beliebiger anderer Algorithmus für beliebige gegebenene Eingabedaten halten wird oder nicht.

Oder mit anderen Worten: Es gibt keinen ELCH-Test für Programme.

Wir führen den Beweis dieses Satzes durch Widerspruch:
Nehmen wir einmal an, dass findige indische Programmierer ein solches ELCH-Programm implementiert hätten. Es sei ein anspruchsloses Konsolenprogramm, das beim Aufruf das zu untersuchende Programm und den Satz der Eingabe-Daten übergeben bekommt und dann die gesuchte Antwort auf die Konsole zurückgibt:
        ELCH (XYZ, DAT)
        JA
Bei dieser Ausgabe hätte XYZ den ELCH-Test bestanden, - wenn auch nur für die speziellen Eingabedaten DAT, aber immerhin! Wir können den Test ja mit anderen Datensätzen DET, DIT, DOT,..... wiederholen. Liefert ELCH immer "JA", dann wächst unser Vertrauen in das Programm XYZ. Wenn wir dann alle möglichen Eingabe-Datensätze durchprobiert haben und nie das Testergebnis "NEIN" aufgetaucht ist, können wir XYZ das Prädikat "endlosschleifen-frei" zuerkennen.

Richtig harte Tester kommen dabei auch auf skurrile Ideen: man könnte dem Programm XYZ auch mal die eigene Datei als Eingabe vorsetzen. Wenn das Programm wirklich stabil ist, sollte auch der Aufruf ELCH (XYZ, XYZ) das Ergebnis "JA" liefern.

Wir programmieren nun ein neues Programm KNILCH, das ein beliebiges Programm P übergeben bekommt und intern ELCH benutzt. Hier ist der verwendete Algorithmus in Pascal:
        program KNILCH (P);
          var i, k : Integer;
          begin
          If ELCH (P, P) = "NEIN" then
            exit
          else begin
            i := 1;
            k := 0;
            While i <> 0 do
              Inc(k);
            end;
          end.

Bevor wir KNILCH nun im Alltag einsetzen (- wozu auch immer! -), wollen wir das Programm natürlich testen. Hält es denn unter allen Umständen an? Nein, natürlich nicht, denn im "else"-Teil des Programmcodes steht eine astreine Endlos-Schleife! Also hält KNILCH genau dann an, wenn ELCH(P, P) den Wert "NEIN" liefert; dies ist genau dann der Fall, wenn das Programm P in eine Endlosschleife geht, sofern man ihm als Input seine eigene Datei vorsetzt.

Die heiße Frage ist nun: Was passiert, wenn wir KNILCH mit sich selbst als Argument aufrufen? Hält KNILCH (KNILCH) an? Ehe wir uns hier in hirnverzwirnende Argumentationen verstricken, kalkulieren wir einfach mal beide Fälle durch:

  1. Angenommen, KNILCH (KNILCH) hält an. Dann muss ELCH (KNILCH, KNILCH) das Ergebnis "NEIN" geliefert haben, was aber bedeutet, dass KNILCH (KNILCH) nicht anhält!

  2. Angenommen, KNILCH (KNILCH) hält nicht an. Dann muss ELCH (KNILCH, KNILCH) das Ergebnis "JA" geliefert haben, denn nur dann gerät KNILCH in seine Endlos-Schleife. Wenn aber ELCH (KNILCH, KNILCH) "JA" liefert, heißt das, dass KNILCH (KNILCH) anhält!

In beiden Fällen erhalten wir also einen satten Widerspruch! KNILCH ist damit ein ganz raffiniertes Programm, das seinem Namen alle Ehre macht, wenn man ihm seine eigene Datei als Eingabe vorsetzt:

KNILCH (KNILCH) hält genau dann an, wenn es nicht anhält!

Widerspruchsbeweise haben es so an sich, dass man an ihrem Ende nach dem Denkfehler am Anfang suchen muss. Und es darf im ganzen Gedankengang nur genau einen Denkfehler geben - den nämlich, den man zeigen will! Gehen wir also unsere Argumentation nochmals kritisch durch:
Selbst die Inder können also keinen solchen ELCH-Test für Programme implementieren - wo sie doch sonst jede programmiertechnische Herausforderung erfolgreich annehmen ;-)
Weil es kein solches Programm geben kann, kann es auch keinen entsprechenden Algorithmus geben; daraus folgt, dass das Halte-Problem unentscheidbar ist!   q.e.d.



Aufgabe:


  1. Teil-Lösung für bescheidene Leute?

    Man kann die oben konstruierte Situation so interpretieren: das Programm KNILCH beweist, dass das Programm ELCH eben nicht für alle möglichen Eingaben testen kann, ob das übergebene Programm anhält oder nicht.

    Welche Programme müsste man aus dem Definitions-Bereich von ELCH mindestens entfernen, damit es seine Aufgabe wenigstens für alle "zugelassenen" Programme erfüllen könnte?

    Welche Auswirkungen hätte diese Veränderung auf den obigen Beweis?
    Ist - unter diesen Einschränkungen - das Halte-Problem möglicherweise zumindest "partiell" entscheidbar? Was bringt uns das für die Beurteilung der Entscheidbarkeit des allgemeinen Halte-Problems?
    [Lösungsvorschlag]





3.4 Was wäre wenn?

Dass das Halte-Problem nicht entscheidbar ist und es keinen universellen ELCH-Test für Programme gibt, bewahrt uns unter anderem davor, auf fast jede Frage eine Antwort zu bekommen. Es gibt nämlich einen einfachen Algorithmus, mit dem man das Programm ELCH als Entscheider für eine ziemlich große Menge offener Fragen einsetzen könnte. Wir wollen das am Beispiel der berühmten Goldbach'schen Vermutung illustrieren, die noch heute (2006) zu den ungelösten Problemen der Zahlentheorie gehört. Sie besagt:

Jede gerade natürliche Zahl größer als 2 lässt sich als Summe zweier Primzahlen darstellen.

Nun könnte man ein (Brut-Force-) Programm GOLDBACH schreiben, das (nach Drücken der ENTER-Taste) systematisch die Serie der geraden natürlichen Zahlen durchmustert, bis es eine Zahl gefunden hat, die nicht als Summe zweier Primzahlen darstellbar ist. Statt das Programm nun zu starten und vielleicht Jahrhunderte zu warten, bis es eine solche Zahl ausgibt und dann - müde, aber glücklich - anhält, fragen wir einfach ELCH, ob GOLDBACH anhalten wird: der Aufruf
        ELCH (GOLDBACH, [ENTER])
bringt's sofort an den Tag! Liefert er "JA", dann hält das Programm GOLDBACH an; mithin gibt es eine gerade natürliche Zahl, die nicht als Summe zweier Primzahlen darstellbar ist. In diesem Fall erweist sich die Goldbach'sche Vermutung also als falsch. Liefert der obige Aufruf hingegen "NEIN", dann hält GOLDBACH nie an, sucht also endlos nach einem Gegenbeispiel für die Goldbach'sche Vermutung - und wird keines finden. Also ist die GOLDBACH'sche Vermutung wahr. ELCH würde uns diese Information liefern, ohne dass wir die unendliche Laufzeit von GOLDBACH abwarten müssten!

Analog könnte man bei anderen offenen Fragen der Mathematik vorgehen, für die sich ein Brute-Force-Algorithmus formulieren lässt. Das dürften zumindest mal alle bisher unentschiedenen Sätze der Zahlentheorie sein, die mit "Für alle natürlichen Zahlen gilt...." oder "Es gibt eine natürliche Zahl, so dass..." beginnen. Die Idee der Gödelisierung legt den Verdacht nahe, dass man auch viele Probleme aus anderen Gebieten so umformulieren könnte, dass sie "ELCH-entscheidbar" würden.

Kehren wir wieder zurück auf den Boden der Realitäten! Da es kein universelles ELCH-Programm gibt, ist es müßig darüber zu spekulieren, welche Probleme man damit lösen könnte. Beim Streben nach neuer Erkenntnis steht uns nach wie vor ausschließlich der steinige Pfad harter geistiger Arbeit offen - wie ihn Andrew Wiles so vorbildlich gegangen ist. Wenn Sie ihm nacheifern wollen, können Sie sich ja mal an der Goldbach'schen Vermutung versuchen! Man hat übrigens inzwischen nachgerechnet, dass sie für alle n < 1014 wahr ist (Stand 2003). Sie müssen also nur noch die paar restlichen Zahlen bis unendlich untersuchen....






Zum vorigen Kapitel Zum Inhaltsverzeichnis Zum nächsten Kapitel