First page Back Continue Last page Overview Text


The important issue in the proof is how to enforce the standard logic for how a TM advances in time. The flight sequence must correctly simulate the TM.

Start by considering a single TM transition. The tape away from the head does not change. The cell the head is over may change contents, the state may change, and the head may move left or right one cell. Thus, all change takes place in a window of 3 cells centered on the head, and within these cells only a small finite number of before and after configurations are possible. Therefore the set of permitted transitions can be encoded using a non-deterministic finite-state transducer (FST) that uses (0:0|1:1)* to account for most of the tape and a small set of triples L:A Q:B R:C to encode the changes near the head. From the start of the diagram, we see that one triple is $:$ GREEN0:1 0:GREEN0.

We can change the representation so that the before-and-after contents of each cell are interleaved, as in the lower diagram. There the gray cells represent the tape at the current time step, and the white cells the tape at the next time step. Then a single row reflects one transition, and the consistency of that transition can be enforced by a non-deterministic finite-state machine (FSM): where the FST had X:Y, the FSM has XY. Therefore the initial flight sequence becomes TA1000 TA1000 GA2000 TA3000 TA2000 GA2000.