WHILE-Programm

2023-07-23T09:38:30Z

217.61.192.163: ,

'''WHILE-Programme''' spielen in der [[Theoretische Informatik|Theoretischen Informatik]] eine Rolle, insbesondere in Zusammenhang mit [[Berechenbarkeit]].

== Eigenschaften ==
* [[Random Access Machine|RAM-berechenbar]], [[Turing-Berechenbarkeit|Turing-berechenbar]], [[GOTO-Programm|GOTO-berechenbar]] und WHILE-berechenbar sind äquivalent
* [[LOOP-Programm|LOOP-berechenbar]] <math> \varsubsetneq </math> 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]]:

<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-Programm|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, wie im Abschnitt „Simulation durch GOTO-Programme“ dieses Artikels beschrieben, um, um ein äquivalentes GOTO-Programm <math>P'</math> zu erhalten. Anschließend formen wir <math>P'</math> den Anweisungen im Abschnitt „Simulation durch WHILE-Programm“ im Artikel [[GOTO-Programm]] folgend in ein äquivalentes WHILE-Programm <math>P''</math> um. Hierbei ist zu beachten, dass die für diese Konstruktion notwendigen IF THEN END Anweisungen durch LOOPs simuliert werden können. Per Konstruktion hat <math>P''</math> 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 (Programmiersprache)|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 x_2 \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 ==
* [[LOOP-Programm]]
* [[GOTO-Programm]]

== Literatur ==
* {{Literatur| Autor=[[Uwe Schöning]]| Titel=Theoretische Informatik – kurz gefasst| Auflage=5| Verlag=Spektrum Akademischer Verlag| Ort=Heidelberg| Kapitel=2.3 LOOP-, WHILE und GOTO-Berechenbarkeit| ISBN=978-3-8274-1824-1}}

[[Kategorie:Berechenbarkeitstheorie]]

GOTO-Programm

2023-07-23T09:34:42Z

217.61.192.163: ,

'''GOTO-Programme''' sind spezielle [[Computerprogramm|Programme]] mit einer sehr einfachen [[Syntax]]. Dennoch spielen sie in Zusammenhang mit [[Berechenbarkeit]] eine große Rolle für die [[theoretische Informatik]], insbesondere weil sich zeigen lässt, dass jede [[Turing-Berechenbarkeit|Turing-berechenbare]] Funktion GOTO-berechenbar ist.

== Syntax ==
GOTO-Programme haben folgende [[Syntax]] in modifizierter [[Backus-Naur-Form]]:

* <math>P ::= M_1 : A; ... ; M_k : A</math>
* <math>A ::= x_i := x_j + c \, | x_i := x_j - c \, | \, \mathrm{GOTO} \, M_i \, | \, \mathrm{IF} \, x_i = c \, \mathrm{THEN} \, \mathrm{GOTO} \, M_j \, | \, \mathrm{STOP}</math>
* <math>M_1, ..., M_k</math> sind Marken (k ∈ ℕ)

<math>GOTO</math> ist die Menge aller GOTO-Programme gemäß obiger Definition.

Jede GOTO-berechenbare Funktion ist [[WHILE-Programm|WHILE-berechenbar]] und umgekehrt.

Jede Turing-berechenbare Funktion ist GOTO-berechenbar und umgekehrt.

=== Erklärung der Syntax ===
Jedes GOTO-Programm <math>P</math> besteht aus einer Anzahl von Anweisungen <math>A</math>, getrennt mit jeweils einem Semikolon. Vor jeder Anweisung befindet sich eine (eindeutige) Marke <math>M_1,\ M_2,\ \dots</math>, gefolgt von einem Doppelpunkt.

GOTO-Programme haben eine endliche Anzahl von Variablen <math>x_1,\ x_2,\ \dots</math> und Konstanten <math>c</math>. Es sind nur fünf verschiedene Anweisungen erlaubt:
* Zuweisung einer Variablen durch eine weitere (dieselbe oder eine andere) Variable, vermehrt um eine Konstante, etwa
::<math>x_1 := x_2+3</math>
* oder vermindert um eine Konstante, etwa
::<math>x_3 := x_3-1</math>.
* eine Sprunganweisung
::<math>\mathrm{GOTO} \quad M_4</math>
* eine bedingte Sprunganweisung, wobei eine Variable auf Gleichheit mit einer Konstanten abgefragt wird, etwa
::<math>{\rm IF} \quad x_4 = 45 \quad {\rm THEN} \quad {\rm GOTO} \quad M_5</math>
* und die STOP-Anweisung
::<math>{\rm STOP}</math>.

== Konsequenz ==
Man kann formal beweisen, dass jedes [[GOTO]]-Programm auch durch ein äquivalentes [[Pascal (Programmiersprache)|Pascal]]-, [[C (Programmiersprache)|C]]-, [[C++]]- oder [[Java (Programmiersprache)|Java]]-Programm dargestellt werden kann, und umgekehrt.

== Beispiele ==

=== Addition zweier Variablen ===
Das folgende GOTO-Programm berechnet die Summe <math>x_1 + x_2</math> von zwei nicht-negativen Zahlen <math>x_1, x_2</math> und speichert diese in die Variable <math>x_3</math>.

<math>M_1:</math> <math>x_3:=x_1</math>;
<math>M_2:</math> <math>x_4:=x_2</math>;
<math>M_3:</math> <math>{\rm IF} \ x_4 = 0 \ {\rm THEN} \ {\rm GOTO} \ M_{7}</math>;
<math>M_4:</math> <math>x_3:=x_3+1</math>;
<math>M_5:</math> <math>x_4:=x_4-1</math>;
<math>M_6:</math> <math>\mathrm{GOTO} \quad M_3</math>;
<math>M_7:</math> <math>STOP</math>

=== Multiplikation zweier Variablen ===

Das folgende Programm berechnet das Produkt <math>x_1 \cdot x_2</math> von zwei nicht-negativen Zahlen <math>x_1, x_2</math> und speichert dieses in die Variable <math>x_3</math>.
Da wir schon ein Programm zur Implementierung der Addition zweier Variablen haben, verwenden wir diese, um eine Implementierung der Multiplikation zu entwickeln.

<math>M_1:</math> <math>x_3:=0</math>;
<math>M_2:</math> <math>x_4:=x_2</math>;
<math>M_3:</math> <math>{\rm IF} \quad x_4 = 0 \quad {\rm THEN} \quad {\rm GOTO} \quad M_{7}</math>;
<math>M_4:</math> <math>x_4 := x_4 - 1</math>;
<math>M_5:</math> <math>x_3 := x_3+x_1</math>;
<math>M_6:</math> <math>\mathrm{GOTO} \quad M_3</math>;
<math>M_7:</math> <math>STOP</math>;

Hier ist zu beachten, dass <math>M_5:</math> <math>x_3 := x_3+x_1</math> formal kein gültiges GOTO-Programm ist, sondern durch ein entsprechendes GOTO-Programm für die Addition ersetzt werden muss.
Führt man diese Ersetzung durch, erhält man folgendes GOTO-Programm für die Multiplikation von zwei nicht-negativen Zahlen <math>x_1, x_2</math>.

<math>M_1:</math> <math>x_3:=0</math>;
<math>M_2:</math> <math>x_4:=x_2</math>;
<math>M_3:</math> <math>{\rm IF} \quad x_4 = 0 \quad {\rm THEN} \quad {\rm GOTO} \quad M_{10}</math>;
<math>M_4:</math> <math>x_4 := x_4 - 1</math>;
<math>M_5:</math> <math>x_5:=x_1</math>;
<math>M_6:</math> <math>{\rm IF} \quad x_5 = 0 \quad {\rm THEN} \quad {\rm GOTO} \quad M_{3}</math>;
<math>M_7:</math> <math>x_3:=x_3+1</math>;
<math>M_8:</math> <math>x_5:=x_5-1</math>;
<math>M_9:</math> <math>\mathrm{GOTO} \quad M_6</math>;
<math>M_{10}:</math> <math>STOP</math>;

== Simulation durch WHILE-Programm ==
Ein GOTO-Programm
M1: A1; M2: A2; ... Mk: Ak
kann durch ein [[WHILE-Programm]] der folgenden Form simuliert werden
counter := 1;
WHILE counter != 0 DO
IF counter = 1 THEN B1 END;
IF counter = 2 THEN B2 END;
...
IF counter = k THEN Bk END;
IF counter = k+1 THEN counter := 0 END
END
wobei
Bi = xj := xn + c; counter := counter + 1 falls Ai = xj := xn + c
Bi = xj := xn - c; counter := counter + 1 falls Ai = xj := xn - c
Bi = counter := n falls Ai = GOTO Mn
Bi = IF xj = c THEN counter := n
ELSE counter := counter + 1 falls Ai = IF xj = c THEN GOTO Mn
END
Bi = counter := 0 falls Ai = STOP

In WHILE-Programmen gibt es keine IF THEN END Anweisungen, diese können aber mit [[LOOP-Programm#IF THEN ELSE|LOOP]] oder WHILE Schleifen implementiert werden.
Das folgende Programm simuliert eine ''IF x1 = c THEN P1 END'' Anweisung, dabei werden drei neue Variablen xn1, xn2, xn3 verwendet.

xn1:=x1-(c-1); xn2:=x1-c; xn3:=1;
LOOP xn1 DO
LOOP xn2 DO
xn3:=0
END;
LOOP xn3 DO
P1
END
END
#

== Siehe auch ==
* [[Sprunganweisung]] (GOTO)
* [[LOOP-Programm]]
* [[WHILE-Programm]]
* [[µ-Rekursion]]

== Literatur ==
* {{Literatur| Autor=[[Uwe Schöning]]| Titel=Theoretische Informatik – kurz gefasst| Auflage=5| Verlag=Spektrum Akademischer Verlag| Ort=Heidelberg| Kapitel=2.3 LOOP-, WHILE und GOTO-Berechenbarkeit| ISBN=978-3-8274-1824-1}}

[[Kategorie:Berechenbarkeitstheorie|Gotoprogramm]]

Wikipedia (Deutsch) – Lokale Kopie - Benutzerbeiträge [de]

WHILE-Programm

GOTO-Programm