Das Kefk Network Wiki befindet sich im Testbetrieb.

LOOP-Programm

Aus Kefk.

(Weitergeleitet von Loop-Programm)
Wechseln zu: Navigation, Suche

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 ist die Menge der durch LOOP-Programme berechenbaren Funktionen nur 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.

Inhaltsverzeichnis

Formale Definition

Jedes LOOP-Programm besteht 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:

P ::= x_i := x_j + c \, | \, x_i := x_j - c \, | \, P;P \, | \, \mathrm{LOOP} \, x_i \, \mathrm{DO} \, P \, \mathrm{END}

Hierbei sind Var: = {x0,x1,...} Variablennamen und c \in \mathbb{N} Konstanten.

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

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


Beispiel Addition x0 := x1 + x2

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

Beispiel Multiplikation x0 := x1 * x2 

LOOP x1 DO
  x0 := x0 + x2
END

Hinweis: Die Multiplikation benutzt das oben definierte Unterprogramm der Addition.

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

Wikipedia
 Dieses Dokument entstammt in seiner ersten oder einer späteren Version der deutschsprachigen Wikipedia. Es ist dort zu finden unter dem Stichwort LOOP-Programm, die Liste der bisherigen Autoren befindet sich in der Versionsliste; die Originalfassung kann dort auch bearbeitet werden. Alle Texte der Wikipedia und ihre Derivate stehen unter der GNU-Lizenz für freie Dokumentation.
Von „http://www.kefk.org/wiki/LOOP-Programm“
Persönliche Werkzeuge