GOTO program

GOTO programs are special programs with a very simple syntax . Nevertheless, in connection with calculability , they play a major role in theoretical computer science , especially because it can be shown that every Turing-calculable function is GOTO-calculable.

syntax

GOTO programs have the following syntax in modified 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}}$ are trademarks (k ∈ ℕ)

${\displaystyle GOTO}$ is the set of all GOTO programs as defined above.

Every GOTO-calculable function is WHILE-calculable and vice versa.

Every Turing-calculable function is GOTO-calculable and vice versa.

Explanation of the syntax

Every GOTO program consists of a number of instructions , each separated by a semicolon. There is a (unique) label in front of each instruction , followed by a colon. ${\displaystyle P}$ ${\displaystyle A}$ ${\displaystyle M_{1},\ M_{2},\ \dots }$

GOTO programs have a finite number of variables and constants . Only five different statements are allowed: ${\displaystyle x_{1},\ x_{2},\ \dots }$ ${\displaystyle c}$

• Assignment of a variable by another (the same or a different) variable, augmented by a constant, for example

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

• or reduced by a constant, for example

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

• a jump instruction

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

• a conditional jump statement, where a variable is queried for equality with a constant, for example

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

• and the STOP statement

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

consequence

One can formally prove that every GOTO program can also be represented by an equivalent Pascal , C , C ++ or Java program, and vice versa.

Examples

Addition of two variables

The following GOTO program calculates the sum of two non-negative numbers and stores them in the variable . ${\displaystyle x_{1}+x_{2}}$ ${\displaystyle x_{1},x_{2}}$ ${\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}$

Multiplication of two variables

The following program calculates the product of two non-negative numbers and stores this in the variable . Since we already have a program to implement the addition of two variables, we use this to develop an implementation of the multiplication. ${\displaystyle x_{1}\cdot x_{2}}$ ${\displaystyle x_{1},x_{2}}$ ${\displaystyle x_{3}}$

  ${\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}$;

It should be noted here that formally there is no valid GOTO program, but must be replaced by a corresponding GOTO program for the addition. If you carry out this replacement, you get the following GOTO program for the multiplication of two non-negative numbers . ${\displaystyle M_{5}:}$ ${\displaystyle x_{3}:=x_{3}+x_{1}}$ ${\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 by WHILE program

A GOTO program

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

can be simulated by a WHILE program of the following form

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

in which

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

There are no IF THEN END statements in WHILE programs, but these can be implemented with LOOP or WHILE loops. The following program simulates an IF x ₁ = c THEN P1 END instruction, three new variables xn1, xn2, xn3 are used.

xn1:=x1-(c-1); xn2:=x1-c; xn3:=1;
LOOP xn1 DO
  LOOP xn2 DO
     xn3:=0
  END;
  LOOP xn3 DO
     P1
  END
END

See also

• Jump instruction (GOTO)
• LOOP program
• WHILE program
• µ recursion

literature

• Uwe Schöning : Theoretical Computer Science - in a nutshell . 5th edition. Spectrum Akademischer Verlag, Heidelberg, ISBN 978-3-8274-1824-1 , 2.3 LOOP, WHILE and GOTO predictability.