patternMinor
Problems unsolvable by an oracle machine?
Viewed 0 times
machineoracleproblemsunsolvable
Problem
Are there classes of problems that cannot be solved by an oracle machine? If so, are there specific problem examples of that class of problems?
Even the Omega number, at least the first N digits, could be computed as the Oracle could just return TRUE or FALSE for each {0,1}-digits...
Even the Omega number, at least the first N digits, could be computed as the Oracle could just return TRUE or FALSE for each {0,1}-digits...
Solution
Every problem $P$ can be solved with an oracle machine with oracle access to $P$. In order to get a more meaningful answer, we consider the concept of Turing semi-degree, which is the set of all problems computable with an oracle to $P$, for some problem $P$. The same diagonalization argument used to prove that the halting problem isn't decidable shows that no Turing semi-degree encompasses all languages. (Alternatively, there are uncountably many languages but only countable many problems computable with any given oracle.)
A Turing degree consists of the "hardest" problems in a Turing semi-degree. More formally, it is the set of problems equivalent to some problem $P$: problems which are computable given an oracle to $P$, and conversely $P$ can be computed given an oracle to them. The study of Turing degrees consists a significant part of classical recursion theory.
A Turing degree consists of the "hardest" problems in a Turing semi-degree. More formally, it is the set of problems equivalent to some problem $P$: problems which are computable given an oracle to $P$, and conversely $P$ can be computed given an oracle to them. The study of Turing degrees consists a significant part of classical recursion theory.
Context
StackExchange Computer Science Q#13596, answer score: 5
Revisions (0)
No revisions yet.