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

  • 2
    $\begingroup$ Every problem can trivially be solved by an oracle to itself. So in order for the question to be interesting, you need to put constraints on the oracle. Perhaps you should read about the Arithmetical Hierarchy, as a starting point. $\endgroup$ – Shaull Aug 4 '13 at 13:50
  • $\begingroup$ Check Turing degrees. $\endgroup$ – Sasho Nikolov Aug 4 '13 at 15:23

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.

  • 2
    $\begingroup$ Yuval I think your definition of Turing degree is not quite right: it's a set of Turing equivalent problems. $\endgroup$ – Sasho Nikolov Aug 5 '13 at 4:49
  • $\begingroup$ @Sasho Thanks, corrected. Is there a proper name for "Turing semi-degree"? $\endgroup$ – Yuval Filmus Aug 5 '13 at 4:57
  • $\begingroup$ not sure, but what you wrote makes sense! $\endgroup$ – Sasho Nikolov Aug 5 '13 at 5:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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