# Countably many oracle Turing machines?

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?

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$.
• 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"... – theQman Dec 20 '16 at 15:10