PROBLEM

In this homework you will be experimenting with a given process on number sequences. This process resemble the action of a simplified Von Neumann Machine. You will observe that the number sequence (which will change from problem to problem) acts like a machine code program loaded into the memory of a Von Neumann machine. The two registers ${\cal R}_1$, ${\cal R}_2$ and the instruction pointer ${\cal I}$, the only three internals of the process, carry out the functions of the data, address, condition and the instruction registers of a Von Neumann machine.

Our process (lets name it from now on as the HW-1 machine) works on a sequence of integers each of which are in the range [-127,+127]. Here is an example for such a sequence:

If we are speaking about the value of the 3rd element in the sequence then we will denote this by enclosing the 3 into square brackets, like [3]. In the example above [3] is 33.

Furthermore, the HW-1 machine has three registers which we name as ${\cal R}_1$, ${\cal R}_2$ an ${\cal I}$.Each one of ${\cal R}_1$ and ${\cal R}_2$ can hold an integer in the range [-127,+127]. Storing negative values into ${\cal I}$ is not allowed, it can hold any integer in the range [0,+255] (though in your exercises the values of ${\cal I}$ will be about 10-30, at most). The square bracket notation applies for these registers as well. Namely $[{\cal R}_1]$ means the content of the ${\cal R}_1$th element in the sequence. So, for instance, if ${\cal R}_1$ has at any moment the value 3 and if at that moment the 3rd sequence element is 33 (as it is in the example above) then $[{\cal R}_1]$ refers that 33.

The interesting point is that the values in the sequence as well as the values in the registers can be changed freely to new values. When this is the case the former value is erased and the new value is substituted in that place. We will call this action an assignment and will represent it by the following notation:

place $\leftarrow$ new value

Here are some assignment examples:

$${\cal R}_1\leftarrow 5 {\cal R}_1$$

$${\cal R}_1\leftarrow {\cal R}_2 {\cal R}_1 {\cal R}_2 {\cal R}_2 {\cal R}_1$$

$${\cal R}_2\leftarrow [2] {\cal R}_2$$

$$[0] \leftarrow {\cal R}_1 {\cal R}_1$$

$${\cal I}\leftarrow {\cal I}+ 1 {\cal I}$$

The number of changes is not limited and can be performed as many times as desired on any register or sequence element.

Given a sequence, HW-1 starts with the ${\cal I}$ register having 0 (zero) value and the other two registers having arbitrary values. It works by repeatatively going through a process cycle until a halt instruction is executed. A process cycle is:

1.

Take $[{\cal I}]$ as an instruction.

2.

If this instruction is the halt instruction then terminate the process,

3.

else perform the action associated with that instruction.

4.

Continue with step (1).

If any instruction described in the following two pages computes a result (at any cycle) that falls out of the limits then the machine automatically halts.

The HW-1 accepts 17 instructions which are explained below. Instructions are recognized as integers [0,1,...,16].

Instruction

Halt the process..

Instruction

Load ${\cal R}_1$ with the next number in the sequence.

$${\cal R}_1\leftarrow [{\cal I}+1] \;,\quad {\cal I}\leftarrow {\cal I}+ 2$$

Instruction

Load ${\cal R}_2$ with the next number in the sequence.

$${\cal R}_2\leftarrow [{\cal I}+1] \;,\quad {\cal I}\leftarrow {\cal I}+ 2$$

Instruction

Load ${\cal R}_1$ with the sequence element which is at the position given as the next number in the sequence.

$${\cal R}_1\leftarrow [[{\cal I}+1]] \;,\quad {\cal I}\leftarrow {\cal I}+ 2$$

Instruction

Load ${\cal R}_2$ with the sequence element which is at the position given as the next number in the sequence.

$${\cal R}_2\leftarrow [[{\cal I}+1]] \;,\quad {\cal I}\leftarrow {\cal I}+ 2$$

Instruction

Load ${\cal R}_1$ with the content of ${\cal R}_2$.

$${\cal R}_1\leftarrow {\cal R}_2\;,\quad {\cal I}\leftarrow {\cal I}+ 1$$

Instruction

Load ${\cal R}_1$ with the sequence element which is at the position ${\cal R}_2$.

$${\cal R}_1\leftarrow [{\cal R}_2] \;,\quad {\cal I}\leftarrow {\cal I}+ 1$$

Instruction

Change the sequence element which is at the position ${\cal R}_1$ to be the content of ${\cal R}_2$.

$$[{\cal R}_1] \leftarrow {\cal R}_2\;,\quad {\cal I}\leftarrow {\cal I}+ 1$$

Instruction

Change the sequence element which is at the position given as the next number in the sequence to the content of ${\cal R}_1$.

$$[[{\cal I}+1] ]\leftarrow {\cal R}_1\;,\quad {\cal I}\leftarrow {\cal I}+ 2$$

Instruction

Take the sequence element which is at the position given as the next number in the sequence as the next instruction to be performed.

$${\cal I}\leftarrow [{\cal I}+ 1]$$

Instruction

If ${\cal R}_1$ contains zero continue with the sequence element following the next one as the next instruction to be performed, otherwise act like the instruction 9.

$$\begin{array} {l@{\quad:\quad}l} \mbox{if}\;\;{\cal R}_1=0 ... ...box{otherwise} & {\cal I}\leftarrow [{\cal I}+1] \end{array}$$

Instruction

Increment ${\cal R}_1$ by the content of ${\cal R}_2$.

$${\cal R}_1\leftarrow {\cal R}_1+ {\cal R}_2\;,\quad {\cal I}\leftarrow {\cal I}+ 1$$

Instruction

Decrement ${\cal R}_1$ by the content of ${\cal R}_2$.

$${\cal R}_1\leftarrow {\cal R}_1- {\cal R}_2\;,\quad {\cal I}\leftarrow {\cal I}+ 1$$

Instruction

Multiply ${\cal R}_1$ by the content of ${\cal R}_2$.

$${\cal R}_1\leftarrow {\cal R}_1\times {\cal R}_2\;,\quad {\cal I}\leftarrow {\cal I}+ 1$$

Instruction

Divide ${\cal R}_1$ by the content of ${\cal R}_2$ (integer division).

$${\cal R}_1\leftarrow {\cal R}_1\div {\cal R}_2\;,\quad {\cal I}\leftarrow {\cal I}+ 1$$

Instruction

Change the sign of the value in ${\cal R}_1$.

$${\cal R}_1\leftarrow -{\cal R}_1\;,\quad {\cal I}\leftarrow {\cal I}+ 1$$

Instruction

Compare the content of ${\cal R}_1$ with the content of ${\cal R}_2$.

$$\begin{array} {l@{\quad:\quad}l} \mbox{if}\;\;{\cal R}_1={\... ...{\mbox{always}\;\;{\cal I}\leftarrow {\cal I}+ 1} \end{array}$$