LOOP-Programme spielen in der Theoretischen Informatik eine Rolle, insbesondere in Zusammenhang mit Berechenbarkeit. In der einfachen Programmiersprache LOOP kann man nur Additionen, Wertzuweisungen und endlich oft durchlaufene Schleifen schreiben.

Jede primitiv-rekursive Funktion ist LOOP-berechenbar und umgekehrt.

Im Unterschied zu GOTO-Programmen und WHILE-Programmen terminieren LOOP-Programme immer. Deswegen enthält die Menge der LOOP-Programme nur eine Untermenge der berechenbaren Funktionen und damit eine Untermenge der WHILE- bzw. GOTO-Programme.

Ein Beispiel für eine Funktion die berechenbar, aber nicht LOOP-berechenbar ist, ist die Ackermann-Funktion.

Formale Definition

---

LOOP-Programme haben folgende Syntax in Backus-Naur-Form:

$P\; ::=\; x\_i\; :=\; x\_j\; +\; c\; \backslash ,\; |\; \backslash ,\; x\_i\; :=\; x\_j\; -\; c\; \backslash ,\; |\; \backslash ,\; P;P\; \backslash ,\; |\; \backslash ,\; \backslash mathrm\{LOOP\}\; \backslash ,\; x\_i\; \backslash ,\; \backslash mathrm\{DO\}\; \backslash ,\; P\; \backslash ,\; \backslash mathrm\{END\}$

Hierbei sind $Var\; :=\; \backslash \{\; x\_0,\; x\_1,\; ...\; \backslash \}$ Variablennamen und $c\; \backslash in\; \backslash mathbb\{N\}$.

$LOOP$ ist die Menge aller LOOP-Programme nach obiger Definition.

Eine Funktion, die ein LOOP-Programm nicht berechnen kann, ist beispielsweise die Ackermann-Funktion.

Beispiele

---

LOOP x DO P END bedeutet: Das Programm P wird x mal ausgeführt, wobei x den Wert am Beginn der Abarbeitung darstellt (auch wenn man x verändert, wird P nur so oft ausgeführt, wie x am Anfang war).

Simulation durch WHILE-Programm

---

Ein jedes LOOP-Programm LOOP x DO P END kann durch das folgende WHILE-Programm simuliert werden y := x WHILE y != 0 DO y := y-1; P END

Siehe auch

---

• µ-Rekursion
• WHILE-Programm
• GOTO-Programm
• Totale Funktion

Berechenbarkeitstheorie