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}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e27dea222e23697b5dba7a1f4a6a8b9a2111a7b3)
![{\ 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}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/464c290058b0ea18353595e53555bed37401080b)
-
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.
![P](https://wikimedia.org/api/rest_v1/media/math/render/svg/b4dc73bf40314945ff376bd363916a738548d40a)
![A.](https://wikimedia.org/api/rest_v1/media/math/render/svg/7daff47fa58cdfd29dc333def748ff5fa4c923e3)
![{\ displaystyle M_ {1}, \ M_ {2}, \ \ dots}](https://wikimedia.org/api/rest_v1/media/math/render/svg/86f177b6959b1f8e8c3f07a961fa325fc3a7a372)
GOTO programs have a finite number of variables and constants . Only five different statements are allowed:
![{\ displaystyle x_ {1}, \ x_ {2}, \ \ dots}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7a4336679d8e3d08d243dc762d9b7d38da1deada)
![c](https://wikimedia.org/api/rest_v1/media/math/render/svg/86a67b81c2de995bd608d5b2df50cd8cd7d92455)
- Assignment of a variable by another (the same or a different) variable, augmented by a constant, for example
![{\ displaystyle x_ {1}: = x_ {2} +3}](https://wikimedia.org/api/rest_v1/media/math/render/svg/98e131d1adb2528dc6f9d021d3e4cfa53c85b8ce)
- or reduced by a constant, for example
-
.
![{\ displaystyle \ mathrm {GOTO} \ quad M_ {4}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e9f9bf164080bf2852f6ae058c20ca6e61ed9a52)
- 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}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5d4f0daf69f7be739edb53ca0a5d1021742cc4ee)
-
.
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 .
![x_1 + x_2](https://wikimedia.org/api/rest_v1/media/math/render/svg/6832c497a90f2dfd883818f60ee527f53b0de22d)
![x_ {1}, x_ {2}](https://wikimedia.org/api/rest_v1/media/math/render/svg/188263943645114e27e316cc1be787861e5b67be)
![x_ {3}](https://wikimedia.org/api/rest_v1/media/math/render/svg/766d09a498699be10e276ad49145c921f8cbe335)
;
;
;
;
;
;
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.
![x_1 \ cdot x_2](https://wikimedia.org/api/rest_v1/media/math/render/svg/cf3316d0af4e28c1d2152f928d97ca6a20d70702)
![x_ {1}, x_ {2}](https://wikimedia.org/api/rest_v1/media/math/render/svg/188263943645114e27e316cc1be787861e5b67be)
![x_ {3}](https://wikimedia.org/api/rest_v1/media/math/render/svg/766d09a498699be10e276ad49145c921f8cbe335)
;
;
;
;
;
;
;
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 x_ {3}: = x_ {3} + x_ {1}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4d0435280aa806749fe24fb8ef39023ca02abf95)
![x_ {1}, x_ {2}](https://wikimedia.org/api/rest_v1/media/math/render/svg/188263943645114e27e316cc1be787861e5b67be)
;
;
;
;
;
;
;
;
;
;
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.