◀ ▲ ▶Branches / Theoretical-computer-science / Computability / Algorithm: Conditional execution of `\(L O O P\)` programs - IF-THEN-ELSE construct

In a unit-cost random access machine, the IF-THEN-construct can be simulated using basic \(L O O P\) commands as well as the algorithm for \(r_i:=c\) and the algorithm for the NOP operation.

Algorithm: Conditional execution of \(L O O P\) programs - IF-THEN-ELSE construct

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

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

  def set_r_n_to_1(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 n to 1 by incrementing it once
      self.r_n = self.r_n + 1

  def LOOP_r_i_DO_decrement_r_n(self):
      while True:
          if self.r_i > 0:
              self.r_i = self.r_i - 1 #  LOOP register i
              if self.r_n > 0:
                  self.r_n = self.r_n - 1  # DO decrement register n
          else:
              break

  def LOOP_r_n_DO_decrement_r_m(self):
      while True:
          if self.r_n > 0:
              self.r_n = self.r_n - 1 #  LOOP register n
              if self.r_m > 0:
                  self.r_m = self.r_m - 1  # DO decrement register m
          else:
              break

  def LOOP_r_n_DO_P1(self):
      while True:
          if self.r_n > 0:
              self.r_n = self.r_n - 1 #  LOOP register n
              # DO P1 and DO decrement register m
              self.P1()
              if self.r_m > 0:
                  self.r_m = self.r_m - 1
          else:
              break

  def LOOP_r_m_DO_P2(self):
      while True:
          if self.r_m > 0:
              self.r_m = self.r_m - 1  # LOOP register m
              self.P2()
          else:
              break

  def P1(self):
      print("executing P1")

  def P2(self):
      print("executing P2")

  def IF_ri_THEN_P1_ELSE_P2_END(self):
      self.set_r_m_to_1()
      self.set_r_n_to_1()
      self.LOOP_r_i_DO_decrement_r_n()
      self.LOOP_r_n_DO_P1()
      self.LOOP_r_n_DO_decrement_r_m()
      self.LOOP_r_m_DO_P2()

1. Usage of simulating an IF r_i==0 THEN P1 ELSE P2 END construct

2. creating a unit-cost access machine ucram = UCRAM() ucram.r_i = 100 ucram.IF_ri_THEN_P1_ELSE_P2_END() ucram.r_i = 0 ucram.IF_ri_THEN_P1_ELSE_P2_END()

3. will output

4. executing P2
5. executing P2

Mentioned in:

Algorithms: 1 2
Examples: 3

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

Github:

References

Bibliography

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