EXTENSION

The most useful extension to the parity counter design would allow tapes longer than sixteen bits to be processed. The device that would allow this extension is a Turing Tape Transport. Such a device is shown in Figure TUR-5 and is a close approximation to an actual drive known as an incremental tape drive. With a tape device such as this each character of the alphabet 0, 1, and B may be represented (assume two bits represent a character as 0 = 00, 1 = 01 and B = 10 or 11). In fact most tapes are 7 or 9 bits wide which would allow alphabets with 2^7 and 2^9 characters respectively. Design a controller for the Turing Tape Transport to compute parity using the quintuple of Figure TUR-2.

ADDITIONAL PROBLEMS

1. Design a Turing machine which computes parity without erasing the tape.

2. Design a Turing machine which adds one to a binary number stored on the tape and leaves the result on the tape. The read head will be placed under the least significant bit of the word initially and the termination symbol, B, will mark the left end of the word.

3. Design a Turing machine which adds two binary numbers together. Assume that special characters delimit the numbers on the tape (i.e. increase the alphabet).

4. The parity counter essentially had its quintuples hardwired in the design. Design a Turing machine simulator that operates from quintuples stored in a memory array, i.e., this machine should operate for any set of quintuples. The major issue here is the representation of the quintuples and the method of table lookup to determine the appropriate action for each current state - symbol read pair. Such a machine resembles K(PCS), described in Chapter 2.