~2025-37651-59: /* IF THEN ELSE */

2025-12-01T15:47:25Z

IF THEN ELSE

Neue Seite

'''LOOP-Programme''' sind [[Computerprogramm|Programme]] in der [[Programmiersprache]] '''LOOP''', einer stark eingeschränkten, modellhaften Sprache, die nur die Formulierung von [[Addition]]en, [[Wertzuweisung]]en und endlich oft durchlaufende [[Schleife (Programmierung)|Schleifen]] erlaubt. LOOP-Programme spielen in der [[Theoretische Informatik|Theoretischen Informatik]] eine Rolle, insbesondere im Zusammenhang mit [[Berechenbarkeit]]. Eine [[Funktion (Mathematik)|Funktion]] heißt '''LOOP-berechenbar''', wenn sie sich als LOOP-Programm formulieren lässt. Die Menge aller LOOP-Programme wird mit <math>\mathit{LOOP}</math> bezeichnet.

== Eigenschaften ==
Aufgrund ihrer Definition [[Terminiertheit|terminieren]] LOOP-Programme für alle Eingaben und definieren daher [[totale Funktion]]en<ref>{{Literatur |Autor=[[Uwe Schöning]] |Titel=Theoretische Informatik- kurz gefasst |Auflage=5. |Verlag=Spektrum Akademischer Verlag |Ort=Heidelberg |Datum=2008 |ISBN=978-3-8274-1824-1 |Seiten=93}}</ref>. Damit stehen sie im Kontrast zu [[GOTO-Programm]]en und [[WHILE-Programm]]en, bei denen eine Terminierung des Programms nicht garantiert ist.

Die Menge der durch LOOP-Programme berechenbaren Funktionen ist eine echte Untermenge der [[Berechenbare Funktion|berechenbaren]] totalen Funktionen (und damit auch eine Untermenge der durch WHILE- bzw. GOTO-Programme berechenbaren Funktionen)<ref name=":0">{{Literatur |Autor=[[Uwe Schöning]] |Titel=Theoretische Informatik- kurz gefasst |Auflage=5. |Verlag=Spektrum Akademischer Verlag |Ort=Heidelberg |Datum=2008 |ISBN=978-3-8274-1824-1 |Seiten=93,94}}</ref>. Ein Beispiel für eine berechenbare, aber nicht LOOP-berechenbare [[totale Funktion]] ist die [[Ackermann-Funktion]]<ref>{{Literatur |Autor=[[Uwe Schöning]] |Titel=Theoretische Informatik- kurz gefasst |Auflage=5. |Verlag=Spektrum Akademischer Verlag |Ort=Heidelberg |Datum=2008 |ISBN=978-3-8274-1824-1 |Seiten=94,112}}</ref>.

Die Menge der LOOP-berechenbaren Funktionen entspricht der Menge der [[primitiv-rekursive Funktion|primitiv-rekursiven Funktionen]]<ref>{{Literatur |Autor=[[Uwe Schöning]] |Titel=Theoretische Informatik- kurz gefasst |Auflage=5. |Verlag=Spektrum Akademischer Verlag |Ort=Heidelberg |Datum=2008 |ISBN=978-3-8274-1824-1 |Seiten=105}}</ref>.

== Formale Definition ==
=== Syntax ===
LOOP-Programme bestehen aus den Symbolen <code>LOOP</code>, <code>DO</code>, <code>END</code>, <code>:=</code>, <code>+</code>, <code>-</code> und <code>;</code> sowie einer beliebigen Anzahl von Variablen und Konstanten. LOOP-Programme haben folgende [[Syntax]] in modifizierter [[Backus-Naur-Form]]:

:<math>\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}
</math>
Hierbei sind <math>\mathit{Var} := \{ x_0, x_1, ... \}</math> Variablennamen und <math>c \in \mathbb{N}</math> Konstanten.

=== Semantik ===
Ein Ausdruck der Form
x0 := x1 + c
bedeutet die Zuweisung des um <math>c</math> erhöhten Wertes der Variablen <math>x_1</math> an die Variable <math>x_0</math>. Dabei ist für <math>c</math> 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 <math>c</math> verminderten Wertes der Variablen <math>x_1</math> an die Variable <math>x_0</math>. 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 <code>:=</code> erscheinen. Ein Ausdruck der Form
x := x + c
erhöht beispielsweise den Wert der Variablen <math>x</math> um <math>c</math>.

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

Ein Ausdruck der Form
''P''1; ''P''2
bedeutet die Hintereinanderausführung der Teilprogramme <math>P_1</math> und <math>P_2</math> in dieser Reihenfolge. Ein Ausdruck der Form
LOOP x DO ''P'' END
bedeutet die <math>x</math>-fache Ausführung des Teilprogramms <math>P</math>, wobei <math>x</math> den Wert am Beginn der Abarbeitung darstellt. (Auch wenn <math>x</math> durch die Ausführung von <math>P</math> verändert wird, wird <math>P</math> nur so oft ausgeführt, wie <math>x</math> am Anfang war.) Hat <math>x</math> dabei den Wert Null, so wird das Teilprogramm <math>P</math> innerhalb des LOOP-Ausdrucks überhaupt nicht ausgeführt. Dieser Umstand erlaubt die Formulierung von [[Verzweigung (Programmierung)|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 <math>x_0</math> die Summe der Werte der Variablen <math>x_1</math> und <math>x_2</math> zu.
x0 := x1 + 0;
LOOP x2 DO
x0 := x0 + 1
END
#
Dabei bekommt zunächst <math>x_0</math> den aktuellen Wert von <math>x_1</math> zugewiesen und wird dann um den Wert von <math>x_2</math> inkrementiert.

Dieses Programm lässt sich wie ein 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.

Dabei gilt zu beachten, dass LOOP-Programme keine Unterprogramme aufrufen können<ref>{{Internetquelle |autor=Till Tantau |url=http://www.tcs.uni-luebeck.de/downloads/mitarbeiter/tantau/2009-ws-ti.pdf |titel=Vorlesungsskript Theoretische Informatik |werk=Institut für Theoretische Informatik - Universität zu Lübeck |hrsg= |datum=2010-02-12 |seiten=154–156 |abruf=2019-01-23 |sprache=de |zitat=Unterprogramme sind nicht erlaubt.}}</ref>, sondern diese Unterprogramme [[Inline-Ersetzung|inlined]] und somit ein Teil des Hauptprogramms werden<ref>{{Literatur |Autor=Uwe Schöning |Titel=Theoretische Informatik - kurz gefasst |Hrsg= |Sammelwerk= |Band= |Nummer= |Auflage=5 |Verlag=Spektrum Akademisch Verlag |Ort= |Datum= |ISBN= |Seiten=102 |Zitat=Die Funktion g (...) kann formal durch eine entsprechende Einsetzung definiert werden (...)}}</ref><ref name=":0" />. Andernfalls bestände die Möglichkeit einer zirkulären Abhängigkeit und damit einhergehend der Verlust der endlichen Laufzeit von LOOP-Programmen.

=== Multiplikation ===
Das folgende LOOP-Programm erhöht den Wert der Variablen <math>x_0</math> um den Wert des Produktes der Werte der Variablen <math>x_1</math> und <math>x_2</math>.
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 <math>x_1</math>-fache Addieren des Wertes von <math>x_2</math> zum Wert von <math>x_0</math> realisiert.

Durch Einsetzen des LOOP-Programms für die Addition erhält man das äquivalente Programm in der ursprünglichen LOOP-Syntax.

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

=== IF THEN ELSE ===
Das folgende LOOP-Programm simuliert eine „if x1 > c then P1 else P2“-Anweisung, wobei x1 eine Variable, c eine Konstante und P1, P2 beliebige LOOP-Programme sind. In dem Programm werden drei neue Variablen xn1, xn2, xn3 verwendet.
xn1:=x1-c; xn2:=0; xn3:=1;
LOOP xn1 DO
xn2 := 1
xn3 := 0
END;
LOOP xn2 DO
P1
END;
LOOP xn3 DO
P2
END;
#

Das folgende LOOP-Programm simuliert eine „if x1 = c then P1 else P2“-Anweisung, wobei x1 eine Variable, c eine Konstante und P1, P2 beliebige LOOP-Programme sind. In dem Programm werden vier neue Variablen xn1, xn2, xn3, xn4 verwendet.
xn1:=x1-(c-1); xn2:=x1-c; xn3:=1; xn4:=1;
LOOP xn1 DO
LOOP xn2 DO
xn3:=0;
END;
LOOP xn3 DO
P1;
xn4:=0;
END
END;
LOOP xn4 DO
P2
END
#

== 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]]
* [[WHILE-Programm]]
* [[GOTO-Programm]]

== Einzelnachweise ==
<references />

== Literatur ==
* {{Literatur |Autor=[[Uwe Schöning]] |Titel=Theoretische Informatik - kurzgefasst |Auflage=4. |Verlag=Spektrum Akademischer Verlag |Datum=2001 |ISBN=3-8274-1099-1}}

[[Kategorie:Berechenbarkeitstheorie]]

LOOP-Programm - Versionsgeschichte

~2025-37651-59: /* IF THEN ELSE */