Informatikmaterialien 
von Tino Hempel

Startseite | Informatik | Physik | Mathematik | Sonstiges |


Richard-Wossidlo-Gymnasium Ribnitz-Damgarten
Fachbereich Informatik


Halteproblem
(nach Breier, N.: Grenzen des Computereinsatzes. Teil 2. In LogIn 10 (1990) Heft 3 und dem zugehörigen Materialien unter der  
URL: http://www.bildung-mv.de/download/fortbildungsmaterial/paket-theoretische-informatik.exe [02.02.2005])


Das Collatz-Problem

Lothar Collatz stellte 1937 folgendes Problem vor. Endet die Folge

Collatz
stets auf 1 für beliebige natürliche Zahlen a0?

Beispiele:

Aufgabe: Man entwickle unter Verwendung des Struktogramms (3A + 1) ein Programm und untersuche, ob der Algorithmus für verschiedene Startwerte stoppt.

o

Stopp-Tester

Die entwickelte Software untersucht letztlich stets eine endliche Menge von Eingaben und prüft, ob die Folge auf Eins endet. Bisher hat man dies für alle Zahlen bis 250 positiv beantworten können. Dennoch könnte schon die nächste Zahl das Programm in eine Endlosschleife führen. Sinnvoll wäre ein Programm, mit dessen Hilfe man für jedes beliebige Programm entscheiden kann, ob es mit jeder beliebigen Eingabe nach endlich vielen Schritten abbricht oder nicht?

Dies dürfte kein Problem sein, da jedes Programm als eine Zeichenkette dargestellt werden kann und damit als Eingabe für das Stopp-Test-Programm dienen kann. Man könnte sogar für Testzwecke das Stopp-Programm selbst als Eingabe nutzen. Die Informatiker nennen dies "Selbstanwendbarkeitsproblem". 

Wie kann so ein Programm aussehen: sicherlich ist ein bestimmter Programmvorbau notwendig. Da jedoch zum Ende des Programms die Ausgabe der Entscheidung ansteht, hat das Programm sicherlich folgende Gestalt, wobei stopp eine entsprechende boolesche Variable ist:

BEGIN
{...}
IF stopp
THEN writeln('Das Programm ist selbststoppend')
ELSE writeln('Das Programm ist nicht selbststoppend');
END.

Nun könnte ja ein fieser Programmierer den Quelltext nehmen und hinter die positive Antwort eine Endlosschleife einbauen und damit das Programm SELTSAM erschaffen:

BEGIN
{...}
IF stopp
THEN
BEGIN
writeln('Das Programm ist selbststoppend');
while true do;
END
ELSE writeln('Das Programm ist nicht selbststoppend');
END.

Ist dieses neue Programm nun selbststoppend oder nicht?

Da SELTSAM weder die Eigenschaft "selbststoppend" noch deren logische Negation besitzt, kann es nach den Gesetzen der Logik nicht existieren. Dann kann es aber auch kein Programm Stopp-Tester.

Resümee:

Es ist nicht möglich von einem beliebigen Programm zu sagen, ob es nach endlich vielen Schritten stoppt oder nicht! Damit wurde (beweisbar) ein Problem gefunden, dass nicht mit Hilfe des Computers gelöst werden kann



zur Startseite
© Tino Hempel 1997 - 2007 Im Web vertreten seit 1994.
Eine Internet-Seite aus dem Angebot von Tino Hempel.

Für alle Seiten gilt der 
Haftungsausschluss/Disclaimer.