# 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$$.

Definitions: 1 2
Theorems: 3

Github: ### References

#### Bibliography

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