Definition: GOTO Command, GOTO Program, Index
Let \(M\) be a unit-cost random access machine with the registers \(r_1,\ldots, r_n\).
\((1)\) The syntax of a GOTO command and a GOTO program
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 \).
\((2)\) The semantics of a GOTO command and a GOTO program
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\).
Mentioned in:
Definitions: 1 2
Theorems: 3
Thank you to the contributors under CC BY-SA 4.0!
![](https://github.com/bookofproofs/bookofproofs.github.io/blob/main/_sources/_assets/images/calendar-black.png?raw=true)
- Github:
-
![bookofproofs](https://github.com/bookofproofs.png?size=32)
References
Bibliography
- Erk, Katrin; Priese, Lutz: "Theoretische Informatik", Springer Verlag, 2000, 2nd Edition