Turing Trains i Logo Wang Tiles Maze Array

# Turing Trains

## 2's Complement

Two's complement is a method of representing negative binary numbers. It allows arithmetic operations to work correctly with negative values, in a similar manner as positive numbers. The MSB (most significant bit) of each register is reserved to hold the sign of the number. A 0 denotes a positive value, so positive values remain unchanged. A leading 1 denotes a negative value.

Normally, a 3 bit binary number ranges from 0 (000) to 7 (111). With 2's complement the range is from plus 3 (011) to minus 3 (101).

Note that binary zero (all 0's) has a single representation.

Applying the 2's complement function a second time reverts back to the original number.

 Dec Binary Dec 2's Comp 0 1 2 3 4 5 6 7 000 001 010 011 100 101 110 111 +3 +2 +1  0 -1 -2 -3 011 010 001 000 111 110 101

Both these layouts calculate the value of A minus B using the 2's complement method of invert and add 1. The result is held in register B, so the original value of B is 'lost'. Three functions are used:

1. Inverter function, to invert B.
2. Incrementor function, to increment (add 1) to B.
3. Accumulator function, to add A to B.

### Operation

Enter the values of A and B and start the train from the station. When the train halts, the result can be read from register B.                               Click layout to pause/run train Click points to switch 0/1 Click start circle to reset train/points Lazy points switch between upper 0 or lower 1 branch lines Trains arriving on a branch line switch the point to that line Sprung points allow branch line trains to join the main line All main line trains go straight ahead and never 'branch off'

### How it works

The lower Inverter and Incrementor functions calculate the 2's complement of B. The Inverter uses compact flip-flops. The Adder then adds the value of A to B.

This second layout is more compact as the Incrementor is not needed. Instead, a 'first return' latch ensures the train returns to the Adder to add the final 1. The operation is the same as the layout above.                    Click layout to pause/run train Click points to switch 0/1 Click start circle to reset train/points Lazy points switch between upper 0 or lower 1 branch lines Trains arriving on a branch line switch the point to that line Sprung points allow branch line trains to join the main line All main line trains go straight ahead and never 'branch off'

### How it works

From the station, the train enters the Inverter function which inverts the value of B. It then passes up to the Adder, resetting the 'first return' latch to 0 on the way. Therefore there is no need to reset this latch before each new calculation.
The Accumulator function adds A to B. As the train returns, it uses the top set of latches to set A to 1. The 'first return' latch returns the train to the Adder, so that the 1 is added to B.
On its second visit, the 'first return' latch lets the train pass through, so the train returns to the 'Halt' siding to end the calculation.

### Note

1. The 2's complement method only works when all registers are of the same size. Add and Incrementor overflows are simply 'lost', so there are no overflow error lines.
2. If B is greater than A, then the result of A-B is negative, and is read as a 2's complement value.
 Turing Trains | cr31.co.uk | 2019
 zoom in to enlarge layouts