217.61.192.163: ,

2023-07-23T09:34:42Z

Neue Seite

'''GOTO-Programme''' sind spezielle [[Computerprogramm|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-Berechenbarkeit|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-Programm|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 (Programmiersprache)|Pascal]]-, [[C (Programmiersprache)|C]]-, [[C++]]- oder [[Java (Programmiersprache)|Java]]-Programm dargestellt werden kann, und umgekehrt.

== Beispiele ==

=== Addition zweier Variablen ===
Das folgende GOTO-Programm berechnet die Summe <math>x_1 + x_2</math> von zwei nicht-negativen Zahlen <math>x_1, x_2</math> und speichert diese in die Variable <math>x_3</math>.

<math>M_1:</math> <math>x_3:=x_1</math>;
<math>M_2:</math> <math>x_4:=x_2</math>;
<math>M_3:</math> <math>{\rm IF} \ x_4 = 0 \ {\rm THEN} \ {\rm GOTO} \ M_{7}</math>;
<math>M_4:</math> <math>x_3:=x_3+1</math>;
<math>M_5:</math> <math>x_4:=x_4-1</math>;
<math>M_6:</math> <math>\mathrm{GOTO} \quad M_3</math>;
<math>M_7:</math> <math>STOP</math>

=== Multiplikation zweier Variablen ===

Das folgende Programm berechnet das Produkt <math>x_1 \cdot x_2</math> von zwei nicht-negativen Zahlen <math>x_1, x_2</math> und speichert dieses in die Variable <math>x_3</math>.
Da wir schon ein Programm zur Implementierung der Addition zweier Variablen haben, verwenden wir diese, um eine Implementierung der Multiplikation zu entwickeln.

<math>M_1:</math> <math>x_3:=0</math>;
<math>M_2:</math> <math>x_4:=x_2</math>;
<math>M_3:</math> <math>{\rm IF} \quad x_4 = 0 \quad {\rm THEN} \quad {\rm GOTO} \quad M_{7}</math>;
<math>M_4:</math> <math>x_4 := x_4 - 1</math>;
<math>M_5:</math> <math>x_3 := x_3+x_1</math>;
<math>M_6:</math> <math>\mathrm{GOTO} \quad M_3</math>;
<math>M_7:</math> <math>STOP</math>;

Hier ist zu beachten, dass <math>M_5:</math> <math>x_3 := x_3+x_1</math> 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 <math>x_1, x_2</math>.

<math>M_1:</math> <math>x_3:=0</math>;
<math>M_2:</math> <math>x_4:=x_2</math>;
<math>M_3:</math> <math>{\rm IF} \quad x_4 = 0 \quad {\rm THEN} \quad {\rm GOTO} \quad M_{10}</math>;
<math>M_4:</math> <math>x_4 := x_4 - 1</math>;
<math>M_5:</math> <math>x_5:=x_1</math>;
<math>M_6:</math> <math>{\rm IF} \quad x_5 = 0 \quad {\rm THEN} \quad {\rm GOTO} \quad M_{3}</math>;
<math>M_7:</math> <math>x_3:=x_3+1</math>;
<math>M_8:</math> <math>x_5:=x_5-1</math>;
<math>M_9:</math> <math>\mathrm{GOTO} \quad M_6</math>;
<math>M_{10}:</math> <math>STOP</math>;

== 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-Programm#IF THEN ELSE|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 ==
* [[Sprunganweisung]] (GOTO)
* [[LOOP-Programm]]
* [[WHILE-Programm]]
* [[µ-Rekursion]]

== Literatur ==
* {{Literatur| Autor=[[Uwe Schöning]]| Titel=Theoretische Informatik – kurz gefasst| Auflage=5| Verlag=Spektrum Akademischer Verlag| Ort=Heidelberg| Kapitel=2.3 LOOP-, WHILE und GOTO-Berechenbarkeit| ISBN=978-3-8274-1824-1}}

[[Kategorie:Berechenbarkeitstheorie|Gotoprogramm]]

GOTO-Programm - Versionsgeschichte

217.61.192.163: ,