WHILE-Programm
WHILE-Programme spielen in der Theoretischen Informatik eine Rolle, insbesondere in Zusammenhang mit Berechenbarkeit.
Eigenschaften
- RAM-berechenbar, Turing-berechenbar, GOTO-berechenbar und WHILE-berechenbar sind äquivalent
- LOOP-berechenbar WHILE-berechenbar
- Kleenesche Normalform (Jedes WHILE-Programm kommt auch nur mit einer While-Schleife aus)
Syntax
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
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
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
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 um, um ein äquivalentes GOTO-Programm zu erhalten, und dann wieder zurück in ein äquivalentes WHILE-Programm . 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
kann durch das folgende GOTO-Programm simuliert werden:
M1: IF x2 = 0 THEN GOTO M2; P; GOTO M1; M2: ...
Siehe auch
© biancahoegel.de
Datum der letzten Änderung: Jena, den: 20.08. 2022