Reference no: EM133001084
ASSIGNMENT - Modelling Unlimited Register Machines
Introduction.
Unlimited Register Machines (or URMs) are mathematical abstractions of real-life computers. They are more user-friendly than Turing Machines and 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 three different languages - Java, C and Python. 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 has registers R0,R1,R2,..., which store natural numbers r0,r1,r2,...:
R0 R1 R2 R3 R4 R5 ...
r0 r1 r2 r3 r4 r5 ...
A URM program is a finite list of instructions, each having one of the four following basic types:
|
Instruction Type
|
Notation
|
Effect
|
|
Zero
|
Z(n)
|
rn = 0
|
|
Successor
|
S(n)
|
rn = rn+1
|
|
Transfer
|
T(m,n)
|
rn = rm
|
|
Jump
|
J(m,n,q)
|
If rn = rm go to instruction q, else go to the next instruction.
|
- Z(n) - sets value of register Rn to zero and moves to the next instruction in the program list.
- S(n) - increases the value of register Rn by one and moves to the next instruction in the program list.
- T(m,n) - copies the value of Rm to Rn and 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 of instructions, i.e., instructions in a program can be accessed via indexes and the index of the first instruction is 0.
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 program halts after execution reaches the end of the program list or a Jump instruction J(m,n,q) is executed, where q is not a valid index in the program list.
URM is used to compute functions that take integer parameters and return an integer value.
Input and Output conventions: To compute a function f(n1,.....nk), we start with n1,.....nk in registers R0,......,Rk-1, 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)
Programming tasks.
You are required to implement Unlimited Register Machines (URMs) in three different languages - Java, C and Python.
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}: use 0 for Z, 1 for S, 2 for T and 3 for J.
• Instructions should be represented by arrays or lists of integers, for example, instruction J(1,2,4) in your 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 your 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 in each of the implementations:
(1) isValidCommand(command) - takes a list/array of integers and returns true if it is a valid URM command, otherwise returns false.
(2) isValidProgram(program) - takes a list of instructions and returns true if it is a valid URM program, otherwise returns false.
(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 your implementation of URM by running the program from Example 1.
3. Write a URM program.
In this task you are required to write and test a URM program that computes the product of two numbers.
Attachment:- Modelling Unlimited Register Machines.rar