Grenzen der Berechenbarkeit — das Halteproblem

Was besagt das Halteproblem?

• ● Es gibt kein Programm, das für JEDES Programm und jede Eingabe korrekt entscheidet, ob es anhält
• ○ Manche Programme lassen sich nicht starten
• ○ Jedes Programm hält irgendwann an, man weiß nur nicht wann

Mit ausreichend schnellen Computern der Zukunft wird sich das Halteproblem lösen lassen.

Welche Aufgabe kann eine Turingmaschine lösen, ein endlicher Automat aber nicht?

• ● prüfen, ob ein beliebig langes Wort genau gleich viele a wie b enthält
• ○ prüfen, ob ein Wort mit a beginnt
• ○ prüfen, ob ein Wort eine gerade Anzahl von Einsen enthält

Welche Situation zeigt, dass Programme selbst nur Daten sind?

• ● Ein Compiler liest den Quelltext eines Programms ein und übersetzt ihn
• ○ Ein Programm liest eine Zahl von der Tastatur ein
• ○ Zwei Programme laufen gleichzeitig auf demselben Rechner

Ein Problem, das kein Algorithmus für alle Fälle lösen kann, nennt man prinzipiell ___ (Gegenteil von „entscheidbar").

Was macht das Ergebnis „das Halteproblem ist unentscheidbar" wissenschaftlich so bemerkenswert?

• ● Es zieht eine beweisbare, endgültige Grenze dessen, was Computer überhaupt können — schon 1936, vor dem ersten Computer
• ○ Es zeigt, dass Computer Fehler machen
• ○ Es beweist, dass Menschen klüger als Maschinen sind

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?

• ● Widerspruchsbeweis — die Annahme führt auf einen unmöglichen Fall, also war sie falsch
• ○ Vollständige Induktion über alle Programme
• ○ Beweis durch Ausprobieren aller Fälle

Für ein EINZELNES, konkretes Programm kann ein Mensch oder ein Werkzeug durchaus nachweisen, dass es anhält — das widerspricht dem Halteproblem nicht.

Ein Softwarehaus verspricht einen Scanner, der JEDE Endlosschleife in JEDEM Programm sicher vor dem Start erkennt. Was ist davon zu halten?

• ● Das Versprechen ist beweisbar unerfüllbar — es wäre eine Lösung des Halteproblems
• ○ Mit genug Entwicklern ist das machbar
• ○ Das gibt es längst in jedem Betriebssystem

Warum folgt aus dem Halteproblem, dass es keinen perfekten Virenscanner geben kann?

• ● Weil „verhält sich dieses Programm schädlich?" eine Frage über das Verhalten aller Programme ist — solche Fragen sind im Allgemeinen unentscheidbar
• ○ Weil Viren sich zu schnell verändern
• ○ Weil Virenscanner selbst Viren enthalten

Die Turingmaschine ist nur ein Gedankenmodell — trotzdem gilt, was sie nicht berechnen kann, als für Computer überhaupt nicht berechenbar.

Die These, dass alles im intuitiven Sinn Berechenbare auch von einer Turingmaschine berechnet werden kann, heißt ___-Turing-These.

Welches Problem ist praktisch unlösbar, aber NICHT prinzipiell unlösbar?

• ● die kürzeste Rundreise durch 50 Städte durch Ausprobieren aller Reihenfolgen finden
• ○ für jedes beliebige Programm entscheiden, ob es anhält
• ○ eine Liste mit einer Million Zahlen sortieren

Dass das Halteproblem unentscheidbar ist, bedeutet: Kein Programm kann jemals über ein anderes Programm irgendetwas herausfinden.