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)?
2
$\begingroup$
$\endgroup$
-
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
6
$\begingroup$
$\endgroup$
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.
