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.