LOOP-Programm

LOOP-Programme sind Programme in der Programmiersprache LOOP, einer stark eingeschränkten, modellhaften Sprache, die nur die Formulierung von Additionen, Wertzuweisungen und endlich oft durchlaufenen Schleifen erlaubt. LOOP-Programme spielen in der Theoretischen Informatik eine Rolle, insbesondere in Zusammenhang mit Berechenbarkeit. Eine Funktion heißt LOOP-berechenbar, wenn sie sich als LOOP-Programm formulieren läßt. Die Menge aller LOOP-Programme wird mit $LOOP$ bezeichnet.

Eigenschaften

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

Im Unterschied zu GOTO-Programmen und WHILE-Programmen terminieren LOOP-Programme immer. Deswegen ist die Menge der durch LOOP-Programme berechenbaren Funktionen eine echte Untermenge der berechenbaren Funktionen (und damit eine Untermenge der durch WHILE- bzw. GOTO-Programme berechenbaren Funktionen).

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

Formale Definition

LOOP-Programme bestehen aus den Symbolen LOOP, DO, END, :=, +, - und ; sowie einer beliebigen Anzahl von Variablen und Konstanten. LOOP-Programme haben folgende Syntax in modifizierter Backus-Naur-Form:

${\begin{array}{lrl}P&::=&x_{i}:=x_{j}+c\\&|&x_{i}:=x_{j}-c\\&|&P;P\\&|&\mathrm {LOOP} \,x_{i}\,\mathrm {DO} \,P\,\mathrm {END} \end{array}}$

Hierbei sind $Var:=\{x_{0},x_{1},...\}$ Variablennamen und $c\in \mathbb {N}$ Konstanten.

Die in einem LOOP-Programm verwendeten Variablen werden vor Beginn des Programmablaufs mit vorgegeben Initialwerten vorbelegt. Bei der Ausführung von Zuweisungen werden negative Werte implizit durch Nullen ersetzt.

Ein Ausdruck der Form

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.)

Beispielprogramme

Addition

Das folgende LOOP-Programm weist der Variablen $x_{0}$ die Summe der Werte der Variablen $x_{1}$ und $x_{2}$ zu.

x0 := x1 + 0;
LOOP x2 DO
   x0 := x0 + 1
END

Dabei bekommt zunächst $x_{0}$ den aktuellen Wert von $x_{1}$ zugewiesen und wird dann um den Wert von $x_{2}$ inkrementiert.

Dieses Programm läßt sich als Unterprogramm in anderen LOOP-Programmen verwenden. Solche Verwendungen werden durch eine einfache Erweiterung der ursprünglichen LOOP-Syntax in der Form

x0 := x1 + x2

beschrieben.

Multiplikation

Das folgende LOOP-Programm erhöht den Wert der Variablen $x_{0}$ um den Wert des Produktes der Werte der Variablen $x_{1}$ und $x_{2}$.

LOOP x1 DO
  x0 := x0 + x2
END

Das Programm benutzt dabei das im ersten Beispiel definierte Unterprogramm der Addition. Die ausgeführte Multiplikation wird dabei durch das $x_{1}$-fache Aufaddieren des Wertes von $x_{2}$ zum Wert von $x_{0}$ realisiert.

Simulation von LOOP-Programmen 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