In Sipser's text, when proving that there exists an oracle $A$ such that $P^A \ne NP^A$, he writes:

Let $M_1, M_2, \ldots$ be a list of all polynomial time oracle TMs.

I understand that there are countably many Turing machines, but aren't there uncountably many oracles?


2 Answers 2


There are $2^{\aleph_0}$ possible oracles, but when fixing an oracle $A\subseteq \Sigma^*$, there are only countably many Turing machines $M^A$ with access to the oracle $A$.

Remember that a Turing machine with access to some oracle is defined in the same manner as a normal Turing machine, but with an additional operation (they can query the oracle). They have a special tape on which they can write a query, and say, three additional special states $q_{ask},q_{yes},q_{no}$. Upon entering $q_{ask}$, if $s\in\Sigma^*$ is the content of the query tape, the machine enters either $q_{yes}/q_{no}$, depending on whether or not $s\in A$.

Nothing stops us from encoding such machines as strings, in the same way we encode regular Turing machines, hence we only have countably many such machines.

  • $\begingroup$ Are you saying that "Let $M_1$,$M_2$,… be a list of all polynomial time oracle TMs." means: fix an oracle $A$ and consider all TMs that have $A$ as an oracle? I was reading this as "consider all TMs with all possible oracles"... $\endgroup$
    – theQman
    Dec 20, 2016 at 15:10
  • $\begingroup$ First option (otherwise as you said, you have uncountably many). $\endgroup$
    – Ariel
    Dec 20, 2016 at 15:12

There are uncountably many oracles. ​ However, those are sold separately:
The oracle Turing machine only comes with an interface for
interacting with whatever oracle one might choose to use it with.


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.