Website durchsuchen

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:

{\displaystyle 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 und umgekehrt.

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 {\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 c. Es sind nur fünf verschiedene Anweisungen erlaubt:

{\displaystyle x_{1}:=x_{2}+3}
{\displaystyle x_{3}:=x_{3}-1}.
{\displaystyle \mathrm {GOTO} \quad M_{4}}
{\displaystyle {\rm {IF}}\quad x_{4}=45\quad {\rm {THEN}}\quad {\rm {GOTO}}\quad M_{5}}
{\displaystyle {\rm {STOP}}}.

Konsequenz

Man kann formal beweisen, dass jedes GOTO-Programm auch durch ein äquivalentes Pascal-, C-, C++- oder Java-Programm dargestellt werden kann, und umgekehrt.

Beispiele

Addition zweier Variablen

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

 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 x_1 \cdot x_2 von zwei nicht-negativen Zahlen x_{1},x_{2} und speichert dieses in die Variable x_{3}. Da wir schon ein Programm zur Implementierung der Addition zweier Variablen haben verwenden wir diese um eine Implementierung der Multiplikation zu entwickeln. 

 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 x_{1},x_{2}. 

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

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 x1 = 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

Trenner
Basierend auf einem Artikel in: Wikipedia.de
Seitenende
Seite zurück
©  biancahoegel.de
Datum der letzten Änderung: Jena, den: 21.09. 2022