Endlosschleife, unendliche Wiederholung eines Programmteils in einem Computerprogramm aufgrund eines Programmierfehlers (Bug) oder Eingabefehlers. Ein Beispiel für eine Endlosschleife ist eine unendliche ►Rekursion.
In Pseudocode sieht eine rekusive Endlosschleife etwa so aus:
function Endlos (Daten):
TuWasMit (Daten);
Endlos (Daten);
return;
Diese Funktion ruft sich immer wieder selbst auf und erreicht nie ihr Ende, die return-Zeile. Endlosschleifen bewirken einen Absturz des Programms, da dieses den Programmteil nicht mehr verlassen und der Computer dadurch nicht mehr auf Eingaben reagieren kann. Vermutlich kennen alle PC-Besitzer den Effekt: Das Programm 'hängt fest' und muss per Resetknopf, Affengriff* oder Task-Manager auf die harte Tour abgebrochen werden. Es ist nicht möglich, durch bloße Analyse, also ohne das Programm selbst auszuführen, generell festzustellen, ob es mit bestimmten Eingabedaten korrekt beendet wird oder festhängt. Dieses Halteproblem wurde 1936 von dem britischen Mathematiker Alan Turing bewiesen.
'Fehler gibt es nicht' gibt es nicht
Hier der Beweis (zum Verständnis sind rudimentäre Programmierkenntnisse nützlich). Wir nehmen an, es gäbe eine Funktion Endlich, die zuverlässig feststellen kann, ob ein Programm mit bestimmten Eingabedaten eine Endlosschleife ausführt oder korrekt endet. Die Funktion sähe in Pseudocode so aus:
function Endlich (Programm, Daten):
if
('Programm' endet bei Eingabe von 'Daten')
then
return JA;
else return NEIN;
Endlich selbst soll natürlich keine Endlosschleifen enthalten, sondern immer zuverlässig enden, auch wenn das getestete Programm nicht endet. Wir definieren nun eine rekursive Funktion TesteMich, die Endlich aufruft:
function TesteMich (Programm):
if (Endlich
(Programm, Programm))
then TesteMich (Programm);
Diese etwas fiese Funktion endet nur, wenn Programm nicht endet, wenn es sich selbst als Eingabedaten bekommt. Andernfalls läuft TesteMich in eine unendliche Rekursion: Die Funktion ruft sich selbst immer wieder auf, so dass sie niemals endet. Wenn man nun der Funktion TesteMich diese selbst als Programm übergibt, führt dies zu einem logischen Widerspruch:
TesteMich (TesteMich);
Dieser Funktionsaufruf endet genau dann, wenn er nicht endet. Folglich kann es eine Funktion Endlich nicht geben. Für Programmierer bedeutet dies, dass sie niemals beweisen können, dass ein von ihnen abgeliefertes Programm fehlerfrei ist. Dies klingt nicht sehr aufregend (außer vielleicht für Programmierer). Der Beweis hatte jedoch 1936 eine Schockwirkung auf das mathematische Weltbild, obwohl es damals noch keine Computer gab. Turing bezog ihn lediglich auf einen hypothetischen, von ihm selbst definierten Computer, eine Turingmaschine. Doch aus dem Beweis lässt sich folgern, dass manche Probleme im Rahmen des mathematischen Formalismus prinzipiell unlösbar sind. Eine Folgerung, die bereits 6 Jahre vorher Gödel in seinem ►Unvollständigkeitssatz gezogen hatte.
Kann Gott bugfrei programmieren?
Aus Problemen wie dem Halteproblem und dem Unvollständigkeitssatz ergeben sich philosophische und religiöse Konsequenzen. ►Allwissenheit führt zu logischen Widersprüchen: Wenn die Fehlerfreiheit eines Programms prinzipiell nicht entscheidbar ist, so kann auch ►Gott nicht wissen, ob ein von ihm geschriebenes Programm fehlerfrei ist. Die Frage allerdings, ob gewisse Mängel in der Schöpfung hierauf zurückzuführen sind, gehört vermutlich ebenfalls zu den nichtentscheidbaren Problemen.
* [Strg]-[Alt]-[Entf]
Weblinks zum Thema
■ Grenzen
der Berechenbarkeit
■ Grundlagen
der Linguistik
■ Alan Turing