I am currently taking a class in complexity theory and I am struggling with this question.

We define a TM with Oracle per. Sipser 6.18 as:

"An oracle for language $B$ is an external device that is capable of reporting whether any string $w$ is a member of $B$. An oracle Turing machine is a modified Turing machine that has the additional capability of querying an oracle. We write $M^b$ to describe an oracle Turing machine that has an oracle for language B."

I think that the answer is potentially false. We know that the set of languages is uncountable and suppose we had a Oracle Turing machine that accepts if the oracle answers YES, reject otherwise. Wouldn't that mean that then the set of languages recognized by TM with an oracle be uncountable?

  • 1
    $\begingroup$ Yes, it depends on what the set of potential oracles is. $\endgroup$ – Raphael Nov 17 '17 at 6:38
  • $\begingroup$ duplicate $\endgroup$ – Ariel Nov 17 '17 at 8:37

Every language can be accepted by a Turing machine with an appropriate oracle, for example an oracle for the very language you want to accept. So if you understand "languages recognized by a Turing machine with an oracle" in this way, then certainly their number is uncountable.

Another way to understand this phrase is the you fix the oracle and then ask how many languages are recognized by a Turing machine with access to this specific oracle. In this case the number of languages is countable, since there are countably many ways to specify a Turing machine.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.