# Can a collection of oracle machines decide every language?

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?

• 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$.

• Oracle machines are supposed to be able to answer any problem posed to them. How can they not be able to solve a halting problem that involves them? – Melab Mar 17 '18 at 2:42
• An oracle for a language $L$ answers questions of the form "$x\in L$?". That's all it can do. – Yuval Filmus Mar 17 '18 at 4:52
• I don't understand. Why is that part of the definition? – Melab Mar 18 '18 at 13:58
• This is the definition. – Yuval Filmus Mar 18 '18 at 15:52

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.