Infiniter Regress

Der Ausdruck infiniter Regress (auch unendlicher Regress oder Endlosrekursion; regressus in/ad infinitum) beschreibt einen „endlose[n] Rückgang in einer unendlichen Reihe“. Er wird allgemein in der Philosophie, insbesondere in der Logik und Argumentationstheorie, sowie in der Mathematik und Informatik verwendet.

Infiniter Regress in der Mathematik und Informatik

In der Mathematik und Informatik bezeichnet „infiniter Regress“ einen endlosen Selbstaufruf. Ein infiniter Regress entsteht beispielsweise durch eine Funktion, die auf sich selbst verweist (Rekursion), ohne dass eine gültige Abbruchbedingung den Prozess jemals beendet.

Beispielsweise ist die Fibonacci-Folge rekursiv, jedoch entsteht hier kein infiniter Regress. Diese ist definiert als:

$f(1)=0;f(2)=1$

$f(n)=f(n-1)+f(n-2)$

d. h., es werden die ersten zwei Folgenglieder zu Eins definiert, und das n-te als die Summe der zwei vorherigen Folgenglieder. Ein Beispiel für eine infinit regressive Folge wäre

$f(n)=f(n)$.

Möchte man hier das n-te Folgenglied berechnen, so tritt nach Funktionsvorschrift dieser Prozess in eine Endlosschleife. Die Funktion $f$ ruft sich dabei ständig selbst auf, ohne – wie bei der Fibonacci-Folge – das Resultat auf eine der Anfangsbedingungen zurückzuführen.

Zur Erkennung und Vermeidung von infinitem Regress, insbesondere von Computerprogrammen, bedient man sich der semantischen Verifikation von rekursiven Funktionen. Der Beweis, dass kein infiniter Regress vorliegt, wird dann zumeist mittels einer Schleifeninvariante geführt (siehe auch Invariante). Dieser Beweis ist allerdings nicht immer nach einem bestimmten Verfahren möglich (siehe Halteproblem).