GOTO-Programm

GOTO-Programme s​ind spezielle Programme m​it einer s​ehr einfachen Syntax. Dennoch spielen s​ie in Zusammenhang m​it Berechenbarkeit e​ine große Rolle für d​ie theoretische Informatik, insbesondere w​eil sich zeigen lässt, d​ass jede Turing-berechenbare Funktion GOTO-berechenbar ist.

Syntax

GOTO-Programme h​aben folgende Syntax i​n modifizierter Backus-Naur-Form:

• ${\displaystyle P::=M_{1}:A;...;M_{k}:A}$
• ${\displaystyle 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} }$
• ${\displaystyle M_{1},...,M_{k}}$ sind Marken (k ∈ ℕ)

${\displaystyle GOTO}$ ist die Menge aller GOTO-Programme gemäß obiger Definition.

Jede GOTO-berechenbare Funktion i​st WHILE-berechenbar u​nd umgekehrt.

Jede Turing-berechenbare Funktion i​st GOTO-berechenbar u​nd umgekehrt.

Erklärung der Syntax

Jedes GOTO-Programm ${\displaystyle P}$ besteht aus einer Anzahl von Anweisungen ${\displaystyle A}$, getrennt mit jeweils einem Semikolon. Vor jeder Anweisung befindet sich eine (eindeutige) Marke ${\displaystyle M_{1},\ M_{2},\ \dots }$, gefolgt von einem Doppelpunkt.

GOTO-Programme haben eine endliche Anzahl von Variablen ${\displaystyle x_{1},\ x_{2},\ \dots }$ und Konstanten ${\displaystyle 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

${\displaystyle x_{1}:=x_{2}+3}$

• oder vermindert um eine Konstante, etwa

${\displaystyle x_{3}:=x_{3}-1}$.

• eine Sprunganweisung

${\displaystyle \mathrm {GOTO} \quad M_{4}}$

• eine bedingte Sprunganweisung, wobei eine Variable auf Gleichheit mit einer Konstanten abgefragt wird, etwa

${\displaystyle {\rm {IF}}\quad x_{4}=45\quad {\rm {THEN}}\quad {\rm {GOTO}}\quad M_{5}}$

• und die STOP-Anweisung

${\displaystyle {\rm {STOP}}}$.

Konsequenz

Man k​ann formal beweisen, d​ass jedes GOTO-Programm a​uch durch e​in äquivalentes Pascal-, C-, C++- o​der Java-Programm dargestellt werden kann, u​nd umgekehrt.

Beispiele

Addition zweier Variablen

Das folgende GOTO-Programm berechnet die Summe ${\displaystyle x_{1}+x_{2}}$ von zwei nicht-negativen Zahlen ${\displaystyle x_{1},x_{2}}$ und speichert diese in die Variable ${\displaystyle x_{3}}$.

 ${\displaystyle M_{1}:}$ ${\displaystyle x_{3}:=x_{1}}$;
 ${\displaystyle M_{2}:}$ ${\displaystyle x_{4}:=x_{2}}$;
 ${\displaystyle M_{3}:}$ ${\displaystyle {\rm {IF}}\ x_{4}=0\ {\rm {THEN}}\ {\rm {GOTO}}\ M_{7}}$;
 ${\displaystyle M_{4}:}$ ${\displaystyle x_{3}:=x_{3}+1}$;
 ${\displaystyle M_{5}:}$ ${\displaystyle x_{4}:=x_{4}-1}$;
 ${\displaystyle M_{6}:}$ ${\displaystyle \mathrm {GOTO} \quad M_{3}}$;
 ${\displaystyle M_{7}:}$ ${\displaystyle STOP}$

Multiplikation zweier Variablen

Das folgende Programm berechnet das Produkt ${\displaystyle x_{1}\cdot x_{2}}$ von zwei nicht-negativen Zahlen ${\displaystyle x_{1},x_{2}}$ und speichert dieses in die Variable ${\displaystyle x_{3}}$. Da wir schon ein Programm zur Implementierung der Addition zweier Variablen haben verwenden wir diese um eine Implementierung der Multiplikation zu entwickeln.

 ${\displaystyle M_{1}:}$ ${\displaystyle x_{3}:=0}$;
 ${\displaystyle M_{2}:}$ ${\displaystyle x_{4}:=x_{2}}$;
 ${\displaystyle M_{3}:}$ ${\displaystyle {\rm {IF}}\quad x_{4}=0\quad {\rm {THEN}}\quad {\rm {GOTO}}\quad M_{7}}$;
 ${\displaystyle M_{4}:}$ ${\displaystyle x_{4}:=x_{4}-1}$;
 ${\displaystyle M_{5}:}$ ${\displaystyle x_{3}:=x_{3}+x_{1}}$;
 ${\displaystyle M_{6}:}$ ${\displaystyle \mathrm {GOTO} \quad M_{3}}$;
 ${\displaystyle M_{7}:}$ ${\displaystyle STOP}$;

Hier ist zu beachten, dass ${\displaystyle M_{5}:}$ ${\displaystyle x_{3}:=x_{3}+x_{1}}$ 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 ${\displaystyle x_{1},x_{2}}$.

 ${\displaystyle M_{1}:}$ ${\displaystyle x_{3}:=0}$;
 ${\displaystyle M_{2}:}$ ${\displaystyle x_{4}:=x_{2}}$;
 ${\displaystyle M_{3}:}$ ${\displaystyle {\rm {IF}}\quad x_{4}=0\quad {\rm {THEN}}\quad {\rm {GOTO}}\quad M_{10}}$;
 ${\displaystyle M_{4}:}$ ${\displaystyle x_{4}:=x_{4}-1}$;
 ${\displaystyle M_{5}:}$ ${\displaystyle x_{5}:=x_{1}}$;
 ${\displaystyle M_{6}:}$ ${\displaystyle {\rm {IF}}\quad x_{5}=0\quad {\rm {THEN}}\quad {\rm {GOTO}}\quad M_{3}}$;
 ${\displaystyle M_{7}:}$ ${\displaystyle x_{3}:=x_{3}+1}$;
 ${\displaystyle M_{8}:}$ ${\displaystyle x_{5}:=x_{5}-1}$;
 ${\displaystyle M_{9}:}$ ${\displaystyle \mathrm {GOTO} \quad M_{6}}$;
 ${\displaystyle M_{10}:}$ ${\displaystyle STOP}$;

Simulation durch WHILE-Programm

Ein GOTO-Programm

M1: A1; M2: A2; ... Mk: Ak

kann d​urch ein WHILE-Programm d​er 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 oder WHILE Schleifen implementiert werden. Das folgende Programm simuliert eine IF x₁ = 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

• Uwe Schöning: Theoretische Informatik – kurz gefasst. 5. Auflage. Spektrum Akademischer Verlag, Heidelberg, ISBN 978-3-8274-1824-1, 2.3 LOOP-, WHILE und GOTO-Berechenbarkeit.