Informatikmaterialien |
Startseite | Informatik | Physik | Mathematik | Sonstiges | |
Richard-Wossidlo-Gymnasium Ribnitz-Damgarten |
---|
Lothar Collatz stellte 1937 folgendes Problem vor. Endet die Folge
stets auf 1 für beliebige natürliche Zahlen a0?Beispiele:
- a0 = 23: 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1
- a0 = 49: 49, 148, 74, 37, 112, 56, 28, 14, 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1
- a0 = 75: 75, 226, 113, 340, 170, 85, 256, 128, 64, 32, 16, 8, 4, 2, 1
Aufgabe: Man entwickle unter Verwendung des Struktogramms (3A + 1) ein Programm und untersuche, ob der Algorithmus für verschiedene Startwerte stoppt.
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?
Angenommen es ist selbststoppend. Startet man nun das Programm SELTSAM und gibt ihm seinen Quelltext als Eingabe, so wird der gleiche Algorithmus abgearbeitet, wie beim Stopp-Test und damit die Variable stopp auf true gesetzt. Das Programm gibt nun aus, dass es selbststoppend ist, bleibt aber dann in der Endlosschleife hängen, ist also nicht selbststoppend. Damit steht es im Widerspruch zur Annahme.
Angenommen es ist nicht selbststoppend. Auch hier wird das Programm SELTSAM wie oben beschrieben abgearbeitet und die Variable stopp erhält den Wert false. Der Algorithmus gibt nun aus "Das Programm ist nicht selbststoppend", hält aber anschließend. Damit ist aber wieder ein Widerspruch zur Annahme vorhanden.
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. |