Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

If I have a collection of oracle machines, can I decide every language? (I got this question from a former university exam and it sparked my interest).

I thought if my collection has to be countable than I can't decide every language, since there's an uncountable amount of languages.

But if my collection can be of any kind I figured could just add an oracle machine for every language with an oracle for that language, which would be sort of a trivial - brute force approach (the size of the collection would be uncountable than).

Is there an issue with my approach / did I miss something? What happens if I have a countable number of oracles that can be used?

share|cite|improve this question
Your question lives in a landscape where extreme caution on details and formality needs to be taken. First, are you talking about Turing machines? What do you mean by any language, simply $2^{\mathbb{N}}$? What is an oracle? If an oracle can be any $S \in 2^{\mathbb{N}}$, then sure, one machine is needed, for input $x$, ask the oracle. You are also correct in your assumption that countably many oracles isn't enough. – Pål GD Jan 20 '13 at 21:16
@PålGD When I talk about oracle machines I mean indeed Turing machines that have the ability to ask an oracle. I consider all languages to be $P(\Sigma^*)$. I have to say our course is not 100% clear on what the exact nature of an oracle is, so I just assumed any language as defined above. (Am I wrong to assume $2^\mathbb N$ and $P(\Sigma^*)$ are equivalent?) – Samuel Jan 20 '13 at 21:31
Yes, they are equivalent. In recursion theory (computation theory) it is often easiest to consider a language a subset of the natural numbers. So accepting a language $\mathcal{L} \in \wp(\Sigma^*)$ is the same as accepting a set $S \subseteq \mathbb{N}$. Did my previous comment answer your question, by the way? If you allow uncountably many the answer is yes, otherwise the answer is no. – Pål GD Jan 20 '13 at 22:16

This answer assumes that "a collection of oracle machines" means "a sequence of oracles", that is, you have a Turing machine with access to a sequence of oracles.

A sequence of oracles is equivalent to a single oracle: if the original sequence is $O_i$, choose some pairing function $\langle \cdot,\cdot \rangle$ (e.g. $\langle x,y \rangle = 2^x (2y+1)$), and define a single oracle $O$ by $\langle x,y \rangle \in O$ if $y \in O_x$.

It is known that a machine with oracle access to $O$ cannot decide all languages, for reasons of cardinality. We can also exhibit a specific language undecidable by such a machine, namely the halting problem for oracle machines with oracle access to $O$.

share|cite|improve this answer

Yes, if your collection of oracles is $2^{\Sigma^*}$ then every language in $2^{\Sigma^*}$ can be decided by a oracle machine from this class (the language itself): the Turing machine will pass its input to the oracles and will output the oracle's answer.

If the size of the set of oracles is countable the by the cardinality argument there are many languages that cannot be decided by OTMs with oracles from that set.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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