Oracle Turing Machine

@oracle @turing_machine

The oracle Turing machine is a theoretical construct that is useful for expressing how powerful a machine would have to be in order to solve problems in some complexity class in polynomial time.

A Turing Machine decides on a language (or alternatively, a problem encoding in that language) if it performs instructions from an input string and ends in an accepting state if and only if the input is correct. Because of this decision-character, Turing machines are useful for reasoning about the complexity of problems (relation of maximum computation steps as a function of the input size).

The Oracle Turing Machine is an extension to the regular Turing Machine because it has, in addition to its regular tape, an oracle tape that behaves as described below.

Johan Kwisthout , Artificial Intelligence Volume 218, January 2015, Pages 56-73:

Oracle Turing Machine (OTM) is a Turing Machine enhanced with a so-called oracle tape and an oracle O for deciding membership queries for a particular language $L_{O}$. Apart from its usual operations, the OTM can write a string y on the oracle tape and ‘summon the oracle’. In the next state, the OTM will have either replaced the string with 1 if $y \in L_{O}$ , or 0 if $y \notin L_{O}$. The oracle can thus be seen as a ‘black box’ that answers membership queries in constant time. Note that both accepting and rejecting answers of the oracle can be used. (7-8)

W.r.t. the last remark, recall that the NP class is only defined on yes-instances of decision problems.

A proof of membership (for NP-problems) is called a certificate (has to be polynomially bounded to the input size).

Such a machine is called an oracle because it is assumed to have access to an oracle for problems in some class, that is, that machine can query the oracle and receive answer in constant O(1) time. Obviously, such a machine does not exist, but is a theoretical construct that is useful for reasoning about complexity classes.

Oracles are used to define various complexity classes e.g. $NP^{PP}$ which is "the class of problems which are verifiable in polynomial time on a machine that has access to an oracle deciding problems in PP" (p.40, Kwisthout TFCA lecture notes). So the "PP" superscript indicates the oracle access.

Because these classes make use of the oracle, computations in PP are assumed to be "for free", in O(1).