Recall the simulation of RAMs by multi-tape DTMs described in class and consider
ID: 3753506 • Letter: R
Question
Recall the simulation of RAMs by multi-tape DTMs described in class and consider the RAM program to compute n! described on picture(1) . Show the contents of tape 1 (simulating the RAM memory) and tape 2 (simulating the accumulator r0) after the execution of each instruction in this RAM program up to the first execution of "Mult 3". Use a format similar to Question on picture (2)(3) , and abbreviate integers in unary notation to decimal notation.
Solution :
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 HaltExplanation / Answer
Read 1
##1#n##
Empty
Load 1
##1#n##
n
n
Sub =1
n-1
Store 3
n-1
Load 3
n-1
Load 2
n
n*(n-1)
INSTRUCTION TAPE 1(RAM MEMORY) TAPE 2(ACCUMULATOR)Read 1
##1#n##
Empty
Load 1
##1#n##
n
Store 2 ##1#n##2#n##n
Sub =1
##1#n##2#n##n-1
Store 3
##1#n##2#n##3#n-1##n-1
Load 3
##1#n##2#n##3#n-1##n-1
Load 2
##1#n##2#n##3#n-1##n
Mult 3 ##1#n##2#n##3#n-1##n*(n-1)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.