ASSIGNMENT 2. Modelling Minsky Machines.
35 MARKS
0.Introduction.
Minsky Machines (or MMs) are mathematical abstractions of
real-life computers. Any effectively computable function can be computed on a
MM. It is easier to write a program for MMs than Turing Machines and their
behaviour is closer to real computers. MMs were invented by Marvin Minsky. In
this assignment you are required to implement Minsky Machines (MMs) using three
different languages – Java, C and Python. i.e., you are required to write
programs in these languages that imitate the functionality of MMs (to develop
Virtual MMs).
1.
Description of the Minsky Machines. A MM has a
finite number of registers R0,R1,…,Rn-1 that can store non-negative integers
r0,r1,…,rn-1: R0 R1 … Rn-1 r0 r1 … rn-1 Fig 1. Minsky Machine with n registers.
A MM program is a finite list of instructions, each having one of the following
three basic types: • I(k;i) – increments the value of register Rk by one and
moves to the instruction at index i in the program list. • D(k;i,j) – if the
value of register Rk is greater than 0, then the instruction decrements the
register’s value by one and moves to the instruction at index i in the program
list. Otherwise, the value stays 0 and execution moves to the instruction at
index j in the program list. • HALT – halts the execution. MM programs are
zero-based indexed lists (arrays) of instructions, i.e., first index of the
list is 0. We will assume a convention that the instruction at index 0 is
always HALT. A MM program, therefore, should start with the instruction at
index 1 and then the execution is governed by the instructions. The program
halts when it is directed to the instruction at index 0, i.e., HALT. MMs with
only two registers can be used to compute algorithmically computable (general
recursive) functions, e.g., a sum of two numbers, a product of two numbers etc.
Note. Sometimes, in the literature, registers of MMs are called glasses, where
one can put or remove coins (numbers). So, you can easily build such a machine
in your kitchen. Fig 2. Minsky Machine with four registers. Example 1.
Computations in MMs can be coded in many different ways. Therefore, before
computing a certain function we need to make conventions about how to represent
the input to the function and which register will contain the result of the
computation. In this example, we use a three-register MM to compute a sum of
two numbers, m + n. The program is written so that if the arguments m and n are
put in the registers R0, R1 correspondingly, the result will be put in the
register R0. Here’s the program: 0.HALT 1.D(1;2,0) 2.I(0;1) 2.
2.
Programming tasks.
You
are required to implement Minsky Machines (MMs) in three different languages –
Java, C and Python. Implementation Requirements: • Set of MM’s registers should
be implemented as an array or list of integers. • Instruction types should be
coded by the integers {0,1,2}: use 0 for I, 1 for D, 2 for HALT. • Instructions
should be represented by arrays or lists of integers, for example, instruction
D(1;2,0) in your Python program should be represented by the list [1,1,2,0]. •
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 = [[2],[1,1,2,0],[0,0,1]] In addition,
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 MM command, otherwise returns false. (2)
isValidProgram(program) – takes a list of instructions and returns true if it
is a valid MM program, otherwise returns false. (3) run(program, reg) – runs
the MM program on the MM with the reg number of registers. Please note, that
depending on the implementation and language, you may have a different number
of parameters in this function. (4) main() – this is a testing method/function
where you test your implementation of URM by running the program from Example
1.
3.
3.Write a
URM program.
In this task you are required to write and
test a program for a Minsky Machine with four registers that computes the
product of two numbers m and n. For this task you should follow the following
conventions: Before the computations start, the arguments m, n should be put in
the first two registers, R0, R1 correspondingly. Result of the computations,
i.e., m*n, should appear in the last register, R3. Allocated Marks: See Course
Description Due Date: See Course Description Please refer to the Course
Description for information relating to late assignments and special
consideration. Assignment Submission: You must supply your program source code
files and report documentation as single compressed archive called:
ITECH5403_Assignment_2__.zip Assignments will be
marked on the basis of fulfilment of the requirements and the quality of the
work. In addition to the marking criteria, marks may be deducted for failure to
comply with the assignment requirements, including (but not limited to): •
successful compilation • successful completion of the required tasks •
adherence to the guidelines provided • quality of code that adheres to the
programming standards for the Course; including: 1. comments and documentation 2.
code layout 3. meaningful variable names Submit your assignment (all program
source files plus your discussion document) to the Assignment 2 upload location
on Moodle before the deadline. The mark distribution for this assignment is
explained on the next page.