LOOP-Programme

LOOP-Programme

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ässt. Die Menge aller LOOP-Programme wird mit LOOP bezeichnet.

Inhaltsverzeichnis

Eigenschaften

Jede primitiv-rekursive Funktion ist LOOP-berechenbar und umgekehrt[1].

Im Unterschied zu GOTO-Programmen und WHILE-Programmen terminieren LOOP-Programme immer[2]. 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)[3].

Ein Beispiel für eine berechenbare aber nicht LOOP-berechenbare totale Funktion ist die Ackermann-Funktion[4].

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:

\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: = {x0,x1,...} Variablennamen und c \in \mathbb{N} Konstanten.

Semantik

Ein Ausdruck der Form

x0 := x1 + c

bedeutet die Zuweisung des um c erhöhten Wertes der Variablen x1 an die Variable x0. Dabei ist für 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 c verminderten Wertes der Variablen x1 an die Variable x0. 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 x um c.

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

Ein Ausdruck der Form

P1; P2

bedeutet die Hintereinanderausführung der Teilprogramme P1 und P2 in dieser Reihenfolge. Ein Ausdruck der Form

LOOP x DO P END

bedeutet die x-fache Ausführung des Teilprogramms P, wobei x den Wert am Beginn der Abarbeitung darstellt. (Auch wenn x durch die Ausführung von P verändert wird, wird P nur so oft ausgeführt, wie x am Anfang war.) Hat x dabei den Wert Null, so wird das Teilprogramm 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 x0 die Summe der Werte der Variablen x1 und x2 zu.

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

Dabei bekommt zunächst x0 den aktuellen Wert von x1 zugewiesen und wird dann um den Wert von x2 inkrementiert.

Dieses Programm lässt 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 x0 um den Wert des Produktes der Werte der Variablen x1 und x2.

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 x1-fache Aufaddieren des Wertes von x2 zum Wert von x0 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

Einzelnachweise

  1. Schöning, 2001, S. 113
  2. Schöning, 2001, S. 101
  3. Schöning, 2001, S. 122
  4. Schöning, 2001, S. 102, S. 120

Literatur

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

Wikimedia Foundation.

Игры ⚽ Нужно сделать НИР?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Loop-Berechenbarkeit — 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… …   Deutsch Wikipedia

  • 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… …   Deutsch Wikipedia

  • Loop (Programmiersprache) — 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… …   Deutsch Wikipedia

  • Loop — (engl.: ‚Schleife‘ oder ‚Schlaufe‘) bezeichnet eine Universal Chess Interface Schachengine, siehe Loop (Schach). bei Druckwasserreaktoren einen Rohrleitungsstrang der Hauptkühlmittelleitung. in der Funktechnik eine Antennenbauweise, bei der die… …   Deutsch Wikipedia

  • LOOP-Programm — Dieser Artikel wurde auf den Seiten der Qualitätssicherung eingetragen. Bitte hilf mit, ihn zu verbessern, und beteilige dich bitte an der Diskussion! Folgendes muss noch verbessert werden: Lemma entspricht nicht Konvention 84.150.18.114… …   Deutsch Wikipedia

  • Loop (instruction) — Structure de contrôle En programmation impérative, une structure de contrôle est une commande qui contrôle l ordre dans lequel les différentes instructions d un algorithme ou d un programme informatique sont exécutées. On appelle aussi cet… …   Wikipédia en Français

  • Loop-Quantengravitation — Die Theorie der Schleifenquantengravitation (engl. loop quantum gravity), auch Loop Quantengravitation oder Loop Theorie genannt, ist ein Ansatz für eine Theorie der Quantengravitation, d. h. eine Theorie zur Vereinigung der Quantenphysik mit der …   Deutsch Wikipedia

  • Loop-Theorie — Die Theorie der Schleifenquantengravitation (engl. loop quantum gravity), auch Loop Quantengravitation oder Loop Theorie genannt, ist ein Ansatz für eine Theorie der Quantengravitation, d. h. eine Theorie zur Vereinigung der Quantenphysik mit der …   Deutsch Wikipedia

  • Loop Quantum Gravity — Die Theorie der Schleifenquantengravitation (engl. loop quantum gravity), auch Loop Quantengravitation oder Loop Theorie genannt, ist ein Ansatz für eine Theorie der Quantengravitation, d. h. eine Theorie zur Vereinigung der Quantenphysik mit der …   Deutsch Wikipedia

  • Fairlop Loop — The Fairlop Loop was a 6.5 mile (10 km) [ [http://www.cravensheritagetrains.co.uk/history.htm Cravens Heritage Trains History] ] branch line of the Great Eastern Railway (GER). It was opened to passenger traffic on 1 May 1903 (though it had… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”