Die Webseiten der Fachschaft Informatik am ERG Saalfeld
Halteproblem
Es soll die Fragestellung untersucht werden, ob es ein Programm gibt (geben kann),
welches ein beliebiges anderes Programm daraufhin untersucht, ob es irgend welche Endlos-Schleifen
enthält oder nicht.
Wir programmieren als einen solchen Programmtester das Programm "test.pl".
Programm
#!/usr/bin/perl
use strict;
use warnings;
sub haelt {
my @quelltext = @_;
my $rueckgabe;
# hier unbekannter funktionierender Quelltext
# wenn das Programm haelt, dann soll eine 1 zurückgegeben werden
# wenn das Programm nicht hält, dann eine 0 zurückgegeben werden
return $rueckgabe;
}
# wir lesen das Programm ein
my $datei = 'dateiname.pl';
open FILE, '<', $datei or die "konnte $datei nicht zum Lesen oeffnen. $!\n";
my @zeilen = <FILE>;
close FILE;
if (&haelt(@zeilen) == 1) {
my $x = 1;
while ($x == 1) { };
}
else {
print "haelt nicht!\n";
}
__END__
Bemerkungen
- Gibt die Funktion "haelt" eine 1 zurück, so geht das Programm in eine Endlosschleife (im Quelltext: while ($x == 1) { }; ), hält also nicht.
- Gibt die Funktion "haelt" eine 0 zurück, wird "hält nicht!" ausgegeben (im Quelltext: print "haelt nicht!
"; ) und das Programm hält.
wenn wir jetzt den eigenen Quelltext einlesen, führt dies zu folgenden Widersprüchen:
- Kommt der Algorithmus zu dem Ergebnis, dass er hält, so geht das Programm hierdurch in eine Endlosschleife. -> Widerspruch
- Umgekehrt, wird zurückgegeben, dass das Programm nicht hält, so hält es dadurch. -> Widerspruch
Fazit:
Das Halte-Problem ist nicht entscheidbar.
Aufgaben
- Erstellen Sie zum angegebenen Programm 'test.pl' ein Struktogramm.
- Das hier besprochene Programm 'test.pl' und das Problem von 'game of life' sind nicht entscheidbar. Worin besteht der Unterschied bzw. die Unterschiede?
- Vergleichen Sie das Halteproblem mit dem allgemein bekannten Barbier-Paradoxon (siehe Weblink 3 und 4).
Weblinks
- de.wikipedia.org/wiki/Halteproblem
- www.gk-informatik.de/algo/halt.html
- de.wikipedia.org/wiki/Barbier-Paradoxon
- de.wikipedia.org/wiki/Russellsche_Antinomie
zurück
© ERG Saalfeld - Hans-Dietrich Kirmse 25.03.2019
|