Grenzen der Berechenbarkeit — das Halteproblem
Was besagt das Halteproblem?
Erklärung: Für einzelne Programme kann man die Frage oft beantworten — aber ein allgemeines Prüfprogramm, das IMMER richtig liegt, kann es beweisbar nicht geben.
Mit ausreichend schnellen Computern der Zukunft wird sich das Halteproblem lösen lassen.
Erklärung: Falsch — die Unentscheidbarkeit ist ein mathematischer Beweis über alle denkbaren Programme, keine Frage der Rechenleistung. Schnellere Hardware ändert daran nichts.
Welche Aufgabe kann eine Turingmaschine lösen, ein endlicher Automat aber nicht?
Erklärung: Die Turingmaschine ist ein endlicher Automat plus unbegrenztes Band zum Lesen und Schreiben. Mitzählen ohne Obergrenze braucht genau dieses Band. Anfangszeichen und gerade/ungerade schafft schon ein Automat mit endlich vielen Zuständen.
Welche Situation zeigt, dass Programme selbst nur Daten sind?
Erklärung: Der Compiler behandelt ein Programm als Eingabe — als Bitfolge wie jeden Text. Diese Programme-sind-Daten-Einsicht ist der Schlüssel zum Beweis des Halteproblems. Eine Tastatureingabe oder paralleles Laufen zeigt davon nichts.
Ein Problem, das kein Algorithmus für alle Fälle lösen kann, nennt man prinzipiell ___ (Gegenteil von „entscheidbar").
Erklärung: Unentscheidbar heißt „durch keinerlei Programm lösbar" — die stärkste Form von Unlösbarkeit, unabhängig von Zeit und Technik.
Der Beweis des Halteproblems beginnt so: „Angenommen, es gäbe ein Prüfprogramm HALT(P, E), das immer korrekt antwortet …" und endet in einem Widerspruch. Wie heißt diese Beweistechnik?
Erklärung: Man baut aus dem angenommenen Prüfer ein Trotzprogramm, das genau dann endlos läuft, wenn der Prüfer „hält an" sagt — auf sich selbst angesetzt ergibt das einen Widerspruch.
Für ein EINZELNES, konkretes Programm kann ein Mensch oder ein Werkzeug durchaus nachweisen, dass es anhält — das widerspricht dem Halteproblem nicht.
Erklärung: Richtig — unentscheidbar ist nur die ALLGEMEINE Frage für alle Programme. Einzelfälle sind oft lösbar, z. B. mit einem Terminierungsargument über eine schrumpfende Größe.
Ein Softwarehaus verspricht einen Scanner, der JEDE Endlosschleife in JEDEM Programm sicher vor dem Start erkennt. Was ist davon zu halten?
Erklärung: Ein perfekter Endlosschleifen-Detektor würde das Halteproblem entscheiden. Praktische Werkzeuge finden viele Fälle — aber niemals alle, und das ist beweisbar.
Warum folgt aus dem Halteproblem, dass es keinen perfekten Virenscanner geben kann?
Erklärung: Fragen über das Laufzeitverhalten beliebiger Programme erben die Unentscheidbarkeit des Halteproblems. Scanner arbeiten deshalb mit Heuristiken — gut, aber nie perfekt.
Die Turingmaschine ist nur ein Gedankenmodell — trotzdem gilt, was sie nicht berechnen kann, als für Computer überhaupt nicht berechenbar.
Erklärung: Richtig — nach der Church-Turing-These erfasst das Modell genau das, was maschinell berechenbar ist. Alle bekannten Rechnermodelle können nicht mehr als sie.
Die These, dass alles im intuitiven Sinn Berechenbare auch von einer Turingmaschine berechnet werden kann, heiĂźt ___-Turing-These.
Erklärung: Die Church-Turing-These verbindet den intuitiven Begriff „berechenbar" mit dem präzisen Maschinenmodell — sie ist Arbeitsgrundlage der gesamten Berechenbarkeitstheorie.
Welches Problem ist praktisch unlösbar, aber NICHT prinzipiell unlösbar?
Erklärung: Die Rundreise ist prinzipiell lösbar — der Algorithmus existiert, braucht aber länger als das Universum alt ist: die praktische Grenze. Das Halteproblem kann dagegen kein Programm je lösen (prinzipielle Grenze), und Sortieren gelingt in Sekunden.
Dass das Halteproblem unentscheidbar ist, bedeutet: Kein Programm kann jemals ĂĽber ein anderes Programm irgendetwas herausfinden.
Erklärung: Falsch — viele Eigenschaften sind prüfbar (Syntax, bestimmte Muster, Einzelfälle). Unentscheidbar ist die allgemeine Verhaltensfrage über ALLE Programme, nicht jede Analyse.
Was macht das Ergebnis „das Halteproblem ist unentscheidbar" wissenschaftlich so bemerkenswert?
Erklärung: Alan Turing bewies die Grenze rein mathematisch, bevor es Computer gab. Ob Menschen solche Fragen „besser" beantworten können, folgt daraus übrigens nicht.