2
$\begingroup$

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)?

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

1 Answer 1

6
$\begingroup$

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.

$\endgroup$

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.