prev up next

Previous: Korrektheit und Terminierung Up: Komplexität, Verifikation, Terminierung 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 haltetest in der Klasse Fee:

public class Fee {
  public 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:

import AlgoTools.IO;
public class Quer {
    public static void main(String[] argv) {
        char[] s = IO.readChars();
        if (Fee.haltetest(s,s)) while (true);
    }
}

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

Was passiert, wenn das Programm Quer.class auf den String q angesetzt wird ? D.h.

java Quer < Quer.java

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

$\Rightarrow$ Also kann es die Methode haltetest nicht geben!


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