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. 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.Write a MM 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.