are there systems whose nontrivial properties can't be decided by Turing machines, but for which a Turing machine with an oracle able to find out these properties isn't able to solve the Halting problem (for ordinary TMs)?

  • 3
    $\begingroup$ I think this question is not research-level. Voting to close as off-topic. $\endgroup$ – Kaveh Jan 24 '11 at 17:21
  • 1
    $\begingroup$ I think this is an okay question, although the wording is a little confusing. $\endgroup$ – Huck Bennett Jan 25 '11 at 5:58

Yes, there are intermediate degrees. One way to see this is that there are computably enumerable sets that are Turing incomparable. See https://secure.wikimedia.org/wikipedia/en/wiki/Turing_degree for some basic information.


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.