First page Back Continue Last page Overview Graphics
Multi-step consistency
Now one-step transitions are encoded within a time step by FSM flight graph
To ensure multi-step consistency, need to enforce equality between cells on a diagonal
- Implemented using round-trip priceable-units that enforce same-flight-number restrictions on outbound flight and return flight
- Key issue is ensuring that right cells are paired; implemented using minimum and maximum stay restrictions: min stay = max stay = TAPE-LENGTH * 2 - 1
- EXP-SPACE limit comes from encoding of min/max stay: n bits encodes 2^n length
Notes:
The advantage of encoding single-step transitions within a row is that multi-step consistency is ensured if the “after” portion of one row is identical to the “before” portion of the next, or in other words, if each white “after” cell is encoded using the same airline and flight number as the gray “before” cell that is one down and to the left of it. But this geometric relation is also a linear one: if the TM tape length is T, then each “before” flight must be the same as the “after” flight that occurs 2T-1 days later.
This flight equality restriction can be enforced using round-trip priceable units. The fare database is constructed so that each white cell (in a non-final row) can only be priced using a fare with rules that ensure it is paired in a round-trip priceable unit with another same-flight fare. The rules also have 2T-1 day minimum and maximum stay restrictions, ensuring that exactly the right white and gray cell are paired. Without this restriction the tape could become scrambled from one time step to the next.
These minimum and maximum stay restrictions are the limiting factor in the simulation. It takes n bits to encode a minimum stay of length 2^n, so this construction can “only” simulate a TM with a tape of length exponential in the length of the encoding of the TM. On the other hand, there is no limit to the number of steps the TM can run.