5
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ 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. $\endgroup$
    – John Kemeny
    Commented Jan 20, 2013 at 21:16
  • $\begingroup$ @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?) $\endgroup$
    – Samuel
    Commented Jan 20, 2013 at 21:31
  • $\begingroup$ 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. $\endgroup$
    – John Kemeny
    Commented Jan 20, 2013 at 22:16

2 Answers 2

Reset to default
5
$\begingroup$

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

Improve this answer
$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$
    – Melab
    Commented Mar 17, 2018 at 2:42
  • $\begingroup$ An oracle for a language $L$ answers questions of the form "$x\in L$?". That's all it can do. $\endgroup$
    – Yuval Filmus
    Commented Mar 17, 2018 at 4:52
  • $\begingroup$ I don't understand. Why is that part of the definition? $\endgroup$
    – Melab
    Commented Mar 18, 2018 at 13:58
  • $\begingroup$ This is the definition. $\endgroup$
    – Yuval Filmus
    Commented Mar 18, 2018 at 15:52
3
$\begingroup$

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.

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.