Das Halteproblem

für Java-Klassen

 

Gibt es eine Methode, die folgendes leistet:
"Ist p eine Klasse und x eine Zeichenfolge, so entscheidet die Methode, ob die Klasse p bei Eingabe von x terminiert." ?

Alternative Formulierung:
Gibt es ein Testprogramm, dass für andere Programme und beliebige Eingaben entscheidet, ob diese Programme anhalten (und eine Ausgabe erzeugen)?

Grobentwurf für die Java-Methode haelt:

static boolean haelt(text p, text x)

{ 
   boolean ergebnis; 

    if (p terminiert bei Eingabe von x) 
       ergebnis = true;
    else
       ergebnis = false;
    return ergebnis;
} // Ende von haelt

Annahme: Es gibt eine solche Methode. Kann sich mit ihr eine Klasse zunächst selbst testen?

Klasse Seltsam:

public class seltsam;
{
 static boolean haelt(text p, text x)

 {
    boolean ergebnis; 

    if (p terminiert bei Eingabe von x) 
       ergebnis = true;
    else
       ergebnis = false;
    return ergebnis;
 } // Ende von haelt

 public static void main (String [] argumente)
 {

    lies(seltsam.java);
    while (haelt(seltsam.java, seltsam.java)==true);
      /* Das ist eine Endlosschleife! */
   
    System.out.println("Bin fertig!");  
 } // Ende von main

} // Ende der Klasse seltsam 

Ergebnis: Der Selbsttest funktioniert nicht! Dann kann diese Klasse und diese Methode erst recht keine beliebigen anderen Klassen auf endliche Programmausführung überprüfen.

Grafische Darstellung des Sachverhaltes:

Satz von Turing (für Java-Methoden):

Es gibt keine Java-Methode, die für eine beliebige Klasse p und eine beliebige Eingabe x die Frage beantwortet, ob p auf x angewendet nach endlich vielen Schritten anhält oder nicht.

Alternative Formulierung:
Es gibt kein Testprogramm, dass für andere Programme und deren Eingaben entscheidet, ob sie anhalten (und eine Ausgabe liefern)!

Allgemein:

Die Halteeigenschaft für Programme ist unentscheidbar.
Die Verantwortung für das Anhalten (die Terminierung) von Programmen wird niemals einer Maschine übertragen werden können; sie bleibt beim Menschen.

Entscheidbar sind:

  • Geradeausprogramme
  • Programme mit ausschließlich Vorwärtsverzweigungen


Unentscheidbar:

  • Programme mit Schleifen
  • rekursive Programme