Example: Simulating More Complex Commands Using Basic \(L O O P\) Commands

(related to Definition: LOOP Command, LOOP Program)

The basic syntax and semantics of a \(L O O P\) program is very plain and simple: It is only possible to increment and decrement a register and repeat a \(L O O P\) program a number of times. However, using these basic commands, it is possible to simulate a lot of more complex commands, among others:

the assignment of a constant value to a register, \[\mathtt{r_i:=c;}\]

setting the value of a register to the value of another register plus/minus a constant, \[\mathtt{r_i:=r_j\pm c;}\]

checking if a register equals \(0\) and, based of this comparison, a conditional execution of a \(L O O P\) program (if-then-else construct), \[\mathtt{IF~r_i=0~THEN~P_1~ELSE~P_2~END;}\]

checking if a register is greater then a constant value and, based of this comparison, a conditional execution of a \(L O O P\) program (if-then construct), \[\mathtt{IF~r_i > c~THEN~P~END;}\]

the no-operation command (NOP command), \[\mathtt{NOP;}\]

addition (or subtraction) of two registers, \[\mathtt{r_i:=r_j\pm r_k;}\]

multiplication of two registers, \[\mathtt{r_i:=r_j\ast r_k;}\]

division with quotient and remainder, \[\begin{array}{l} \mathtt{r_q:=r_j~DIV~r_k;}\\ \mathtt{r_r:=r_j~MOD~r_k;} \end{array}\]

and many more...

  1. Algorithm: Setting the value of a register to the value of another register plus or minus a constant
  2. Algorithm: Conditional execution of \(L O O P\) programs - IF-THEN-ELSE construct
  3. Algorithm: Conditional execution of \(L O O P\) programs - IF-THEN construct
  4. Algorithm: Addition (or Subtraction) of Two Registers
  5. Algorithm: Multiplication of Two Registers
  6. Algorithm: No-Operation Command (NOP)
  7. Algorithm: Division with Quotient and Remainder (Unit-cost Random Access Machine)
  8. Algorithm: Assignment of a Constant \(c\) to the Register \(r_i\) with a \(L O O P\)-Program

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

Github:
bookofproofs


References

Bibliography

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