Models of Computation - Mathematics 352 - Fall 2009

For HW #4

Q1: Is there a URM program such that, when given input R₁ = n (where n is a natural number), the program eventually stops with a 1 in R_n? (The other registers can be anything.)

Q2: Is there a URM program such that, when given input 0 in all registers, it eventually stops with a random output of 0 or 1 in R₁? (The question is not whether or not you can write such a program; rather, whether or not you think such a program exists.)

Q3: Suppose I have written a URM program P. I won't show you my program; I only tell you that it has 100 instructions. Does there exist an N such that all registers after R_N will always contain 0?