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

Syntax

---

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

$P\; :=\; x\_i\; :=\; x\_j\; +\; c\; \backslash ,\; |\; \backslash ,\; x\_i\; :=\; x\_j\; -\; c\; \backslash ,\; |\; \backslash ,\; P;P\; \backslash ,\; |\; \backslash ,\; \backslash mathrm\{WHILE\}\; \backslash ,\; x\_i\; \backslash ne\; 0\; \backslash ,\; \backslash mathrm\{DO\}\; \backslash ,\; P\; \backslash ,\; \backslash mathrm\{END\}$

$WHILE$ ist die Menge aller WHILE-Programme gemäß obiger Definition.

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

Kleenesche Normalform für WHILE-Programme

---

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

Beweis: Sei $P$ ein beliebiges WHILE-Programm. Wir formen $P$ zunächst um, um ein äquivalentes GOTO-Programm $P\text{'}$ zu erhalten und dann wieder zurück in ein äquivalentes WHILE-Programm $P\text{'}\text{'}$. Per Konstruktion hat dieses 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 Spagetticode zu erzeugen.

Simulation durch GOTO-Programm

---

Ein jedes WHILE-Programm WHILE xi != 0 DO P END kann durch das folgende GOTO-Programm simuliert werden M1: IF xi = 0 THEN GOTO M2; P; GOTO M1; M2: ...

Eine weitere verwendete Schleifenstruktur ist ein LOOP-Programm.

Theoretische Informatik