Unlimited Register Machines(orURMs) are mathematical abstractions of real-life computers. They are more user-friendly thanTuring Machinesand make an ideal introduction to machine models of computability. Any effectively computable function can be computed on a URM.

URMs were invented by J. C. Shepherdson and H. E. Sturgis.

In this assignment you are required to implement Unlimited Register Machines (URMs) using Java,Python and LISP. i.e., you are required to write programs in these languages that imitate the functionality of URMs (to develop Virtual URMs).

1.Description of the Unlimited Register Machines, A URM hasregisters R0,R1,R2,...,which store natural

numbersr0,r1,r2,...: R0R1R2R3R4R5...

r0r1r2r3r4r5...

A URMprogramis a finite list of instructions, each having one of the four following basic types:

Instruction Type

Notation

Effect

Zero Z(n) Successor S(n) Transfer T(m,n)

rn= 0 rn= rn+1 rn= rm

Jump

J(m,n,q)

Ifrn=rmgoto instruction q, else go to the next instruction.

Z(n)- sets value of register Rnto zero and moves to the next instruction in the program list.

S(n)- increases the value of register Rnby one and moves to the next instruction in the program list.

T(m,n)- copies the value of Rmto Rnand moves to the next instruction in the program list.

J(m,n,q)- if rm= rn, the instruction at index q in the program list is executed. Else the next instruction in the program list is executed.

URM programs are zero-based indexed lists ofinstructions, i.e., instructions in a program can be accessed via indexes and the index of thefirstinstruction is0.

A URM program starts with the first instruction (at index 0) and executes instructions consecutively, one by one, unless it encounters the Jump instruction. The programhaltsafter execution reaches theendof the program list or aJumpinstruction J(m,n,q) is executed, whereq is not a valid indexin the program list.

URM is used to compute functions thattake integer parameters and return an integer value.

Input and Output conventions:To compute a function(,...,), we start with,...,in registers

, ... ,, respectively, and with 0 in all the other registers. If computation halts, the output is the number in register R0.

Example 1.Addition function,m + n, can be computed by the following URM program:

0)J(1,2,4)

1)S(0)

2)S(2)

3)J(0,0,0)

Example 2.Product function,m*n, can be computed by the following URM program:

0)T(0,2) 1)Z(0) 2)Z(3) 3)Z(4) 4)J(2,4,13) 5)J(1,3,13) 6)S(0) 7)S(4) 8)J(2,4,10) 9)J(1,1,6) 10)S(3) 11)Z(4) 12)J(1,1,5)

2. Programming tasks.

You are required toimplement Unlimited Register Machines (URMs) in three different languages -Java,CandPython.

Implementation Requirements:

Set of URM's registers should be implemented as an array or list of integers.

Instruction types should be coded by the integers {0,1,2,3}: use0forZ,1forS,2forTand3forJ.

Instructionsshouldberepresentedbyarraysorlists of integers, for example, instructionJ(1,2,4)in Python program should be represented by the list[3,1,2,4].

Programs should be implemented as arrays or lists of instructions. For example, the program from Example 1 should be represented by the following list of lists in Python implementation:

• program = [[3,1,2,4], [1,0], [1,2], [3,0,0,0]]

Also, you are required to write the following three functions/methods ineach of the implementations:

(1)isValidCommand(command)- takes a list/array of integers and returnstrueif it is a valid URM command, otherwise returnsfalse.

(2)isValidProgram(program)- takes a list of instructions and returnstrueif it is a valid URM program, otherwise returnsfalse.

(3)run(program, registers)- runs the URM program on the list/array of registers.

(4)main()- this is a testing method/function where you test implementation of URM by running the program from Example 1.

3.Write a URM power program.

In this task you are required to write and test, using one of implementations, aURM programthat computes thepowerfunction. I.e.,power(m,n)should computemn. For example, power(2,3) should return 8.