Z-Machine

The Z Machine Problem:

This is a computer science challenge related to Turing Machines. This programming problem is from the Oxford Department of Computer Science's "interviews" (final exam? entrance exam? not clear) via John Graham-Cumming (link).

The Z Machine

Here is the problem setup:

Suppose you have a computer with a very simple memory layout. The memory consists of a series of numbered locations, each of which can store numbers. These numbers are positive or negative integers. Here is an illustration of an example of this memory layout:

Z-Machine Instructions

The machine can only perform three instructions: Zero (Z), Increment (I), and Jump (J).

The Z operator zeros out a location in memory. The operation specifies which index should be zeroed out. For example, Z4 will zero out index 4 (which is the 5th item in memory, since indexing starts at 0).

The I operator increments the value at a location in memory by 1. The operation specifies which index should be incremented. For example, I6 will increment index 6 (the 7th item in memory) by 1.

The J operator compares two locations in memory. If the values are different, the jump operator will branch (that is, jump to a different location in the code). The two locations are specified when calling the operator, and an arrow (or operation number) indicates where the operator should branch TO if the values are not the same. If the values are the same, the code continues.

The program stops when it reaches the end of the instruction list.

Example: Loop

Here is an example of a loop program. This program sets memory index 4 to 0, then increments it until it is equal to the value in memory index 20:

001   Z4
002   I4
003   J4,20 --> 002

Implementing Addition

Suppose a machine has two numbers in the first two locations in memory. Utilize these three operations to add the two numbers together and put the result into the third location in memory.

Under what circumstances does the program fail?

Solution Approach and THE MATHS

To approach the solution, start with the maths. What we're doing is trying to define a "complex" arithmetical operation (addition) from simpler "unit" operations (increment by one), so it will be helpful to wipe our mental slate clean and start at the very beginning of the problem.

When I teach a math class, whether it be a developmental math class, an algebra class, or a calculus class, I always spend the first "full" lecture by guiding the students through this very procedure. Here's how I set the tone: "Imagine that you are stranded on a desert island, with no calculators, no math books, nothing but your fingers and toes. Now suppose you are tasked with reinventing all of mathematics, entirely from scratch. How would you do it?"

This is a challenging task - and part of the challenge is just knowing where to begin (just how clean should you wipe the mental slate?). The Z-Machine problem formulation resolves that problem by explicitly enumerating valid operations. But let's continue with the desert island analogy for a bit.

If we begin at what is truly the beginning, we can start with a single unit, the number 1. (If we want to fast forward through thousands of years of human history, we can instead start with the number 0 in addition to the number 1.) Having only a single number is boring, because we can't count anything. We need a way to generate more numbers. So, we begin by defining an increment operation. We begin with the unit, 1. We declare that we can combine 1 with any other number. When we combine 1 with another 1, we get a new, larger number - which we arbitrarily call two, and represent using this funny squiggle: 2.

Now that we have defined the increment operation, adding a unit, we can begin to generate new numbers. We start with 1+1, which gives 2. The next number can be found by adding 1 to 2, which gives us a new number that we arbitrarily call three, and represent with a funny squiggle: 3.

We continue in this manner, until we reach 9, and run out of squiggles to write. The next number we will get is a special number, because it is equal to the total number of fingers. When we get to 9, and add one more, we get "two hands", which we arbitrarily call ten. If we want to keep counting beyond ten, we're stuck, because we've run out of fingers. But we can take a shortcut - we can let one toe represent "two hands". So, we hold up one toe, to represent ten. To write ten, we can let the first digit represent how many toes we are holding up, and the second digit represent how many fingers we are holding up. That means we can write our "two hands" quantity as 10 - one toe, no fingers.

We can keep on incrementing by 1, and using this system we can count all the way up to 99, at which point we will need another pair of hands or feet to keep generating new numbers, or we can suppose that after counting to 99, we are able to hold numbers in our head.

But once again, we're generating numbers slowly. We want a way to generate more numbers, faster, so we can count higher. So, we define a new addition operation. Rather than adding 1, we define the general operation of addition recursively. To add two numbers like a and b, we can define this addition in terms of a unit increment:

$a+b=a+1+1+1+\dots +1$

We increment the quantity a by 1, b times. This gives us a way to add arbitrary numbers together, so now we can reach much larger numbers by taking the largest number that we can count to, and adding that number to itself.

If we extend this approach (recursively performing the +1 operation b times, and calling it a new operation +b), we can get multiplication by b (adding a number to itself, b times) and even define more advanced operations like exponentiation and tetration.

Solution 1: Positive Integers Only

Adding two positive integers is the simplest case. Essentially, we just perform two loops: the first loop increments the result and increments a temporary variable 1, and does that until the temporary variable 1 is equal to the first number. The second loop increments the result and increments the result by 1 for a number of times equal to the number at index 1.

001   Z2                    // clear space for the result
002   Z3                    // clear space for temp variable 1
003   I2                    // increment result
004   I3                    // increment temp variable 1
005   J3,0 --> 003
006   Z4                    // clear space for temp variable 2
007   I2                    // increment result
008   I3                    // increment temp variable 2
009   J4,1 --> 007
010   Z3                    // clean up

Because we only have an increment operation at our disposal, there is no way for us to deal with adding negative numbers. Dittos for non-integer real numbers .

Solution 2: Dealing with Zeros

A second solution that is a bit more challenging is dealing with the case of possible zeros in the first or second position. The algorithm above will increment the result and the temporary variable at least once (similar to a do-while loop structure), which will always cause the comparison operation J2,0 or J3,1 to fail. Here is code that can deal more gracefully with a zero in either the first or second positions:

001     Z3
002     Z4 // temp 0
003     Z5 // temp 1
004     Z6 // is index 0 a zero?
005     Z7 // is index 1 a zero?
006     Z8 // zero
007     Z9 // one
008     I9

// increment by amount in index 0
009     J0,8 --> 014
010     I6
011     J4,6 --> 014
012     I4
013     I3
014     J0,4 --> 009

// increment by amount in index 1
015     J1,8 --> 020
016     I7
017     J7,8 --> 020
018     I5
019     I3
020     J1,5 --> 017

021     Z4
022     Z5
023     Z6
024     Z7

Or, in pseudo Z-Machine code:

A001 result = 0
A002 temp0 = 0
A003 temp1 = 0
A004 ix0iszero = 0
A005 ix1iszero = 0
A006 zero = 0
A007 one = 1

B001 compare(ix0,zero) --> B006
B002 ix0iszero++
B003 compare(ix0iszero, zero) --> B006
B004 temp0++
B005 result++
B006 compare(ix0, temp0) --> B003

C001 compare(ix1,zero) --> C006
C002 ix1iszero++
C003 compare(iz1iszero, zero) --> C006
C004 temp1++
C005 result++
C006 compare(ix1, temp1) --> C003

D001 temp1 = 0
D002 temp2 = 0
D003 ix0iszero = 0
D004 ix1iszero = 0

Note that this pattern can be expanded to work for adding an arbitrary number of numbers; one simply needs to add an additional temp variable and an additional iszero variable for each new number being added to the total, then another block of 6 statements. These 6 statements check if the number we are adding is zero, and if it is not, the result is incremented by that many times.

Addition Pseudocode

To develop this idea, I started with a pseudocode sketch of the operation:

result = 0
temp1 = 0
temp2 = 0
zero = 0
if(ix0 != zero) { 
  while(temp1 != ix0) {
    temp1++
    result++
  }
}
if(ix1 != zero) {
  while(temp2 != ix1) { 
    temp2++
    result++
  }
}
temp1 = 0
temp2 = 0

Unfortunately, this pseudocode was not easy to convert into Z-Machine instructions, because of the way that the Jump operation works. What we really need is a way to tuck the while loops into he set of instructions in such a way that they will only be run when the digit being added is non-zero. Structuring it using only the available Z-Machine operations required some visual brainstorming, in addition to pseudocode:

This solution had to implement an additional variable to keep track of whether the number in the first position was zero. That variable was used as a way to skip any of the increment operations for the case of the first position being zero.

Implementing Subtraction

Suppose an operator places a number into the first element of the Z-Machine's memory. We require that the Z-Machine subtract 1 from that number, and place it in the next cell over.

The pseudocode approach here is:

• Increment one (dummy) cell
• If the dummy cell is not equal to the target cell,
• Increment the result cell.

Z-Machine Code

001   Z1
002   Z2
003   Z3
004   I3             // memory index 3 stores the number 1
005   J2,3 --> 007
006   I1
007   I2
008   J2,0 --> 006

Subtraction Pseudocode

The structure of the Z-Machine code above came to me in a stroke of inspiration on the subway. I needed a way to ONLY increment ix2 the first time through, so that it can stay ahead of the neighbor cell by +1 (this is the subtraction mechanism, minus 1). I did this by using a jump condition (instruction 005) that is always false the first time through. By forcing the jump condition to branch the first time through, it allows us to skip one instruction. By inserting a second jump statement, we can ensure that the instruction that was skipped the first time through is run every other time.

ix1 = 0
ix2 = 0
while( ix1 != ix0 ) { 
  ix1++
  if( ix1 != ix0 ) {
    ix2++
  }
}

Implementing the Less Than Operator

Another challenging operation to implement with the Z-Machine is the comparison operator. Suppose that an operator places two numbers into the first two memory positions of the Z-Machine. That is, index 0 contains a number A, and index 1 contains a number B. Supposing these numbers are both natural numbers (either 0 or positive integers), a comparison operator will compare the two numbers, select the smaller (or larger) of the two numbers, and place it into the third position in memory (index 2).

We'll cover how to select the smaller of the two numbers and put it into the third slot in memory.

The pseudocode approach to implement the comparison operator is to create a counter that start at zero, and check if it is equal to A or B (the numbers at index 0 and index 1). If we continue to increment our counter, and check if it is equal to A or B, and stop when it reaches either A or B, we can guarantee that we will stop when the counter reaches the smaller of the two numbers.

Z-Machine Code

In order to increment the memory cell at index 2 to hold the smaller of the two numbers at index 0 and index 1, we can use the following Z-Machine code, which continually checks if the number at index 2 is equal to either the number at index 0 or the number at index 1, increments if false, and stops when true (when it reaches the smaller of the two).

001		Z2 // smaller of the two numbers
002		Z3 // zero
003		Z4 // one 
004		I4 

005		J0,2 --> 007
006		J3,4 --> 011
007		J1,2 --> 009
008		J3,4 --> 011
009		I2
010		J3,4 --> 005
011		Z4

Note that this code can successfully handle the case of either number (or both) being 0 or any other positive integer.

Z-Machine Comparison Operator Pseudocode

Here is the pseudocode for the greater than operator:

// The operator begins by setting ix0 and ix1 to the two numbers to be compared.
// The smaller of the two numbers will be placed into ix2
ix2 = 0
zero = 0
one = 0
one++

// check if ix2 is the first number
if neq(ix0, ix2) --> jump to if neq(ix1, ix2)
if neq(zero,one) --> finished, ix0 is the smaller number, jump to cleanup
if neq(ix1, ix2) --> jump to increment ix2
if neq(zero, one) --> finished, ix1 is the smaller number, jump to cleanup
ix2++
if neq(zero,one) --> jump to top, if neq(ix0, ix2)
clean up