First page Back Continue Last page Overview Graphics
Turing Machine Simulations
Actually write code to translate programs into industry-standard fares and rules
Run on ITA Software’s production servers with unmodified code
What can we handle in practice?
- Non-deterministic Turing Machines
- Search all inputs at once
- With production code settings
- Max tape length with 0/1 alphabet ~20
- Max execution steps ~20
- Max ~10 states
- Takes about 1 second to run
- Thus, e.g, small problems in NP
- Standard Shannon/Minsky alphabet/state tradeoff theorems apply
Notes:
Turing Machines can be encoded as in the EXPSPACE proof, but that doesn't mean a travel planning search engine will be able to run them! Every search engine has limitations, and given the computational complexity of the planning problem it is difficult to imagine very large simulations succeeding. In the case of ITA Software's engine as of early 2003, it is possible to simulate TMs with small numbers of states for between 10 and 20 steps on tapes of length from 10 to 20 (depending on the specific TM and tape alphabet). Fundamentally, ITA Software's engine will not generally duplicate airports for a user-requested portion of a trip, which limits the size of the tape and number of time steps to a polynomial in the size of the databases. The net effect is that ITA Software's engine can execute non-deterministic TMs over small tapes for small numbers of steps, or in other words, that it can solve small instances of problems in NP - as one would expect.
After the databases have been constructed, the machine is run by posing a query with one trip segment per time step, between made-up airports. For example, to run for 3 time steps one poses a query “find solutions from XXA to XXB, then from XXB to XXC, then from XXC back to XXA”. The flights in each trip segment encode the tape at that time step as well as the transition to the next time step.