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 (s. unten).

Syntax

Goto-Programme haben folgende Syntax in Backus-Naur-Form:

• $P::=M_{1}:A_{1};...;M_{k}:A_{k}$
• $A::=x_{i}:=x_{j}\pm c\,|\,\mathrm {GOTO} \,M_{i}\,|\,\mathrm {IF} \,x_{i}=c\,\mathrm {THEN} \,\mathrm {GOTO} \,M_{j}\,|\,\mathrm {STOP}$
• $M_{1},...,M_{k}$ sind Marken (z. B. $\in \mathbb {N}$)

$GOTO$ ist die Menge aller Goto-Programme gemäß Backus-Naur-Form.

Jede GOTO-berechenbare Funktion ist WHILE-berechenbar und umgekehrt.

Jede Turing-berechenbare Funktion ist GOTO-berechenbar.

Konsequenz

Damit kann man ganz formal zeigen, daß 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 Spaghetticode schreibt, auch strukturiert zu schreiben.

Siehe auch

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