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 Backus-Naur-Form:

• $P\; ::=\; M\_1\; :\; A\_1;\; ...\; ;\; M\_k\; :\; A\_k$
• $A\; ::=\; x\_i\; :=\; x\_j\; \backslash pm\; c\; \backslash ,\; |\; \backslash ,\; \backslash mathrm\{GOTO\}\; \backslash ,\; M\_i\; \backslash ,\; |\; \backslash ,\; \backslash mathrm\{IF\}\; \backslash ,\; x\_i\; =\; c\; \backslash ,\; \backslash mathrm\{THEN\}\; \backslash ,\; \backslash mathrm\{GOTO\}\; \backslash ,\; M\_j\; \backslash ,\; |\; \backslash ,\; \backslash mathrm\{STOP\}$
• $M\_1,\; ...,\; M\_k$ 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.

Konsequenz

---

Damit kann man formal zeigen, dass jedes BASIC-Programm auch durch ein äquivalentes Pascal-, C-, C++- oder Java-Programm dargestellt werden kann. Es ist also möglich, alles das, was man in Spagetticode schreibt, auch strukturiert zu schreiben - und umgekehrt.

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

---

• Goto
• LOOP-Programm
• WHILE-Programm
• µ-Rekursion

Berechenbarkeitstheorie