First page Back Continue Last page Overview Graphics
Right to Left Increment
Right-to-left boolean increment-by-1 machine is 2-state DTM (DFST)
Left-to-right boolean increment-by-1 machine is 2-state NTM (NFST)
Set prices of “1” fares to reflect bit position
- 1.00$*2i input tape, 0.01$*2i output tape
Notes:
As a first example, a left-to-right binary increment program is encoded. Incrementing a binary number from right (least significant bit) to left (most significant bit) is a simple deterministic operation that only involves moving the head to the left and maintaining the carry bit in the state. Working from left to right essentially reverses the machine's transitions, which requires non-determinism. The machine must guess whether the remaining low bits will carry to know whether to flip the bit under the head.
To simplify interpretation of results, the encoding of the TM assigns values to fares in such a way that the input and output values represented in binary appear as the dollar and cents portion of the trip cost. This is done by giving a price to the “1” fares used for the first segment of the trip a value in dollars proportional to 2i where i is the distance from the right end of the tape, and similarly in cents to the “1” fares used for the last segment of the trip. Thus, solutions should have values $0.01, $1.02, $2.03, et cetera.