First page Back Continue Last page Overview Graphics

Incrementer Results

Notes:

This slide graphically depicts three of the solutions the search engine found running on a 6-cell tape. Dark gray flights are 1s, light gray are 0s. The labels in cells are the airline (T0 Airlines represents a cell with a 0 in it, T1 Airlines represents a cell with a 1 in it, N0 indicates a cell with a zero that the head is over, in state N, et cetera). Colored cells indicate the tape head, the green state for “carry” and the blue for “no carry”. Orange flights at start and end delimit the tape. Long morning flights encode the current tape, short evening flights the tape at the next time step. Thus, short flights are identically colored to the long flight diagonally below and to the left – 6 days later. When the machine enters a halt state the state disappears from the tape; hence the last row of each solution has no colored state cells. Notice the non-determinism of the machine: in some cases when in the blue no-carry state over a 0 cell, it increments the cell to 1, in some cases it does not: it guesses the next carry (whether the remaining cells to the right are all ones). No solutions result from wrong guesses, because every guess gets verified as the machine scans further right.

Note the complexity of these trips: 98 flights, 98 fares, 36 round-trip PUs, 26 one-way PUs!