Suppose that I have got an oracle to some undecidable decision problem, say, for some language $L$.

Examples include

  • Halting problem
  • group isomorphism problem
  • whether a Turing machine is a busy beaver champion
  • and many others...

Is there an understanding that access to an oracle for some undecidable problem provides different powers?

The situation is analogous to logic and axiomatic set theory: there are undecidable statements, such as the axiom of choice or the continuum hypothesis. We can choose any of them as an additional axiom. But it is known that different such new axioms have different power. For example, the generalized continuum hypothesis implies the axiom of choice.

I am wonder whether similar "power implications" exist for oracles of undecidable problems.

  • 5
    $\begingroup$ This is called Turing Degree: en.wikipedia.org/wiki/Turing_degree This is not really a research-level question as it is very well-known and part of the classical curriculum $\endgroup$
    – Denis
    Commented Jun 5 at 8:12
  • $\begingroup$ I disagree that this is part of a classical curriculum in theoretical CS. $\endgroup$
    – shuhalo
    Commented Jun 6 at 21:50


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.