WHILE-Programm

aus Wikipedia, der freien Enzyklopädie

Du hast neue Nachrichten auf deiner Diskussionsseite.

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

Inhaltsverzeichnis

1 Eigenschaften
2 Syntax
- 2.1 Erklärung der Syntax
3 Kleenesche Normalform für WHILE-Programme
4 Konsequenzen
5 Simulation durch GOTO-Programm

[Bearbeiten] Eigenschaften

RAM-berechenbar, Turing-berechenbar und WHILE-berechenbar sind äquivalent
LOOP-berechenbar $\subset$ WHILE-berechenbar
Kleenesche Normalform (Jedes WHILE-Programm kommt auch nur mit einer WHILE-Schleife aus)

[Bearbeiten] Syntax

WHILE-Programme haben folgende Syntax in modifizierter 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}$

$W H I L E$ ist die Menge aller WHILE-Programme gemäß obiger Definition.

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

[Bearbeiten] Erklärung der Syntax

Ein WHILE-Programm P besteht aus den Symbolen WHILE, DO, END, :=, +, -, ;, $\ne$ , einer Anzahl Variablen $x 1, x 2,...$ sowie beliebigen Konstanten c.

Es sind nur drei verschiedene Anweisungen erlaubt, nämlich

die Zuweisung einer Variablen durch eine weitere Variable, vermehrt um eine Konstante, etwa

x 3 : = x 4 + 10

oder vermindert um eine Konstante, etwa

x 5 : = x 6 - 300

eine WHILE-Anweisung, die eine Variable auf ungleich Null abfragt und ein WHILE-Programm zwischen DO und END enthält, etwa

$\mathrm{WHILE} \quad x_7 \ne 0 \quad \mathrm{DO} \quad x_7:=x_7+1 \quad\mathrm{END}$

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

wieder ein WHILE-Programm.

[Bearbeiten] 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.

[Bearbeiten] 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.

[Bearbeiten] Simulation durch GOTO-Programm

Ein jedes WHILE-Programm

$\mathrm{WHILE} \quad x2 \ne 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: ...

Eine weitere verwendete Schleifenstruktur ist ein LOOP-Programm.

Von „http://de.wikipedia.org../../../w/h/i/WHILE-Programm_86a6.html“

Kategorien: Theoretische Informatik | Berechenbarkeitstheorie

WHILE-Programm

aus Wikipedia, der freien Enzyklopädie

Inhaltsverzeichnis

[Bearbeiten] Eigenschaften

[Bearbeiten] Syntax

[Bearbeiten] Erklärung der Syntax

[Bearbeiten] Kleenesche Normalform für WHILE-Programme

[Bearbeiten] Konsequenzen

[Bearbeiten] Simulation durch GOTO-Programm

Views

Navigation

Mitmachen

Suche