Oracle machine
An oracle machine is a program or machine which has access to an oracle. The oracle is a connected machine or available function/command which can be invoked with arguments. Oracles are primarily used in the context of decision problems, where the oracle can answer if a particular question is in the YES set, in which case it shows a proof, or if the answer is in the NO set. Oracles do not have general properties other than that they perform some (potentially magical) decision on whether or not an example satisfies some condition. Different ways of modeling oracles have different implications for the computational class of the overall oracle machine. The most popular oracles are ones which solve the halting problem, and ones which solve NP complete problems (such as SAT).
Oracle machines can be modeled in many different ways. The magical oracle can be separated from the overall machine and viewed as being able to access some part of the machine to take input and give its answer. One model for Turing machines with an oracle is that the overall machine has two tapes, one for the Turing machine and one for the oracle. The Turing machine writes its question onto the oracle tape, then the head enters a special ask state which invokes the oracle. After the oracle finishes it writes its answer onto its tape and transitions the head to an answered state. Another model has the oracle simply write a yes/no answer (or transition to a yes answered state or a no answered state). Yet another uses a single taped Turing machine.
Computational class of machines with a halting oracle
Machines equipped with a halting oracle are typically uncomputable. This is not always true, however. It depends on the definition of the oracle. This section concerns itself with Turing machine halting oracles, oracles which decide if a Turing machine halts or not.
An oracle with a tape: if the oracle is modeled with its own tape, then an FSM with such an oracle is Turing complete and uncomputable. For completeness, the FSM can simply use the tape for data storage while ignoring the oracle. Since an FSM with a tape is exactly what a Turing machine is, this model is complete. It is also uncomputable, since the FSM can accept any Turing machine as input and write it to the oracle tape, then ask if it halts or not.
An important concept to grasp for the rest of this section is the idea that halting oracles can evaluate any yes/no problem about a Turing machine with input in finite time. Of course, they can answer if it halts or not, but it can also answer if the machine returns true or false. A machine which returns one of two answers, either true or false, is equivalent in behavior to one which (at the end of computation) enters a specific loop on true, otherwise halting. The return value of the machine can be determined by a Turing machine, the simulating machine can simply check if the inner machine has started the loop and halt. With this construction the oracle can also determine what the machine's answer is, if the halting oracle says that the machine does not halt the output was true, otherwise it was false. Since a Turing machine can reach any cell of its tape and perform this conditional infinite looping, the Turing machine description can be modified such that it seeks to a particular cell before performing this infinite looping. This modification and evaluation can be done arbitrarily many times, allowing for a machine with an oracle to read off the output of the machine with time complexity proportional to the output size, regardless of the time complexity of the machine being queried. This construction is interesting because it means a time bounded Turing machine with an oracle is still Turing complete, for some suitable bounding function.
Todo: provide better explanations for these
A bounded Turing machine (FSM) with an oracle: can answer arbitrary but particular (the description must be encoded in the machine, or bounded by a constant) computable problems which have constant bounded outputs (since the seek code in the TM description must be bounded by a constant). Computable. (the description of the TM is constant bounded, so a general halting solver is not necessary)
A linear bounded automaton with an oracle: can answer any (any encoded TM can fit in a linear bounded encoding) computable problem which has an output size that is a linear function of its input (since the seek code in the TM description must be bounded by a linear function). Uncomputable. (the TM description is linearly bounded, allowing for any TM to be used, thus requiring a general solution)
A pushdown automaton with an oracle: can answer any computable problem (the stack can store arbitrarily large indices). Uncomputable.
A Turing machine with an oracle: trivially Turing complete and uncomputable. This is equivalent to the FSM with an oracle that has its own tape, just the tape has a different "owner."
Examples
Halting oracles
- Oracle the oracle in this language not only solves the Turing machine halting problem, but also the halting problem for itself