Models of Computation - Mathematics 450 - Spring 2005

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 0 in all registers except 1 in R_n?

Q2: Is there a URM program such that, when given input R₁ = n, it eventually stops with output R₁ = a random integer between 1 and n, inclusively? For example, if input is R₁ = 2, then, after say 1000 runs, about 500 times the output is 1, and about 500 times the output is 2.

Q3: Suppose I'm thinking of a URM program P with L instructions. Without knowing what P is or does, can you find an N in terms of L so that you can be sure all registers after R_N contain 0 when (and if) the program stops? What is the smallest such N (in terms of L)?