prev up next

Previous: Korrektheit und Terminierung Up: Komplexität und Verifikation Next: Sortieren

Halteproblem

Beh.:
Es gibt kein Programm, welches entscheidet, ob ein gegebenes Programm, angesetzt auf einen gegebenen Input, anhält.

Beweis durch Widerspruch

Annahme: Es gibt eine Methode


static boolean haltetest (char[]s, char[]t)
/* liefert true, falls das durch die Zeichenkette s dargestellte
 * Java-Programm bei den durch die Zeichenkette t dargestellten Eingabedaten
 * anhaelt; liefert false, sonst */

Dann lässt sich folgendes Java-Programm in der Datei Quer.java konstruieren:


public class Quer {

import AlgoTools.IO;

    public static void main(String argv[]) {

        char[] s = IO.readChars();
        if (haltetest(s,s)) while (true);
    }
}

Sei q der String, der in der Datei Quer.java steht.

Was passiert bei Aufruf von

java Quer
und Eintippen von q ?

1. Fall: Hält an haltetest( q , q ) == false
    Quer angesetzt auf q hält nicht!
2. Fall: Hält nicht haltetest( q , q ) == true
    Quer angesetzt auf q hält an!
       

Also kann es die Methode haltetest nicht geben!


prev up next
Previous: Korrektheit und Terminierung Up: Komplexität und Verifikation Next: Sortieren