Theory of Computation - Turing reducibility

An oracle for a language B is an external device that is capable of reporting whether any string w is a member of B.

  An oracle Turing machine (OTM) is a modified Turing machine that has the additional capability of querying an oracle.

Example: Construct an OTM  with an oracle for ATM that decides ATM

O = “On input <M,w>, where M is a TM and w is a string:

         

Language A is decidable relative to language B iff there is an OTM

with an oracle for B that decides A.

Language A is Turing reducible to language B, written A£TB,  iff

A is decidable relative to B.  

Theorem 6.21:

      a)  If  A£TB  and  B  is decidable,  then  A  is decidable.

Consequently,

      b)  If  A£TB  and  A  is undecidable,  then  B  is undecidable.

Proof (a): If B is decidable, then we may replace the oracle for B by

an actual procedure that decides B. Thus we may replace the OTM

that decides A relative to B by an ordinary TM that decides A.