Das Halteproblem

Welche Art von Problemen können eigentlich prinzipiell von Computern gelöst werden, welche nicht?

Bei der Beantwortung dieser Frage sollen allerdings nicht die real existierenden Computer betrachtet werden. Ziel ist vielmehr eine technologie-unabhängige Formulierung des Begriffs der Berechenbarkeit einer Funktion, beziehungsweise der Entscheidbarkeit einer Sprache L entwickeln. Denn:

  • Wir wissen nicht, wie Rechner zukünftiger Technologien aufgebaut sind.
  • Unsere Begriffsbildung sollte für heutige von Neumann Rechner genau so gelten wie z.B. für zukünftige Quanten- oder DNA-Rechner!

Zudem müsste untersucht werden, welche Sprachen oder Probleme zu schwierig sind, also auch durch Rechner in zukünftigen Technologien nicht gelöst werden können.

Wäre es nicht schön …

Wäre es nicht schön, wenn Computer richtig funktionieren würden? Wenigstens sollten sie nicht ständig abstürzen. Dafür könnte man doch eigentlich mal ein Programm schreiben … also ein Programm, welches automatisch prüft, ob andere Programme zum Absturz führen (z. B. durch eine Endlosschleife).

Die Lösung des Halteproblems wäre von großem wirtschaftlichen Nutzen:

  • Es könnte viel Rechenzeit gespart werden.
  • Die Anwender wären zufriedener, weil sie sich nie mehr fragen müssten, „ob da jetzt noch einmal etwas passiert“.

Man könnte daher vermuten, dass weltweit zahlreiche Menschen daran arbeiten, ein Programm zur Lösung des Halteproblems zu entwickeln …

Wie müsste ein solches Programm aussehen? Nehmen wir mal an, wir haben ein solches Programm STOP:

Programm STOP(P,E)
Eingabe: Programm P; Eingabe E
Ausgabe: 1, falls P(E) terminiert
         0, sonst

Gehen wir mal davon aus, dass ein solches Programm STOP existiert. Damit können wir uns ein weiteres Programm HALTEN schreiben:

Programm HALTEN(P,E)
  // STOP wird mit Programm P und Eingabe P aufgerufen
  x = STOP(P,P)
  wenn x = 0
    dann Programm HALTEN hält an
    sonst solange x = x  // Endlosschleife
            x = x

Nun wenden wir HALTEN auf HALTEN selbst an. Was kann passieren?

  1. STOP(P,P) = 0 (STOP hält nicht an) => x = 0 => HALTEN hält an
  2. STOP(P,P) = 1 (STOP terminiert) => x = 1 => HALTEN hält nicht an (Endlosschleife)

Zusammengefasst:
HALTEN angesetzt auf HALTEN hält an <=> HALTEN angesetzt auf HALTEN hält nicht an.

Aus diesem Widerspruch müssen wir schlussfolgern, dass die Annahme falsch war, d. h. dass es ein Programm STOP mit den gewünschten Eigenschaften gibt.

=> Es gibt also kein Programm, welches das Halteproblem löst!

Okay, dann können wir halt das Halteproblem nicht lösen, aber es gibt ja noch eine Menge weiterer interessanter Probleme:

  • Sind zwei Programme äquivalent?
  • Gibt ein Programm stets die Zahl „42“ aus?
  • Berechnet ein Programm bei Eingabe einer Zahl x den Wert f(x)?

Satz von Rice

Aus dem Satz von Rice folgt, dass keine dieser Fragen durch ein Computerprogramm entschieden werden kann:

Definition: Satz von Rice
Keine (nicht-triviale) Eigenschaft von Programmen kann von einem Computerprogramm “erkannt” werden.

Genauer: Sei B die Menge aller berechenbaren Funktionen und F \subseteq B mit F \neq B \neq \emptyset. Dann gibt es keinen Algorithmus, der bei Eingabe eines Programms P entscheidet, ob die von P berechnete Funktion zur Menge F gehört.

Als trivial gelten beispielsweise Eigenschaften wie, ob der Algorithmus eine bestimmte Länge hat oder ob er eine bestimmte Zeichenkette enthält.

Nicht-trivial sind hingegen die Eigenschaften, ob er eine bestimmte Ausgabe erzeugt oder ob eine bestimmte Anweisung ausgeführt wird etc. .

Schlagwörter: