2
$\begingroup$

The notions of a low and high sets were introduced, I think by Soare, in the context of the dense structure of degrees of those sets which are neither r.e. neither recursive. My question is:

Why are all examples of "natural" decision problems (the spectral gap problem for example) reducible to the halting language and none are low or high?

Improve this question
$\endgroup$
2
  • $\begingroup$ Can you find a natural decision problem reducible to the halting language and neither Turing complete nor recursive? $\endgroup$
    – 喻 良
    May 15, 2022 at 2:43
  • $\begingroup$ @喻良 I don't think I could $\endgroup$
    – H.C Manu
    May 16, 2022 at 8:04

0

Reset to default

Your Answer

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

Browse other questions tagged or ask your own question.