217.61.192.163: ,

2023-07-23T09:38:30Z

Neue Seite

'''WHILE-Programme''' spielen in der [[Theoretische Informatik|Theoretischen Informatik]] eine Rolle, insbesondere in Zusammenhang mit [[Berechenbarkeit]].

== Eigenschaften ==
* [[Random Access Machine|RAM-berechenbar]], [[Turing-Berechenbarkeit|Turing-berechenbar]], [[GOTO-Programm|GOTO-berechenbar]] und WHILE-berechenbar sind äquivalent
* [[LOOP-Programm|LOOP-berechenbar]] <math> \varsubsetneq </math> WHILE-berechenbar
* [[Kleenesche Normalform]] (Jedes WHILE-Programm kommt auch nur mit einer [[While-Schleife]] aus)

== Syntax ==
WHILE-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} \\
& | & \mathrm{WHILE} \, x_i \ne 0 \, \mathrm{DO} \, P \, \mathrm{END}
\end{array}
</math>

Auf das LOOP-Konstrukt in dieser Definition kann auch verzichtet werden, ohne dass die Menge der WHILE-berechenbaren Funktionen kleiner wird.
Schließlich kann jeder LOOP-Ausdruck durch ein WHILE emuliert werden. Allerdings hat ein Verzicht auf das LOOP zur Folge, dass nicht mehr alle WHILE-Programme in
[[Kleenesche Normalform]] gebracht werden können.

=== Erklärung der Syntax ===

Ein WHILE-Programm ''P'' besteht aus den Symbolen ''WHILE'', ''LOOP'', ''DO'', ''END'', :=, +, -, ;, <math>\ne</math>, einer Anzahl Variablen <math>x_1, x_2, ...</math> sowie beliebigen Konstanten ''c''.

Es sind nur vier verschiedene Anweisungen erlaubt, nämlich

* die Zuweisung einer Variablen durch eine weitere Variable, vermehrt um eine Konstante, etwa
::<math>x_3:=x_4+10</math>
* oder vermindert um eine Konstante, etwa
::<math>x_5:=x_6-300</math>
* eine LOOP-Anweisung, die zu Beginn den Wert einer Variablen überprüft und ein WHILE-Programm entsprechend oft wiederholt, etwa
::<math>\mathrm{LOOP} \quad x_7 \quad \mathrm{DO} \quad x_7:=x_7+1 \quad\mathrm{END}</math>
Zu beachten ist, dass bei LOOP eine Änderung des Variablenwertes im zu wiederholenden Teilprogramm keine Auswirkung auf die Anzahl der Wiederholungen dieses Teilprogramms hat.
* eine WHILE-Anweisung, die eine Variable auf ungleich Null abfragt und ein WHILE-Programm zwischen DO und END enthält, etwa
::<math>\mathrm{WHILE} \quad x_8 \ne 0 \quad \mathrm{DO} \quad x_8:=x_8+1 \quad\mathrm{END}</math>

Die Anweisungen sind für sich genommen bereits vollständige WHILE-Programme. Des Weiteren ist die
* Aneinanderreihung von WHILE-Programmen, jeweils getrennt durch ein Semikolon, etwa
::<math>x_9:=x_9+3; \quad x_{10}:=x_9-2</math>
wieder ein WHILE-Programm.

=== Allgemein ===
Jede WHILE-berechenbare Funktion ist [[GOTO-Programm|GOTO-berechenbar]] und umgekehrt sowie turingberechenbar.

Mit <math>\mathrm{WHILE}</math> wird ferner die Menge aller WHILE-Programme gemäß obiger Definition bezeichnet.

== Kleenesche Normalform für WHILE-Programme ==

Jede WHILE-berechenbare Funktion kann durch ein WHILE-Programm mit nur einer WHILE-Schleife berechnet werden.

'''Beweis:''' Sei <math>P</math> ein beliebiges WHILE-Programm. Wir formen <math>P</math> zunächst, wie im Abschnitt „Simulation durch GOTO-Programme“ dieses Artikels beschrieben, um, um ein äquivalentes GOTO-Programm <math>P'</math> zu erhalten. Anschließend formen wir <math>P'</math> den Anweisungen im Abschnitt „Simulation durch WHILE-Programm“ im Artikel [[GOTO-Programm]] folgend in ein äquivalentes WHILE-Programm <math>P''</math> um. Hierbei ist zu beachten, dass die für diese Konstruktion notwendigen IF THEN END Anweisungen durch LOOPs simuliert werden können. Per Konstruktion hat <math>P''</math> nur eine WHILE-Schleife.

== Konsequenzen ==

Die einfach beweisbare Tatsache, dass jedes [[GOTO-Programm]] in ein WHILE-Programm überführt werden kann und umgekehrt, hat zur Konsequenz, dass man beweisen kann, dass ein beliebiges [[Pascal (Programmiersprache)|Pascal]]-Programm die gleichen Leistungen erbringen kann wie ein beliebiges [[BASIC]]-Programm. Außerdem zeigt sie, dass man jedes Programm auch strukturiert programmieren kann, ohne „[[Spaghetticode]]“ zu erzeugen.

== Simulation durch GOTO-Programm ==

Ein jedes WHILE-Programm
:<math>\mathrm{WHILE} \quad x_2 \ne 0 \quad\mathrm{DO} \quad P \quad\mathrm{END}</math>

kann durch das folgende GOTO-Programm simuliert werden:

M1: IF x2 = 0 THEN GOTO M2;
P;
GOTO M1;
M2: ...

== Siehe auch ==
* [[LOOP-Programm]]
* [[GOTO-Programm]]

== Literatur ==
* {{Literatur| Autor=[[Uwe Schöning]]| Titel=Theoretische Informatik – kurz gefasst| Auflage=5| Verlag=Spektrum Akademischer Verlag| Ort=Heidelberg| Kapitel=2.3 LOOP-, WHILE und GOTO-Berechenbarkeit| ISBN=978-3-8274-1824-1}}

[[Kategorie:Berechenbarkeitstheorie]]

WHILE-Programm - Versionsgeschichte

217.61.192.163: ,