1
$\begingroup$

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?

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

1 Answer 1

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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