Goto-Berechenbarkeit

Goto-Berechenbarkeit

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.

Inhaltsverzeichnis

Syntax

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

  • P:: = M1:A;...;Mk:A
  • 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}
  • M1,...,Mk sind Marken (k ∈ ℕ)

GOTO 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.

Erklärung der Syntax

Jedes GOTO-Programm P besteht aus einer Anzahl von Anweisungen A, getrennt mit jeweils einem Semikolon. Vor jeder Anweisung befindet sich eine (eindeutige) Marke M_1,\ M_2,\ \dots, gefolgt von einem Doppelpunkt.

GOTO-Programme haben eine endliche Anzahl von Variablen x_1,\ x_2,\ \dots und Konstanten c. Es sind nur fünf verschiedene Anweisungen erlaubt:

  • Zuweisung einer Variablen durch eine weitere (dieselbe oder eine andere) Variable, vermehrt um eine Konstante, etwa
x1: = x2 + 3
  • oder vermindert um eine Konstante, etwa
x3: = x3 − 1.
  • eine Sprunganweisung
\mathrm{GOTO} \quad M_4
  • eine bedingte Sprunganweisung, wobei eine Variable auf Gleichheit mit einer Konstanten abgefragt wird, etwa
{\rm IF} \quad x_4 = 45 \quad {\rm THEN} \quad {\rm GOTO} \quad M_5
  • und die STOP-Anweisung
STOP.

Konsequenz

Damit kann man formal zeigen, dass jedes BASIC-Programm auch durch ein äquivalentes Pascal-, C-, C++- oder Java-Programm dargestellt werden kann.

Simulation durch WHILE-Programm

Ein jedes 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;
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


Wikimedia Foundation.

Игры ⚽ Поможем написать реферат

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

  • 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

  • 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

  • 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

  • Loop-Berechenbarkeit — 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

  • Entscheidbare Sprache — Eine Formale Sprache heißt rekursiv (entscheidbar), wenn eine Turingmaschine M existiert, die auf alle Eingaben hält, d.h HM = L Die Nicht Rekursivität einer Sprache kann man mittels Satz von Rice nachweisen. Wenn es keine Turingmaschine gibt,… …   Deutsch Wikipedia

  • Rekursive Sprache — Eine Formale Sprache heißt rekursiv (entscheidbar), wenn eine Turingmaschine M existiert, die auf allen Eingaben hält, d. h. HM = Σ * , und jede Eingabe genau dann akzeptiert, wenn ist. Die Nicht Rekursivität einer Sprache kann man mittels Satz… …   Deutsch Wikipedia

  • 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

  • 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 der… …   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

Share the article and excerpts

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