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

  1. Erstellen Sie zum angegebenen Programm 'test.pl' ein Struktogramm.
  2. Das hier besprochene Programm 'test.pl' und das Problem von 'game of life' sind nicht entscheidbar. Worin besteht der Unterschied bzw. die Unterschiede?
  3. Vergleichen Sie das Halteproblem mit dem allgemein bekannten Barbier-Paradoxon (siehe Weblink 3 und 4).

 

Weblinks

  1. de.wikipedia.org/wiki/Halteproblem
  2. www.gk-informatik.de/algo/halt.html
  3. de.wikipedia.org/wiki/Barbier-Paradoxon
  4. de.wikipedia.org/wiki/Russellsche_Antinomie

 

zurück


© ERG Saalfeld   -   Hans-Dietrich Kirmse   25.03.2019