WHILE-Programm

WHILE-Programm

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

Inhaltsverzeichnis

Eigenschaften

Syntax

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

\begin{array}{lrl}
P & ::= & x_i := x_j + c \\
  &   | & x_i := x_j - c \\
  &   | & P;P \\
  &   | & \mathrm{WHILE} \, x_i \ne 0 \, \mathrm{DO} \, P \, \mathrm{END}
\end{array}

WHILE ist die Menge aller WHILE-Programme gemäß obiger Definition.

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

Erklärung der Syntax

Ein WHILE-Programm P besteht aus den Symbolen WHILE, DO, END, :=, +, -, ;, \ne, einer Anzahl Variablen x1,x2,... 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
x3: = x4 + 10
  • oder vermindert um eine Konstante, etwa
x5: = x6 − 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.

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 \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: ...

Siehe auch


Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • While-Programm — 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 …   Deutsch Wikipedia

  • While-Berechenbarkeit — 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 …   Deutsch Wikipedia

  • While-Schleife — In den meisten Programmiersprachen gibt es die While Schleife als Kontrollstruktur. Sie dient dazu, eine Abfolge von Anweisungen mehrfach auszuführen, solange eine Bedingung erfüllt ist. Diese Bedingung wird geprüft, bevor die Anweisungsfolge… …   Deutsch Wikipedia

  • Programm (Computer) — Das Computerprogramm oder kurz Programm ist eine Folge von Anweisungen, die auf einem Computer ausgeführt werden können, um damit eine bestimmte Funktionalität (z. B. Textverarbeitung) zur Verfügung zu stellen. Inhaltsverzeichnis 1 Details 2… …   Deutsch Wikipedia

  • GoTo-Programm — GOTO Programme sind spezielle 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 berechenbare… …   Deutsch Wikipedia

  • Goto-Programm — GOTO Programme sind spezielle 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 berechenbare… …   Deutsch Wikipedia

  • LOOP-Programm — Dieser Artikel wurde auf den Seiten der Qualitätssicherung eingetragen. Bitte hilf mit, ihn zu verbessern, und beteilige dich bitte an der Diskussion! Folgendes muss noch verbessert werden: Lemma entspricht nicht Konvention 84.150.18.114… …   Deutsch Wikipedia

  • Loop-Programm — LOOP Programme sind Programme in der Programmiersprache LOOP, einer stark eingeschränkten, modellhaften Sprache, die nur die Formulierung von Additionen, Wertzuweisungen und endlich oft durchlaufenen Schleifen erlaubt. LOOP Programme spielen in… …   Deutsch Wikipedia

  • GOTO-Programm — GOTO Programme sind spezielle 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 berechenbare… …   Deutsch Wikipedia

  • Computer-Programm — Das Computerprogramm oder kurz Programm ist eine Folge von Anweisungen, die auf einem Computer ausgeführt werden können, um damit eine bestimmte Funktionalität (z. B. Textverarbeitung) zur Verfügung zu stellen. Inhaltsverzeichnis 1 Details 2… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”