Implement unlimited register machines

Reference no: EM132992691

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)	r_n = 0
Successor	S(n)	r_n = r_n+1
Transfer	T(m,n)	r_n = r_m
Jump	J(m,n,q)	If r_n = r_m 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
????(????????, ... , ????????), 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)

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

Reference no: EM132992691

Questions Cloud

Describe flow of costs from raw materials to cost of good : Describe the flow of costs from raw materials to cost of goods sold (the flow all the way through the production process until they are sold to a customer)

Benefit from being sustainable in productions : How does a business (which has profitability as its goal) benefit from being sustainable in its productions?

Type of marketing strategy : John spent time on bank websites looking up mortgage rates. He then started to receive ads from a mortgage company whenever he visited a webpage.

Change process at minnesota biolabs : A discussion of how managers may utilize different forms of data collection during the change process at Minnesota Biolabs.

Implement unlimited register machines : Implement Unlimited Register Machines - In this assignment you are required to implement Unlimited Register Machines (URMs) using three different languages

Formulate strategies in specific order : There are 5 categories of strategy formulation available to utilize: directional strategies, adaptive, market entry, competitive, and implementation strategies.

What are the 4 p of marketing : What are the 4 P's of Marketing? Summarize ways that marketing creates utility for business in each area. a good or a service for each of the following product

Design a market strategy : Choose a sole proprietorship company of your own? Design a market strategy in case of perfect competition use S.W.O.T analysis to demonstrate your analysis?

Case study-danforth manufacturing company : What are the problems DMC is facing and how would they solve the problem utilizing solutions?

User Account

All Pages