WHILE-Programm

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

Inhaltsverzeichnis
1 Syntax
2 Kleenesche Normalform für WHILE-Programme
3 Konsequenzen
4 Simulation durch GOTO-Programm

Syntax

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

P := x_i := x_j + c \, | \, x_i := x_j - c \, | \, P;P \, | \, \mathrm{WHILE} \, x_i \ne 0 \, \mathrm{DO} \, P \, \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' zu erhalten und dann wieder zurück in ein äquivalentes WHILE-Programm P''. 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 x1 = 0 THEN GOTO M2;
     P;
     GOTO M1;
 M2: ...

Eine weitere verwendete Schleifenstruktur ist ein LOOP-Programm.

See also: WHILE-Programm, BASIC, Backus-Naur-Form, Berechenbarkeit, GOTO-Programm, LOOP-Programm, Pascal (Programmiersprache), Spagetticode, Syntax, Theoretische Informatik