# Definition: LOOP Command, LOOP Program

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

#### $$(1)$$ The syntax of a LOOP command and a LOOP program

The syntax of a LOOP command and a LOOP program is defined by induction.

Base case * $$\mathtt{r_i:=r_i + 1}$$ is both, a LOOP command and LOOP program for all $$r_i$$. * $$\mathtt{r_i:=r_i - 1}$$ is both, a LOOP command and LOOP program for all $$r_i$$.

Induction step: Let $$P_1,P_2$$ be two LOOP programs. Then * $$\mathtt{P_1;P_2}$$ is a LOOP program. * $$\mathtt{LOOP~r_i~DO~P_1~END}$$ is both, a LOOP command and a LOOP program for all $$r_i$$.

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

#### $$(2)$$ The semantics of a LOOP command and a LOOP program

The semantics of the LOOP commands and a LOOP 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{LOOP~r_i~DO~P~END}$$ means that $$M$$ executes the program $$\mathtt P$$ exactly $$n$$ times, where $$n$$ is the natural number stored in the register $$r_i$$.

Examples: 1

Algorithms: 1 2 3 4 5 6 7
Definitions: 8 9
Examples: 10
Proofs: 11 12
Theorems: 13

Github: ### References

#### Bibliography

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