Definition: GOTO Command, GOTO Program, Index

Let \(M\) be a unit-cost random access machine with the registers \(r_1,\ldots, r_n\).

The syntax of a GOTO command is defined by:

An index is a natural number \(j > 0\).
For all registers \(r_i\) and all indices \(j\):
- \(\mathtt{r_i:=r_i + 1}\) is a GOTO command,
- \(\mathtt{r_i:=r_i - 1}\) is a GOTO command,
- \(\mathtt{ I F~r_i=0~G O T O~j} \) is a GOTO command.

The syntax of a GOTO program is defined by:

\(\mathtt{j : C}\) is a GOTO program, if \(\mathtt{C}\) is a GOTO command,
\(\mathtt{P_1;P_2}\) is a GOTO program, if \(\mathtt{P_1,P_2}\) are two GOTO programs.

A GOTO program terminates, if there are no more GOTO commands / GOTO programs left to be executed.

Without any loss of generality, all program lines can be numbered by consecutive indices \(j=1,2,\ldots \).

The semantics of the GOTO commands and a GOTO programs described above is as follows:

\(\mathtt{r_i:=r_i + 1}\) means that \(M\) increments the natural number, which is contained in the register \(r_i\).
If \(r_i > 0\), \(\mathtt{r_i:=r_i - 1}\) means that \(M\) decrements the natural number contained in the register \(r_i\).
If \(r_i=0\), \(\mathtt{r_i:=r_i - 1}\) means that \(M\) does not change the register \(r_i\) at all.
\(\mathtt{P_1;P_2}\) means that \(M\) executes the program \(\mathtt {P_1}\). After the termination of this program, \(M\) continues with the execution of the program \(\mathtt {P_2}\).
\(\mathtt{j : P}\) means that \(M\) executes the program \(P\).
\(\mathtt{ I F~r_i=0~G O T O~j} \) means that \(M\) compares the value of the register \(r_i\) with \(0\). If \(r_i\neq 0\), then \(M\) ignores the command and continues to execute the program with the next index to the index of the current program. Otherwise (i.e. if \(r_i=0\)), \(M\) continues to execute the program with the next index \(j\).

Definitions: 1 2
Theorems: 3

Thank you to the contributors under CC BY-SA 4.0!

Erk, Katrin; Priese, Lutz: "Theoretische Informatik", Springer Verlag, 2000, 2nd Edition