Notice: Unexpected clearActionName after getActionName already called in /var/www/html/includes/context/RequestContext.php on line 338
LOOP-Programm – Wikipedia (Deutsch) – Lokale Kopie Zum Inhalt springen

LOOP-Programm

aus Wikipedia, der freien Enzyklopädie
(Weitergeleitet von 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 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 <math>\mathit{LOOP}</math> bezeichnet.

Eigenschaften

Aufgrund ihrer Definition terminieren LOOP-Programme für alle Eingaben und definieren daher totale Funktionen<ref>{{#invoke:Vorlage:Literatur|f}}</ref>. 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)<ref name=":0">{{#invoke:Vorlage:Literatur|f}}</ref>. Ein Beispiel für eine berechenbare, aber nicht LOOP-berechenbare totale Funktion ist die Ackermann-Funktion<ref>{{#invoke:Vorlage:Literatur|f}}</ref>.

Die Menge der LOOP-berechenbaren Funktionen entspricht der Menge der primitiv-rekursiven Funktionen<ref>{{#invoke:Vorlage:Literatur|f}}</ref>.

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:

<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 := 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 

P1; P2

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 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>{{#if:|{{#iferror: {{#iferror:{{#invoke:Vorlage:FormatDate|Execute}}|}}| |}}}}{{#if:Till Tantau|Till Tantau: }}{{#if:|{{#if:Vorlesungsskript Theoretische Informatik|[{{#invoke:Vorlage:Internetquelle|archivURL|1={{#invoke:URLutil|getNormalized|1={{{archiv-url}}}}}}} {{#invoke:Vorlage:Internetquelle|TitelFormat|titel=Vorlesungsskript Theoretische Informatik}}]{{#if:| ({{{format}}})}}{{#if:| {{{titelerg}}}{{#invoke:Vorlage:Internetquelle|Endpunkt|titel={{{titelerg}}}}}}}}}|{{#if:http://www.tcs.uni-luebeck.de/downloads/mitarbeiter/tantau/2009-ws-ti.pdf%7C{{#if:{{#invoke:TemplUtl%7Cfaculty%7C}}%7C{{#invoke:Vorlage:Internetquelle%7CTitelFormat%7Ctitel={{#invoke:WLink%7CgetEscapedTitle%7C1=Vorlesungsskript Theoretische Informatik}}}}|[{{#invoke:URLutil|getNormalized|1=http://www.tcs.uni-luebeck.de/downloads/mitarbeiter/tantau/2009-ws-ti.pdf}} {{#invoke:Vorlage:Internetquelle|TitelFormat|titel={{#invoke:WLink|getEscapedTitle|1=Vorlesungsskript Theoretische Informatik}}}}]}}{{#if:| ({{{format}}}{{#if:Institut für Theoretische Informatik - Universität zu Lübeck2010-02-12154–156{{#if: 2019-01-23 | {{#if:{{#invoke:TemplUtl|faculty|}}||1}}}} 

          | )
          | {{#if:{{#ifeq:de|de||{{#if:de|1}}}}| ; 
              | )}}}}}}{{#if:| {{{titelerg}}}{{#invoke:Vorlage:Internetquelle|Endpunkt|titel={{{titelerg}}}}}}}}}}}{{#if:http://www.tcs.uni-luebeck.de/downloads/mitarbeiter/tantau/2009-ws-ti.pdf%7C{{#if:{{#invoke:URLutil%7CisResourceURL%7C1=http://www.tcs.uni-luebeck.de/downloads/mitarbeiter/tantau/2009-ws-ti.pdf}}%7C%7C}}}}{{#if:Vorlesungsskript Theoretische Informatik|{{#if:{{#invoke:WLink|isValidLinktext|1=Vorlesungsskript Theoretische Informatik|lines=0}}||}}}}{{#if: Institut für Theoretische Informatik - Universität zu Lübeck| In: {{#invoke:Vorlage:Internetquelle|TitelFormat|titel=Institut für Theoretische Informatik - Universität zu Lübeck}}}}{{#if: | {{#if: 2010-02-12154–156|,|{{#if: 2019-01-23 | {{#if:{{#invoke:TemplUtl|faculty|}}|;|,}}}}}}}}{{#if: 2010-02-12| {{#if:{{#invoke:DateTime|format|2010-02-12|noerror=1}}
            |{{#invoke:DateTime|format|2010-02-12|T._Monat JJJJ}}
            |{{#invoke:TemplUtl|failure|1=Fehler bei Vorlage:Internetquelle, datum=2010-02-12|class=Zitationswartung}} }}{{#if: 154–156|,|{{#if: 2019-01-23 | {{#if:{{#invoke:TemplUtl|faculty|}}|;|,}}}}}}}}{{#if: 154–156| S. 154–156{{#if: |,|{{#if: 2019-01-23 | {{#if:{{#invoke:TemplUtl|faculty|}}|;|,}}}}}}}}{{#if: {{#invoke:TemplUtl|faculty|}}| {{#if:154–1562010-02-12|{{#if:|archiviert|ehemals}}|{{#if:|Archiviert|Ehemals}}}} {{#if:|vom|im}} Vorlage:Referrer{{#if:{{#invoke:TemplUtl|faculty|}}| (nicht mehr online verfügbar)}}{{#if: | am {{#iferror: {{#iferror:{{#invoke:Vorlage:FormatDate|Execute}}|}}|{{{archiv-datum}}}{{#if:65031||(?)}}}}}}{{#if: Unterprogramme sind nicht erlaubt.2019-01-23|;}}}}{{#if: 2019-01-23| {{#if:154–1562010-02-12{{#invoke:TemplUtl|faculty|}}|abgerufen|Abgerufen}} {{#switch: {{#invoke:Str|len| {{#invoke:DateTime|format| 2019-01-23 |ISO|noerror=1}} }}
       |4=im Jahr
       |7=im
       |10=am
       |#default={{#invoke:TemplUtl|failure|1=Fehler bei Vorlage:Internetquelle, abruf=2019-01-23|class=Zitationswartung}} }} {{#invoke:DateTime|format|2019-01-23|T._Monat JJJJ}}
    | {{#invoke:TemplUtl|failure|1=Vorlage:Internetquelle | abruf=2026-MM-TT ist Pflichtparameter}} }}{{#if:{{#ifeq:de|de||{{#if:de|1}}}}|{{#if:Institut für Theoretische Informatik - Universität zu Lübeck2010-02-12154–156{{#if: 2019-01-23 | {{#if:{{#invoke:TemplUtl|faculty|}}||1}}}}
       |  (
       | {{#if: | |  (}}
       }}{{#ifeq:{{#if:de|de|de}}|de||
          {{#invoke:Multilingual|format|de|slang=!|split=[%s,]+|shift=m|separator=, }}}}{{#if: |{{#ifeq:{{#if:de|de|de}}|de||, }}{{{kommentar}}}}})}}{{#if: 2010-02-12154–156{{#if: 2019-01-23 | {{#if:{{#invoke:TemplUtl|faculty|}}||1}} }}deUnterprogramme sind nicht erlaubt.|{{#if: Unterprogramme sind nicht erlaubt.|: {{
 #if: 
 | „{{
     #ifeq: {{#if:{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|de}} | de
     | Vorlage:Str trim
     | {{#invoke:Vorlage:lang|flat}}
     }}“
 | {{#ifeq: {{#if:{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|de}} | de
     | „Vorlage:Str trim“
     | {{#invoke:Text|quote
         |1={{#if: 
              | {{#invoke:Vorlage:lang|flat}}
              | {{#invoke:Vorlage:lang|flat}} }}
         |2={{#if: {{#invoke:TemplUtl|faculty|}}|de-CH|de}}
         |3=1}} }}

}}{{#if: 

   |  (<templatestyles src="Person/styles.css" />{{#if:  | :  }}{{#if:  | , deutsch: „“ }})
   | {{#if: 
       |  ({{#if:  | , deutsch: „“ }})
       | {{#if:  |  (deutsch: „“) }}
 }}

}}{{#if: Unterprogramme sind nicht erlaubt. 

   | {{#if: 
       | {{#if: Unterprogramme sind nicht erlaubt.
           | Vorlage:": Text= und 1= gleichzeitig, bzw. Pipe zu viel }} }}
   | Vorlage:": Text= fehlt }}{{#if:  | {{#if: {{#invoke:Text|unstrip|{{{ref}}}}}
             | Vorlage:": Ungültiger Wert: ref=
             | {{{ref}}} }}

}}|.{{#if:{{#invoke:TemplUtl|faculty|}}|{{#if:||{{#ifeq: | JaKeinHinweis |{{#switch: 

   |0|=Vorlage:Toter Link/Core{{#if: http://www.tcs.uni-luebeck.de/downloads/mitarbeiter/tantau/2009-ws-ti.pdf
       | {{#if:  | [1] }} (Seite {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. Suche im Internet Archive (T)){{#if: 
           | {{#if: deadurlausgeblendet | | Vorlage:Toter Link/archivebot }}
         }}
       |   (Seite {{#switch:|no|0|=|#default=dauerhaft }}nicht mehr abrufbar{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}.)
     }}{{#switch: 
         |no|0|=
         |#default={{#if:  ||  }}
    }}{{#invoke:TemplatePar|check
         |opt      = inline= url= text= datum= date= archivebot= bot= botlauf= fix-attempted= checked=
         |cat      = Wikipedia:Vorlagenfehler/Vorlage:Toter Link
         |errNS    = 0
         |template = Vorlage:Toter Link
         |format   = 
         |preview  = 1
    }}{{#if: http://www.tcs.uni-luebeck.de/downloads/mitarbeiter/tantau/2009-ws-ti.pdf
      | {{#if:{{#invoke:URLutil|isWebURL|http://www.tcs.uni-luebeck.de/downloads/mitarbeiter/tantau/2009-ws-ti.pdf}}
          || {{#if:  ||  }} 
        }}
      | {{#if: 
           | {{#if:  ||  }}
           | {{#if:  ||  }}
        }}
    }}{{#if: 
       | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}}
             || {{#if:  ||  }} 
         }}
    }}{{#switch: deadurl
         |checked|deadurl|= 
         |#default=  {{#if:  ||  }}
    }}|#default= https://wiki-de.moshellshocker.dns64.de/index.php?title=Wikipedia:Defekte_Weblinks&dwl=http://www.tcs.uni-luebeck.de/downloads/mitarbeiter/tantau/2009-ws-ti.pdf Die nachstehende Seite ist {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar]{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. (Suche im Internet Archive. (T).)  {{#if: 
            | {{#if: deadurlausgeblendet | | Vorlage:Toter Link/archivebot }}
         }}Vorlage:Toter Link/Core{{#switch: 
          |no|0|=
          |#default= {{#if:  ||  }}
        }}{{#invoke:TemplatePar|check
         |all      = inline= url=
         |opt      = datum= date= archivebot= bot= botlauf= fix-attempted= checked=
         |cat      = Wikipedia:Vorlagenfehler/Vorlage:Toter Link
         |errNS    = 0
         |template = Vorlage:Toter Link
         |format   = 
         |preview  = 1
       }}{{#if: http://www.tcs.uni-luebeck.de/downloads/mitarbeiter/tantau/2009-ws-ti.pdf
       | {{#if:{{#invoke:URLutil|isWebURL|http://www.tcs.uni-luebeck.de/downloads/mitarbeiter/tantau/2009-ws-ti.pdf}}
          || {{#if:  ||  }} 
        }}
    }}{{#if: 
         | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}}
             || {{#if:  ||  }} 
           }}
    }}{{#switch: deadurl
         |checked|deadurl|= 
         |#default=  {{#if:  ||  }}
    }}[http://www.tcs.uni-luebeck.de/downloads/mitarbeiter/tantau/2009-ws-ti.pdf }}|{{#switch: 
   |0|=Vorlage:Toter Link/Core{{#if: http://www.tcs.uni-luebeck.de/downloads/mitarbeiter/tantau/2009-ws-ti.pdf
       | {{#if:  | [2] }} (Seite {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. Suche im Internet Archive (T)){{#if: 
           | {{#if:  | | Vorlage:Toter Link/archivebot }}
         }}
       |   (Seite {{#switch:|no|0|=|#default=dauerhaft }}nicht mehr abrufbar{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}.)
     }}{{#switch: 
         |no|0|=
         |#default={{#if:  ||  }}
    }}{{#invoke:TemplatePar|check
         |opt      = inline= url= text= datum= date= archivebot= bot= botlauf= fix-attempted= checked=
         |cat      = Wikipedia:Vorlagenfehler/Vorlage:Toter Link
         |errNS    = 0
         |template = Vorlage:Toter Link
         |format   = 
         |preview  = 1
    }}{{#if: http://www.tcs.uni-luebeck.de/downloads/mitarbeiter/tantau/2009-ws-ti.pdf
      | {{#if:{{#invoke:URLutil|isWebURL|http://www.tcs.uni-luebeck.de/downloads/mitarbeiter/tantau/2009-ws-ti.pdf}}
          || {{#if:  ||  }} 
        }}
      | {{#if: 
           | {{#if:  ||  }}
           | {{#if:  ||  }}
        }}
    }}{{#if: 
       | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}}
             || {{#if:  ||  }} 
         }}
    }}{{#switch: 
         |checked|deadurl|= 
         |#default=  {{#if:  ||  }}
    }}|#default= https://wiki-de.moshellshocker.dns64.de/index.php?title=Wikipedia:Defekte_Weblinks&dwl=http://www.tcs.uni-luebeck.de/downloads/mitarbeiter/tantau/2009-ws-ti.pdf Die nachstehende Seite ist {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar]{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. (Suche im Internet Archive. (T).)  {{#if: 
            | {{#if:  | | Vorlage:Toter Link/archivebot }}
         }}Vorlage:Toter Link/Core{{#switch: 
          |no|0|=
          |#default= {{#if:  ||  }}
        }}{{#invoke:TemplatePar|check
         |all      = inline= url=
         |opt      = datum= date= archivebot= bot= botlauf= fix-attempted= checked=
         |cat      = Wikipedia:Vorlagenfehler/Vorlage:Toter Link
         |errNS    = 0
         |template = Vorlage:Toter Link
         |format   = 
         |preview  = 1
       }}{{#if: http://www.tcs.uni-luebeck.de/downloads/mitarbeiter/tantau/2009-ws-ti.pdf
       | {{#if:{{#invoke:URLutil|isWebURL|http://www.tcs.uni-luebeck.de/downloads/mitarbeiter/tantau/2009-ws-ti.pdf}}
          || {{#if:  ||  }} 
        }}
    }}{{#if: 
         | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}}
             || {{#if:  ||  }} 
           }}
    }}{{#switch: 
         |checked|deadurl|= 
         |#default=  {{#if:  ||  }}
    }}[http://www.tcs.uni-luebeck.de/downloads/mitarbeiter/tantau/2009-ws-ti.pdf }} }}}}}}}}}}{{#if:|
        {{#invoke:Vorlage:Internetquelle|archivBot|stamp={{{archiv-bot}}}|text={{#if:|Vorlage:Webarchiv/archiv-bot}}

}}}}{{#invoke:TemplatePar|check |all= url= titel= |opt= autor= hrsg= format= sprache= titelerg= werk= seiten= datum= abruf= zugriff= abruf-verborgen= archiv-url= archiv-datum= archiv-bot= kommentar= zitat= AT= CH= offline= |cat= {{#ifeq: 0 | 0 | Wikipedia:Vorlagenfehler/Vorlage:Internetquelle}} |template= Vorlage:Internetquelle |format=0 |preview=1 }}</ref>, sondern diese Unterprogramme inlined und somit ein Teil des Hauptprogramms werden<ref>{{#invoke:Vorlage:Literatur|f}}</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

Einzelnachweise

<references />

Literatur

  • {{#invoke:Vorlage:Literatur|f}}
Abgerufen von „https://wiki-de.moshellshocker.dns64.de/index.php?title=LOOP-Programm&oldid=65031“