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

Eigenschaften

Bearbeiten

WHILE-Programme haben folgende Syntax in modifizierter Backus-Naur-Form:

 

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

Bearbeiten

Ein WHILE-Programm P besteht aus den Symbolen WHILE, LOOP, DO, END, :=, +, -, ;,  , einer Anzahl Variablen   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
 

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
 

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

Bearbeiten

Jede WHILE-berechenbare Funktion ist GOTO-berechenbar und umgekehrt sowie turingberechenbar.

Mit   wird ferner die Menge aller WHILE-Programme gemäß obiger Definition bezeichnet.

Kleenesche Normalform für WHILE-Programme

Bearbeiten

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

Beweis: Sei   ein beliebiges WHILE-Programm. Wir formen   zunächst, wie im Abschnitt „Simulation durch GOTO-Programme“ dieses Artikels beschrieben, um, um ein äquivalentes GOTO-Programm   zu erhalten. Anschließend formen wir   den Anweisungen im Abschnitt „Simulation durch WHILE-Programm“ im Artikel GOTO-Programm folgend in ein äquivalentes WHILE-Programm   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   nur eine WHILE-Schleife.

Konsequenzen

Bearbeiten

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

Bearbeiten

Ein jedes WHILE-Programm

 

kann durch das folgende GOTO-Programm simuliert werden:

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

Siehe auch

Bearbeiten

Literatur

Bearbeiten
  • Uwe Schöning: Theoretische Informatik – kurz gefasst. 5. Auflage. Spektrum Akademischer Verlag, Heidelberg, ISBN 978-3-8274-1824-1, 2.3 LOOP-, WHILE und GOTO-Berechenbarkeit.