The random access machine with increment and decrement instructions, abbreviated as RAM-Inc-Dec, replaces the four arithmetic instructions Add, Sub, Mult, Div of the RAM (show on the picture) by the following two instructions:

Inc r₀ r₀ + 1 Dec r₀ r₀ 1

The other instructions remain the same. You are to show that the computing powers of the RAM and RAM-Inc-Dec are equivalent in principle by following the steps below.

a). In detail, show how to simulate Add instruction by Inc, Dec instructions together with Load, Store, and jump instructions. First describe your simulation method in high-level pseudocode like the factorial example, then translate it into instruction streams of RAM-Inc-Dec. Note that values of r_i and literal operands "=i" may be negative integers.

b). Describe clearly how to simulate Sub, Mult, Div instructions with help of high-level pseudo code; no need to translate the pseudocode into instruction streams of RAM-Inc-Dec. You may use previously simulated instructions as "subroutines" to simulate a new instruction. For example, you may use the RAM-Inc-Dec code simulating Add instruction as a subroutine to simulate Sub instruction, then use Add and/or Sub instructions as subroutines to simulate Mult and/or Div.

A RAM has three parts: The memory consisting of intinitely many cells ri, i 20. The cell ro is the accumulator where all arithmetic and comparison operations are performed. . The read-only input tape consisting of infinitely many cells, together with the read-head. The write-only output tape consisting of infinitely many cells, togcther with the write-hcad. * The read/write tape cells and * Initially the mcmory cclls rj, i20, contain 0 the memory cells r may contain integers only An instruction operand takes one of the two forms: i, indicating integer literal i i, indicating the contents of memory cell r * Definc v(a), the valuc of opcrand a, by: vi) i v(i) the contents of r The following is the instruction set. instruction operational semantics Load aoV(a) Store i Add a |h"-ro + v(a) Sub a Mult a ToTo*v(a) roro -v(a) Jump L unconditionally jump to label L Jgtz L f0, jump to label L; otherwise go to the next instruction Jzero Lifro -0, jump to label L; otherwise go to the next instruction Rcad iTvalue of input tape cell pointed by read-head; read-head moves one position to right. Write a v(a) is written in output tape cell pointed by write-head; write-head moves one position to right. Halt halt execution The following are an algorithm to compute the factorial function n!, n the input tape 1, and a RAM program implementingit. The value of n is initially given on r1 n; // read n r i r accumulates the product value n(n-(n-i) r3r1-r3 is a counter for (n-i), to be decremented by 1 in each iteration while r3> 0) 3 3-1i write r2; / rn stored on the input tape Read 1 Load 1 Store 2 Sub-1 Store 3 Load 3 Jgtz continue Jump endwhile while: ror3 //if ro> 0 then jump to "continue" // jump to "endWhile" continue: Load 2 r2 Hult 3 Store2 Load 3 Sub 1 Store 3 Jurp while rror rro r r3 jump to "while" // write r2 on the output tape endwhile: Write 2 Halt A RAM has three parts: The memory consisting of intinitely many cells ri, i 20. The cell ro is the accumulator where all arithmetic and comparison operations are performed. . The read-only input tape consisting of infinitely many cells, together with the read-head. The write-only output tape consisting of infinitely many cells, togcther with the write-hcad. * The read/write tape cells and * Initially the mcmory cclls rj, i20, contain 0 the memory cells r may contain integers only An instruction operand takes one of the two forms: i, indicating integer literal i i, indicating the contents of memory cell r * Definc v(a), the valuc of opcrand a, by: vi) i v(i) the contents of r The following is the instruction set. instruction operational semantics Load aoV(a) Store i Add a |h"-ro + v(a) Sub a Mult a ToTo*v(a) roro -v(a) Jump L unconditionally jump to label L Jgtz L f0, jump to label L; otherwise go to the next instruction Jzero Lifro -0, jump to label L; otherwise go to the next instruction Rcad iTvalue of input tape cell pointed by read-head; read-head moves one position to right. Write a v(a) is written in output tape cell pointed by write-head; write-head moves one position to right. Halt halt execution The following are an algorithm to compute the factorial function n!, n the input tape 1, and a RAM program implementingit. The value of n is initially given on r1 n; // read n r i r accumulates the product value n(n-(n-i) r3r1-r3 is a counter for (n-i), to be decremented by 1 in each iteration while r3> 0) 3 3-1i write r2; / rn stored on the input tape Read 1 Load 1 Store 2 Sub-1 Store 3 Load 3 Jgtz continue Jump endwhile while: ror3 //if ro> 0 then jump to "continue" // jump to "endWhile" continue: Load 2 r2 Hult 3 Store2 Load 3 Sub 1 Store 3 Jurp while rror rro r r3 jump to "while" // write r2 on the output tape endwhile: Write 2 Halt