ABSTRACT
You are having trouble solving a mathematics problem and enter your department looking for help. You knock on Professor A’s office door. There is no reply. You wait. Unfortunately Professor A has had an accident while working in his garden, and will never again be coming to work. You wait forever. Your mathematics problem remains unsolved . . . A realistic scenario? Of course not — nobody behaves that stupidly —
there is something wrong here with the oracle Turing machine model. In real life, having got no help from Professor A, you move on to Professor B’s office, and if she is not there — you try Professor C. Professor C, always helpful and knowledgeable, gives you just the information you need, and you happily complete your project. In this chapter we learn how to model computability relative to sources of
auxiliary information that are not always responsive. The model we come up with will involve nondeterministic computations — mirroring the guessing at Professors A, B and C. There will also be important applications to situations in which the oracles do always answer-or where there is even no oracle used — but where there are time constraints which make us guess at optimal routes to successfully terminating computations. The extent to which this guessing actually helps in this context is a famous — and as yet unsolved — problem.
