Consider a Turing machine $T$ with access to an oracle for a proper, nonempty subset of $A_{TM}$, say $L$. That is, $T$ can query this oracle to check whether some string belongs or doesn't belong to $L$. Is it possible to define such an $L$ so that $T$ does not decide $E_{TM}$ (the language of descriptions of Turing machines whose languages are empty)?

Intuitively, it seems the problem is that when the oracle answers "No", $T$ is unable to distinguish whether the string it fed to the oracle to receive this response belongs to $A_{TM} - L$ or $\overline{A_{TM}}$. But this doesn't really prove that $T$ can't decide $E_{TM}$.

  • $\begingroup$ What if $L$ is $A_{TM}$ minus 3 strings? Or minus an infinite recursive subset of it? $T$ in such case is able to decide $A_{TM}$. Knowing that it is a proper non empty subset is quite weak. $\endgroup$ – chi Feb 27 '17 at 18:00
  • $\begingroup$ Would it be possible to define $L \subset A_{TM}$ in such a way that $T$ can't decide $E_{TM}$? $\endgroup$ – NBose35 Feb 27 '17 at 18:08
  • 1
    $\begingroup$ Yes, that's possible for some $L$, e.g. the recursive ones. $\endgroup$ – chi Feb 27 '17 at 18:19

It seems you're working towards the notion of Turing reducibility. For example, adding a nontriviality assumption you're roughly asking here:

Is there a set which is not computable but also does not compute the halting problem?

This is an excellent question, and the answer is far from obvious - but ultimately yes in a very strong sense (although a subsequent follow-up question is still open and generally believed to have a negative answer). These were some of the first serious results in computability theory:

  • Kleene and Post in $1945$ showed that the answer to your question is yes in a strong way: there is in fact some $A$ which is strictly intermediate between the computable sets and the halting problem with respect to Turing reducibility. Their argument also showed that we can find an $A$ which is incomparable with the halting problem with respect to Turing reducibility, so we get a strong affirmative answer.

  • This wasn't the end of the story, though. One year earlier, Post had posed a separate question: is there a computably enumerable set which is noncomputable but does not compute the halting problem? (Such a set would necessarily be strictly weaker than the halting problem as opposed to incomparable.) This was answered affirmatively about ten years later by Friedberg and by Muchnik independently; this required a new idea, the priority argument (although later priority-free proofs were discovered). The priority argument subsequently became one of the most, if not the most, important technique in computability theory, and was rapidly advanced far beyond the point of the Friedberg/Muchnik argument (some relevant results here include Sacks' density theorem and Lachlan's monster theorem).

  • However, the Kleene/Post and Friedberg/Muchnik degrees were all fairly artificial. Their arguments showed that the interval between the computable sets and the halting problem is extremely rich, and subsequent results would point towards them being "maximally" rich in some senses, but did not construct examples of such sets which are interesting on their own. Indeed, it is still the case that every natural Turing degree is basically just an iterate of the Turing jump (basically, something of the same "flavor" as the halting problem itself). The question of whether there is a natural intermediate Turing degree is still wildly open; there are some not-too-implausible candidates, but also results pointing towards a negative answer (and I think almost everybody believes that the answer is negative). Certainly the discover of any natural degree which isn't an iterate of the Turing jump would be one of the most important results in computability theory.

  • $\begingroup$ For, 1945 thats highly impressive. For an amaterur,thats revolutionary. $\endgroup$ – Travis Wells May 12 '20 at 1:47

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.