In letzter Zeit beschäftigen wir uns in der Schule ein bisschen mit theoretischer Informatik und sind dabei auf das Halteproblem zu sprechen gekommen und haben einen interessanten Beweis gefunden, dass dieses Problem nicht lösbar ist.

Das Halteproblem beschäftigt sich mit der Fragen, ob es einen Algorithmus geben kann, der berechnet, ob ein anderer Algorithmus mit jeder Eingabe terminiert. Mit diesem Problem setzte sich schon Alan Turing auseinander und obwohl es nach einem sehr komplexen Problem aussieht ist der Beweis, dass das Halteproblem nicht lösbar ist, relativ einfach:

Man nimmt an, dass folgende Funktion existiert:

1
2
3
4
5

boolean halts ( String p )
{
        if ( Programm p terminert ) return true ;
        else return false ;
}

Diese Funktion sollte das Halteproblem lösen. Als Parameter p wird ein Programmtext übergeben und sollte dieser terminieren, gibt die Funktion true zurück und wenn nicht false.

Jetzt hat man noch eine Funktion test, die nur aus einer while-Schleife besteht. Die Bedinging der Schleife ist ein Aufruf von halts mit test als Parameter:

1
2
3
4

void test ( )
{
        while ( halts("test()") ) ;
}

Jetzt gibt es 2 Möglichkeiten, was passiert:

• test terminiert –> halts liefert true –> while-Schleife läuft endlos weiter –> test terminiert nicht

• test terminiert nicht –> halts liefert false –> while-Schleife wird nicht durchlaufen –> test terminiert

Dieses Paradoxon beweist, dass es keine Lösung für das Halteproblem geben kann.

Source: http://www.inf.fh-flensburg.de/lang/se/veri/halteproblem.htm