GOTO-Programm - LinkFang.de





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 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-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-, C-, C++- oder Java-Programm dargestellt werden kann, und umgekehrt.

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

Siehe auch


Kategorien: Berechenbarkeitstheorie

Quelle: Wikipedia - http://de.wikipedia.org/wiki/GOTO-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.