WHILE-Programm - LinkFang.de





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:

[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
[math]x_3:=x_4+10[/math]
  • oder vermindert um eine Konstante, etwa
[math]x_5:=x_6-300[/math]
  • 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
[math]x_9:=x_9+3; \quad x_{10}:=x_9-2[/math]

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 um, um ein äquivalentes GOTO-Programm [math]P'[/math] zu erhalten und dann wieder zurück in ein äquivalentes WHILE-Programm [math]P''[/math]. 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

[math]\mathrm{WHILE} \quad x2 \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


Kategorien: Berechenbarkeitstheorie

Quelle: Wikipedia - http://de.wikipedia.org/wiki/WHILE-Programm (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.