## 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

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.