In a unit-cost random access machine, the assignment of a constant \(c\in\mathbb N\) to a register \(r_i\) can be simulated using basic \(L O O P\) commands only:

Algorithm: Assignment of a Constant \(c\) to the Register \(r_i\) with a \(L O O P\)-Program

class UCRAM(): # unit-cost random access machine with 3 registers r_i = 0 r_j = 0 r_n = 0

  def set_r_n_to_5(self):
      # set r_n=0 with loop r_n do
      while True:
          if self.r_n > 0:
              self.r_n = self.r_n - 1 # LOOP register n
              self.NOP() # DO nothing
          else:
              break
      # set register to 5 by incrementing it 5 times
      self.r_n = self.r_n + 1
      self.r_n = self.r_n + 1
      self.r_n = self.r_n + 1
      self.r_n = self.r_n + 1
      self.r_n = self.r_n + 1

  def NOP(self):
      self.r_i = self.r_i + 1 #  LOOP register i
      self.r_i = self.r_i - 1  # LOOP register i
  1. Usage for adding the r_i = const
  2. creating a unit-cost access machine with registers initially set ucram = UCRAM()
  3. ucram.r_n // r_n is undefined
  4. ucram.r_i // r_i is undefined
  5. ucram.r_j // r_j is undefined

setting r_n:=constant (here 5)

ucram.set_r_n_to_5() print(ucram.r_i, ucram.r_j, ucram.r_n)

  1. will output
  2. will output

Algorithms: 1 2 3 4
Examples: 5


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