0
$\begingroup$

Assume that a language A is reducible to language B. The claim is true?

if A is decidable then B is decidable too.

The correct answer is:

This claim is wrong. If A is e.g. the empty language (which is clearly decidable) and B is $A_{TM}$, then surely ∅ is reducible to $A_{TM}$, but $A_{TM}$ is undecidable. The claim is true the other way round: If B is decidable then A is decidable too.

I have problem to understand two points:

  1. A is e.g. the empty language (which is clearly decidable)

Why empty language is ("clearly") decidable and $L_∅$ is not?, where, $$L_\emptyset = \{\langle M\rangle \mid M \text{ is a Turing Machine and }L(M)=\emptyset\}.$$

  1. **A is reducible to $A_{TM}$ **

I have difficulties to image a reduction from $∅$ to $A_{TM}$, where $A_{TM} = \{<M,w> | \ M \ is \ a \ TM \ and \ M \ accepts \ w\}$

| cite | improve this question | |
$\endgroup$
  • $\begingroup$ In which relation are A and B? What is ATM? $\endgroup$ – Daniel Dec 26 '19 at 17:34
  • $\begingroup$ language A is reducible to language B. Added on the question. Thanks. $\endgroup$ – Gianni Spear Dec 26 '19 at 17:37
1
$\begingroup$
  1. By definition, a language $L$ is decidable if there exists a TM $M\mid L = L(M)$ deciding it. Consider a TM that rejects on all inputs (for example, one where $q_o = q_{\text{rej}}$). The language of this TM is $\emptyset$, so $L=\emptyset$ is decidable.
  2. With reductions, in general if $A\leq B$ ($A$ reduces to $B$), then $B$ is at least as hard as $A$ with respect to decidability. An undecidable language $A_{TM}$, regardless of what it actually is, is harder to decide than the decidable language $\emptyset$ by definition. The specifics of the reduction don't matter; the only information we needed was given in the problem statement (that $A$ is reducible to $B$).
| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ I don't think the empty language is a good example for the answer because there is not reduction from the empty language to an another language. $\endgroup$ – Gianni Spear Dec 26 '19 at 18:17
  • 1
    $\begingroup$ By Turing reductions specifically, the empty language can be reduced to other languages. Let $M_B$ be the decider for $B$; then the reduction from $A = \emptyset$ to $B$ could just be "def $M_A\langle x\rangle$: run $M_B\langle x\rangle$, then reject." $\endgroup$ – elucidium Dec 26 '19 at 18:33
  • $\begingroup$ @GianniSpear That's not correct (and this answer is right). As elucidium says, it's easy to whip up a Turing reduction from $\emptyset$ to $A$ by ignoring the oracle $A$ completely. We can build even stronger reductions too. For example, we have $\emptyset\le_mA$ for any $A$ (where $\le_m$ refers to many-one reducibility): if $A=\emptyset$ we just use the identity function, and if $A\not=\emptyset$ we pick some $n\in A$ and use the constant function $x\mapsto A$. It's only when we consider $1$-reductions that things break down. $\endgroup$ – Noah Schweber Dec 26 '19 at 19:31
  • $\begingroup$ (FWIW it's still the case that $\emptyset\le_1A$ whenever the complement of $A$ has an infinite computable subset - and $A_{TM}$ fits this criterion via the Padding Lemma. So in fact $\emptyset\le_1A_{TM}$, which is about as strong a fact as you could hope for.) $\endgroup$ – Noah Schweber Dec 26 '19 at 19:34
1
$\begingroup$

Elucidium addresses most of your question; let me address the remaining point, which is why $\emptyset$ and $L_\emptyset$ behave differently.

The point is that they're simply very different sets in the first place. For example, $\emptyset$ has no elements - that's its definition - while $L_\emptyset$ is infinite (there are lots of Turing machines which don't do anything). Just because something is related to $\emptyset$ doesn't mean it behaves like $\emptyset$.

| cite | improve this answer | |
$\endgroup$

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.