patternMinor
Can a collection of oracle machines decide every language?
Viewed 0 times
cancollectioneverylanguagedecidemachinesoracle
Problem
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?
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?
Solution
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$.
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$.
Context
StackExchange Computer Science Q#9061, answer score: 5
Revisions (0)
No revisions yet.