Halteproblem & Konsequenzen, 103KB

Berechenbarkeit
Das Halteproblem
Gibt es ein Programm (Methode) H, welches feststellt (entscheidet), ob ein beliebiges
Programm P mit seinen Eingabedaten E nach endlich vielen Schritten endet oder nicht ?
→ Entscheidungsverfahren!
Wir führen hier einen Beweis für JAVA-Programme. Ein allgemeiner Beweis ist ebenfalls möglich.
Ein Programm mit seinen Eingabedaten lässt sich als (sehr lange) Binärzahl interpretieren.
Programm & Eingabe
E = Eingabedaten,
darstellbar
als Binärzahl
Terminierung?
Programm P
Ausgabe?
P = Folge von Anweisungen, auch als Binärzahl darstellbar
⇒ Ein Programm P mit Eingabe E lässt sich als
Binärzahl schreiben: P, E
⇒ P, E = 01001101 11011111 01010011 01101111
11101101 11000011 01100000 00011100 .......
Seite 13 /09.10
Berechenbarkeit
Halteproblem
Gibt es ein universelles Programm H, welches bei Eingabe
von (P , E) false oder true liefert?
Eingabe
(P , E) = Binärzahl
aus P und der
Haltetester
true: P hält mit
Eingabe E an
H
false: P terminiert nicht,
d.h. P gerät in eine
Endlosschleife
H(Binaerzahl P, Binaerzahl E) {
?!??
Ausgabe: true; // terminiert
??!!?
Ausgabe: false; // terminiert nicht
}
Eingabe E
Das Programm H könnte in das gegebene Betriebssystem integriert werden, um 'schlechte'
Programme zu erkennen.
Seite 14 /09.10
Berechenbarkeit
Wir formulieren mit Hilfe von H( ) ein Programm Seltsam( ):
Die Eingabe y ist wieder als Binärzahl zu verstehen.
Seltsam(Binaerzahl y) {
if ( H(y,y) ) {
while (true) { ; }
}
else
Ausgabe: “Fertig“;
}
// Endlosschleife !!
Wir rufen jetzt das Programm Seltsam auf und übergeben den eigenen Quelltext
als Eingabe:
Seltsam( Seltsam );
Fall 1 H(Seltsam, Seltsam) = true H sagt, dass Seltsam terminiert
Laut Quelltext gerät aber Seltsam in die Endlosschleife und terminiert deshalb nicht!
Widerspruch
Fall 2 H(Seltsam, Seltsam) = false
Der else-Teil wird ausgeführt und Seltsam terminiert, obwohl H(Seltsam, Seltsam) besagt, dass
Seltsam nicht terminiert.
Widerspruch
→ Die Annahme, dass H existiert ist falsch.
Satz von Turing (1936)
Das Halteproblem ist unentscheidbar. Es gibt keinen Algorithmus, der entscheiden kann, ob ein
beliebiges Programm P mit seiner Eingabe E in eine Endlosschleife gerät oder nicht.
Seite 15 /09.10
Berechenbarkeit
Bemerkungen
• Die Halte-Eigenschaft für Programme ist nicht entscheidbar. Ob ein beliebiges Programm P nach
endlich vielen Schritten anhält, lässt sich nur feststellen, indem man P mit den Eingaben E startet
und abwartet.............
• Nicht entscheidbare Probleme sind algorithmisch, d.h. mit Hilfe von Computern unlösbar.
• Die Verantwortung für die Terminierung von Programmen kann niemals einer Maschine
übertragen werden, sie bleibt beim Menschen.
• Die Unentscheidbarkeit des Halteproblems ist unabhängig von der Programmiersprache (ohne
Beweis).
• Das Halteproblem bedeutet, dass es Aufgabenstellungen gibt, die nicht mit Computern gelöst
werden können.
Es gibt weitere unlösbare Probleme: Es gibt kein sicheres Virenprüfprogramm!
Satz von Dowling (1989)
Es ist unmöglich ein Programm zu formulieren, das selber sicher ist (keinen Virus verbreitet)
und
von jedem beliebigen Programm entscheiden kann, ob dieses virenfrei ist oder nicht.
Navigationsprogramme
Es gibt kein Programm, das für jedes mögliche Navigationsprogramm dessen Korrektheit überprüft.
Grammatiken
Das Problem, ob für eine kontextfreie Grammatik L(G) = { } gilt, ist entscheidbar.
Das Problem, ob für eine beliebige Grammatik L(G) = { } gilt, ist nicht entscheidbar.
Unvollständigkeitssatz von Gödel (1931)
Es gibt korrekt gebaute Formeln der Zahlentheorie, die weder beweisbar, noch widerlegbar sind.
Wahrheit und mathematische Beweisbarkeit sind unterschiedliche Kategorien:
Der Unvollständigkeitssatz besagt, dass mathematische Theorien niemals alle wahren Aussagen
erfassen können.
Achtung: Der Unvollständigkeitssatz sagt nichts über einen Mangel des menschlichen Denkens
aus!
Seite 16 /09.10

Download Report