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 :
-
are trademarks (k ∈ ℕ)
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.
GOTO programs have a finite number of variables and constants . Only five different statements are allowed:
- Assignment of a variable by another (the same or a different) variable, augmented by a constant, for example
- or reduced by a constant, for example
-
.
- a conditional jump statement, where a variable is queried for equality with a constant, for example
-
.
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 .
;
;
;
;
;
;
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.
;
;
;
;
;
;
;
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 .
;
;
;
;
;
;
;
;
;
;
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 1 = 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
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.