WHILE-Programm

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

Eigenschaften

Syntax

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

{\displaystyle {\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}\neq 0\,\mathrm {DO} \,P\,\mathrm {END} \end{array}}}

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, :=, +, -, ;, \ne, einer Anzahl Variablen x_{1},x_{2},... sowie beliebigen Konstanten c.

Es sind nur vier verschiedene Anweisungen erlaubt, nämlich

x_{3}:=x_{4}+10
x_{5}:=x_{6}-300
{\displaystyle \mathrm {LOOP} \quad x_{7}\quad \mathrm {DO} \quad x_{7}:=x_{7}+1\quad \mathrm {END} }

Zu beachten ist, dass bei LOOP eine Änderung des Variablenwertes im zu wiederholenden Teilprogramm keine Auswirkung auf die Anzahl der Wiederholungen dieses Teilprogramms hat.

{\displaystyle \mathrm {WHILE} \quad x_{8}\neq 0\quad \mathrm {DO} \quad x_{8}:=x_{8}+1\quad \mathrm {END} }

Die Anweisungen sind für sich genommen bereits vollständige WHILE-Programme. Des Weiteren ist die

{\displaystyle x_{9}:=x_{9}+3;\quad x_{10}:=x_{9}-2}

wieder ein WHILE-Programm.

Allgemein

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

Mit {\mathrm  {WHILE}} 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 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 „Spaghetticode“ zu erzeugen.

Simulation durch GOTO-Programm

Ein jedes WHILE-Programm

{\mathrm  {WHILE}}\quad x2\neq 0\quad {\mathrm  {DO}}\quad P\quad {\mathrm  {END}}

kann durch das folgende GOTO-Programm simuliert werden:

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

Siehe auch

Trenner
Basierend auf einem Artikel in: Extern Wikipedia.de
Seitenende
Seite zurück
©  biancahoegel.de
Datum der letzten Änderung: Jena, den: 20.08. 2022