Es wird niemals eine Software geben, die sich eine andere Software anschaut und entscheidet, ob sie etwas bestimmtes macht.
In der theoretischen Informatik gibt es das Halteproblem.
Man kann kein Programm schreiben, das sich ein anderes beliebiges Programm anschaut und nach endlich vielen Schritten erkennt, ob es hält.
(Es kann auch interpretiert werden, aber man hat nicht beliebig Zeit. Wenn ein Programm exakt 10 Jahre läuft, kann man das nicht „testen“, da der Test ja auch 10 Jahren dauert.)
Nehmen wir an es gibt ein Programm
bollean willStop( char[] program )
das entscheidet, ob ein anderes Programm endet.
So sollte folgendes true ergeben:
willStop(„return“);
willStop(„for(int i=0;i<100000000;i++)print(i);“);
und folgendes false:
willStop(„while(true);“);
Eine zweites Methode:
void reverser( char[] program ) {
while ( willStop( program ) )
out.println( „willStop will stop“ );
}
Umgangssprachlich:
– Wenn willStop() true liefert, endet reverser() nicht.
– Wenn willStop() false liefert, endet reserver().
Frage: Was passiert bei folgendem Aufruf?
void reverser( „void reverser(char[]…“ );
Ausgefaltet:
void reverser( char[] program ) {
while ( willStop( „void reverser(char[]…“ ) )
out.println( „willStop will stop“ );
}
Stoppt reserver(), hat willStop(„void reserver…“) aber false gegeben. Aber warum ergibt willStop() dann false? Die Funktion stoppt doch? (Umgekehrtes gilt auch.)
Durch diesen Widerspruch muss die Annahme falsch sein, dass es willStop() überhaupt gibt.
Aus dem Seminar: Codeanalyse mit FindBugs, PMD, Checkstyle und JDepend
Danke, schöne Erinnerungen an Theoretische Infomatik!
Aber es sollte wohl heißen
Umgangssprachlich:
– Wenn willStop() true ergibt, endet reverser() nicht.
– Wenn willStop() false ergibt, endet reserver().
Ähem, ja. Fehler ist korrigiert.
Nur durch Ausführen, kann man in der Tat nie erkennen, dass ein Programm nicht endet. Durch die Analyse des Codes kann man es bei manchen Programmen aber doch erkennen. Man kann ja z.B. nachgucken, ob while-true-Schleifen kein breake; enthalten. Dann weiß man, dass (in Java) das Programm nicht enden kann.
Ich finde daher, dass es insgesamt etwas zu verallgemeinert ist.
BTW sind in dem Satz "Kann man kein Programm schreiben, das sich ein anderes Programm anschaut und nach endlich vielen Schritten erkennt, ob es hält." die ersten beiden Wörter verdreht.
Wir haben in der Schule in Mathematik auch mal einen "Beweis" durchgemacht, bei dem rausgekommen ist, daß 0=1
Irgendwo war natürlich ein versteckter Fehler – aber wie relevant sind solche Theorien?
Muss denn alles relevant und finanziell verwertbar sein? Es ist halt ein schöner Beweis. Bei einem Kunstwerk fragt man doch auch nicht, ob es relevant ist.