3
$\begingroup$

I want to find two undecidable languages $A$ and $B$ that $A$ cannot mapping (i.e. many-one) reduce to $B$, $B$ cannot reduce to $A$. 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$

$\endgroup$
9
  • $\begingroup$ Try the halting problem and its complement. $\endgroup$ 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$ 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
6
$\begingroup$

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.

Below, $\Phi_e$ is the $e$th oracle machine according to some standard enumeration (in older texts this is often written "$\{e\}$," which ... yeah).


The simplest approach (indeed, the easiest I know) is via mutual diagonalization: we build inductively a pair of increasing sequences of finite 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 Turing-reducible to the halting problem.)


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.
$\endgroup$
20
  • $\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$ Nov 22 '19 at 0:49
  • 1
    $\begingroup$ @xdavidliu ${\bf 0'}$ is the standard notation for the Turing degree of the halting problem; more generally, see here. I've removed it and defined the $\Phi$-notation, but this is really notation you should familiarize yourself with if you're interested in the topic; Soare is a better source than Sipser here. $\endgroup$ Oct 24 '20 at 20:48
  • 1
    $\begingroup$ @xdavidliu Exactly what I've written in the next line: that $\gamma\prec \rho$, that is, $\gamma$ is (properly) extended by $\rho$. "$\prec$" is the standard notation for (proper) string/sequence extension. $\endgroup$ Oct 24 '20 at 21:04
0
$\begingroup$

A really simple example is $A_\mathrm{TM}$ (i.e. the language of $\langle M, w \rangle$ where TM $M$ accepts $w$) and its complement $\overline{A_\mathrm{TM}}$.

$A_\mathrm{TM}$ is recognizable but not decidable, while $\overline{A_\mathrm{TM}}$ is not even recognizable (if it were, then $A_\mathrm{TM}$ would be decidable!).

Clearly, $A_\mathrm{TM}$ is not mapping reducible (i.e. not many-one reducible) to its complement, since if it were, then its complement would be recognizable.

$\endgroup$
2
  • 1
    $\begingroup$ Note that Yuval Filmus mentions this in his comment to the OP, and the OP responds by clarifying that they're looking for Turing reducibility. (They then edited the question from Turing reducibility to many-one, after they'd already accepted my answer ... so that's a bit confusing.) $\endgroup$ Oct 25 '20 at 2:05
  • $\begingroup$ I'm guessing the OP had incorrectly assumed when asking the question that the two were the same thing. $\endgroup$
    – xdavidliu
    Oct 25 '20 at 2:11

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.