Berechenbarkeit und Halteproblem

Eine Funktion heißt berechenbar, wenn es einen Algorithmus gibt, der zu jeder Eingabe nach endlich vielen Schritten den korrekten Funktionswert liefert. Was „Algorithmus“ genau ist, definierte Alan Turing 1936 mit seinem Modell der Turingmaschine. Die Church-Turing-These behauptet: alles, was überhaupt mit einem mechanischen Verfahren berechenbar ist, lässt sich durch eine Turingmaschine berechnen. Sie ist eine These, kein Satz, denn „mechanisches Verfahren“ ist informell.

Eine Turingmaschine besteht aus einem unendlich langen Band, einem Lese-/Schreibkopf, einem endlichen Zustand und einer Überführungsfunktion \( \delta : Q \times \Sigma \rightarrow Q \times \Sigma \times \{L, R, N\} \). In jedem Schritt liest die Maschine ein Zeichen, schreibt ein neues, ändert den Zustand und bewegt den Kopf nach links, rechts oder bleibt stehen. Trotz dieses einfachen Modells kann sie alles berechnen, was ein heutiger Computer berechnen kann.

Das Halteproblem fragt: Gibt es einen Algorithmus, der für jedes beliebige Programm \( P \) und jede Eingabe \( w \) entscheidet, ob \( P(w) \) nach endlich vielen Schritten anhält? Turing bewies 1936: Ein solches Verfahren existiert nicht. Das Halteproblem ist unentscheidbar.

Angenommen, es gibt eine Funktion halt(P, w), die genau dann true liefert, wenn das Programm P auf der Eingabe w hält. Konstruiere ein neues Programm diag:

def diag(P):
    if halt(P, P):
        while True:
            pass    # endlos
    else:
        return     # hält

Was passiert nun bei diag(diag)?

• Hält diag(diag), dann müsste halt(diag, diag) = true sein, also läuft diag in eine Endlosschleife – Widerspruch.
• Läuft diag(diag) endlos, dann müsste halt(diag, diag) = false sein, also hält diag – Widerspruch.

Beide Fälle führen zu einem Widerspruch, daher kann halt nicht existieren.

Aus dem Halteproblem folgt, dass viele weitere Fragen über Programme unentscheidbar sind: Gibt das Programm jemals einen bestimmten Wert aus? Sind zwei Programme äquivalent? Diese Tatsache ist nicht nur theoretisch, sondern hat praktische Bedeutung: kein Compiler kann garantieren, dass ein Programm nicht in eine Endlosschleife läuft, kein Antivirenprogramm kann jeden Schadcode zuverlässig erkennen.

Berechenbarkeit fragt „ist es überhaupt möglich?“, Komplexität fragt „wie schnell?“. Ein Problem kann berechenbar, aber praktisch unlösbar sein (z. B. Schach mit perfektem Spiel ist berechenbar, aber zu komplex). Das Halteproblem ist nicht einmal berechenbar.

Verwechslung von „unentscheidbar“ und „NP-schwer“, Verwechslung der Church-Turing-These mit einem Satz, falsche Annahme, das Halteproblem könne für „einfache“ Programme gelöst werden (es geht um den allgemeinen Fall).

Zusammenfassung: Das Halteproblem ist beweisbar unentscheidbar. Daraus folgt, dass es prinzipielle Grenzen dessen gibt, was Computer berechnen können.

Abitur-Tipp: Lerne die Beweis-Idee mit der Diagonalisierung – sie wird oft als Zusatzaufgabe gestellt und ist nicht so schwer, wie sie klingt.