WHILE-Programm

WHILE-Programme spielen in der Theoretischen Informatik eine Rolle, insbesondere in Zusammenhang mit Berechenbarkeit.

Eigenschaften

RAM-berechenbar, Turing-berechenbar, GOTO-berechenbar und WHILE-berechenbar sind äquivalent
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

oder vermindert um eine Konstante, etwa

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

wieder ein WHILE-Programm.

Allgemein

Jede WHILE-berechenbare Funktion ist 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-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

Literatur

{{#invoke:Vorlage:Literatur|f}}