Models of Computation - Mathematics 450 - Fall 2006

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 R₁ = 0 or 1? (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. Can you find an N so that you can be sure all registers after R_N contain 0 when (and if) my program stops?