I want to find two undecidable languages $A$ and $B$ that $A$ cannot reduce to $B$, $B$ cannot reduce to $A$(Many-one reduce). One of my thought is to let $A$ be the halting problem, let $B$ be some non-Turing-recognizable language, then it is clear that $B$ cannot reduce to $A$, but I don't know which $B$ can I pick to show that $A$ cannot reduce to $B$

  • $\begingroup$ Try the halting problem and its complement. $\endgroup$ – Yuval Filmus Nov 21 '19 at 22:51
  • 1
    $\begingroup$ @YuvalFilmus but how can we prove that halting problem cannot reduce to its complement? $\endgroup$ – Joe Nov 21 '19 at 23:26
  • $\begingroup$ That’s a different question. $\endgroup$ – Yuval Filmus Nov 21 '19 at 23:27
  • 1
    $\begingroup$ @YuvalFilmus But if I remember correctly, there is indeed a Turing reduction from halting problem to its complement... $\endgroup$ – Joe Nov 21 '19 at 23:29
  • 1
    $\begingroup$ @YuvalFilmus okay.. But it is Turing reduction in context $\endgroup$ – Joe Nov 21 '19 at 23:31

There is no known natural example of such a pair, and indeed there are various results in computability theory suggesting that such a pair does not exist. So to whip up an example one has to do some work.

The simplest approach (indeed, the easiest I know) is via mutual diagonalization: we build inductively a pair of increasing sequences of infinite binary strings $$\sigma_0\prec\sigma_1\prec\sigma_2\prec ...\quad\mbox{and}\quad \tau_0\prec\tau_1\prec\tau_2\prec ...$$ such that for each $i$ there do not exist infinite binary sequences $f,g$ extending $\sigma_i,\tau_i$ respectively such that $\Phi_i^f=g$ or $\Phi_i^g=f$.

  • Proving that such sequences in fact exist is a good exercise.

Taking $$a=\bigcup\sigma_i,\quad b=\bigcup\tau_i$$ we then have that $a$ and $b$ are Turing-incomparable. (Thinking about this construction a bit, we can in fact ensure that $a,b$ are $\le_T{\bf 0'}$.)

A better result is that there are computably enumerable sets which are Turing incomparable (the Friedberg-Muchnik theorem). This is much harder to prove, however; it was the first example of a priority argument.

Yuval Filmus commented that a pair of "random" languages should probably work. There are multiple senses in which this is true - in particular, the set of pairs of infinite binary sequences which are Turing incomparable is both comeager and of full measure in the space of all pairs of infinite binary strings (with the usual topology and measure). The former observation is basically just the mutual diagonalization argument above, slightly tweaked; the latter is a bit harder to prove. (In general, in computability theory measure is more complicated than category.)

  • In fact, the proofs of the observations in the previous paragraph actually yield stronger results without significant changes: namely, we get that for every noncomputable infinite binary sequence $f$ the set of infinite binary sequences Turing-incomparable with $f$ is both comeager and of full measure in the space of all infinite binary sequences.
| cite | improve this answer | |
  • $\begingroup$ Thank for such a detailed answer. However, this may seem a bit too complicated for me... I am just an undergrad who start to learn Turing Machine recently. This is just a class exercise so I would not expect the answer to be that hard. Maybe I state the question unclear $\endgroup$ – Joe Nov 22 '19 at 0:46
  • $\begingroup$ The question asks for Two non Turing decidable language A and B such that A cannot be Turing reduces to B, B cannot be Turing reduced to A. We are given hint that we can choose one of the language to be the halting problem $\endgroup$ – Joe Nov 22 '19 at 0:48
  • $\begingroup$ @Joe Are you sure it is Turing reductions that are being looked for? If so, I think your instructor made a mistake (or this is a challenge problem) - it genuinely is this hard. $\endgroup$ – Noah Schweber Nov 22 '19 at 0:49
  • $\begingroup$ Sorry, I did not notice that our professor said it should be many-one reduction $\endgroup$ – Joe Nov 22 '19 at 1:36
  • $\begingroup$ @Joe In that case Yuval Filmus' suggestion works - if a c.e. (respectively, co-c.e.) set is m-reducible to a co-c.e. (resp., c.e.) set, then it is computable (this is a good exercise). Since the halting problem is c.e., its complement is co-c.e., and neither is computable, this tells us that the halting problem and its complement are many-one incomparable. $\endgroup$ – Noah Schweber Nov 22 '19 at 2:12

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.