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 durchlaufende Schleifen erlaubt. LOOP-Programme spielen in der Theoretischen Informatik eine Rolle, insbesondere im Zusammenhang mit Berechenbarkeit. Eine Funktion heißt LOOP-berechenbar, wenn sie sich als LOOP-Programm formulieren lässt. Die Menge aller LOOP-Programme wird mit ${\displaystyle {\mathit {LOOP}}}$ bezeichnet.

Eigenschaften

Aufgrund ihrer Definition terminieren LOOP-Programme für alle Eingaben und definieren daher totale Funktionen. Damit stehen sie im Kontrast zu GOTO-Programmen und WHILE-Programmen, bei denen eine Terminierung des Programms nicht garantiert ist.

Die Menge der durch LOOP-Programme berechenbaren Funktionen ist eine echte Untermenge der berechenbaren totalen Funktionen (und damit auch eine Untermenge der durch WHILE- bzw. GOTO-Programme berechenbaren Funktionen). Ein Beispiel für eine berechenbare, aber nicht LOOP-berechenbare totale Funktion ist die Ackermann-Funktion.

Die Menge der LOOP-berechenbaren Funktionen entspricht der Menge der primitiv-rekursiven Funktionen.

Formale Definition

Syntax

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:

${\displaystyle {\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 ${\displaystyle {\mathit {Var}}:=\{x_{0},x_{1},...\}}$ Variablennamen und ${\displaystyle c\in \mathbb {N} }$ Konstanten.

Semantik

Ein Ausdruck der Form

x0 := x1 + c 

bedeutet die Zuweisung des um ${\displaystyle c}$ erhöhten Wertes der Variablen ${\displaystyle x_{1}}$ an die Variable ${\displaystyle x_{0}}$. Dabei ist für ${\displaystyle c}$ der Wert Null zulässig, so dass sich auch die direkte Zuweisung des Wertes einer Variablen an eine andere Variable mit diesem syntaktischen Konstrukt formulieren lässt:

x0 := x1 + 0 

Ein Ausdruck der Form

x0 := x1 - c 

bedeutet die Zuweisung des um ${\displaystyle c}$ verminderten Wertes der Variablen ${\displaystyle x_{1}}$ an die Variable ${\displaystyle x_{0}}$. Bei der Ausführung von Zuweisungen werden negative Werte implizit durch Nullen ersetzt.

Variablen dürfen in Zuweisungsausdrücken gleichzeitig auf der linken und auf der rechten Seite des Symbols := erscheinen. Ein Ausdruck der Form

x := x + c 

erhöht beispielsweise den Wert der Variablen ${\displaystyle x}$ um ${\displaystyle c}$.

Die in einem LOOP-Programm verwendeten Variablen werden vor Beginn des Programmablaufs mit vorgegebenen Initialwerten vorbelegt.

Ein Ausdruck der Form

P1; P2

bedeutet die Hintereinanderausführung der Teilprogramme ${\displaystyle P_{1}}$ und ${\displaystyle P_{2}}$ in dieser Reihenfolge. Ein Ausdruck der Form

LOOP x DO P END 

bedeutet die ${\displaystyle x}$-fache Ausführung des Teilprogramms ${\displaystyle P}$, wobei ${\displaystyle x}$ den Wert am Beginn der Abarbeitung darstellt. (Auch wenn ${\displaystyle x}$ durch die Ausführung von ${\displaystyle P}$ verändert wird, wird ${\displaystyle P}$ nur so oft ausgeführt, wie ${\displaystyle x}$ am Anfang war.) Hat ${\displaystyle x}$ dabei den Wert Null, so wird das Teilprogramm ${\displaystyle P}$ innerhalb des LOOP-Ausdrucks überhaupt nicht ausgeführt. Dieser Umstand erlaubt die Formulierung von Verzweigungen in LOOP-Programmen durch die bedingte Ausführung von Teilprogrammen in Abhängigkeit vom Wert einer Variablen.

Beispielprogramme

Addition

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

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

1. WHILE-Programm
2. GOTO-Programm

Literatur

• Uwe Schöning: Theoretische Informatik - kurzgefasst. 4. Auflage. Spektrum Akademischer Verlag, 2001, ISBN 3-8274-1099-1. 

wikipedia, wiki, enzyklopädie, buch, bibliothek, artikel, lesen, kostenlos herunterladen, Informationen über LOOP-Programm, Was ist LOOP-Programm? Was bedeutet LOOP-Programm?