# Many to one reductions from undecidable Turing Machine to a decidable language

From what I read, a many-to-one reduction $A \leq_m B$ means that $\forall x \in A$, there exists a computable function $f$ s.t. $f(x) \in B$. However, $f$ is not necessarily surjective (i.e. not all elements in $B$ have to be mapped).

But what if I try to reduce the language $ATM$ : {$(i,w)$ | $TM_i$ accepts $w$} to a well-known computable Turing-decidable language (i.e. $VERTEX-COVER$) using this function $f$:?

Where $f$: On input $(i,w)$, if Turing Machine $i$ accepts $w$, then a Turing Machine $M$ outputs a Graph $g$ that has a 2-vertex cover (any arbitrary graph with a valid 2-node vertex cover), and does otherwise.

In this case, $f$ is computable, and if $(i,w) \in A$, then $f(i,w)$ = $g \in VERTEX-COVER$. Since many-to-one reductions do not have to be surjective, I do not have to map all elements in the vertex-cover set, and yet, $g$ meets the conditions of the many-to-one reduction. There is also no necessary condition for $f$ to have a 'pullback' function $\hat{f}$, where $\hat{f}$ is an 'inverse' that maps all elements in vertex-cover back to $ATM$ since $A \leq_m B$ does $\textbf{not}$ necessarily imply $B \leq_m A$. (the pullback function $\hat{f}$ holds only if $f$ is surjective, which is not necessary in $\leq_m$).

Given the lemma, if $A \leq B$ and $B$ is decidable, then $A$ is decidable. In this case, $VERTEX-COVER$ is decidable, then $ATM$ should be decidable... which is clearly wrong.

There is something obvious that I am missing here ...

• Your understanding of many-one reduction is thoroughly wrong. ​ ​ – user12859 Sep 14 '17 at 3:34
• in the surjective part of many-one reductions? – Link L Sep 14 '17 at 3:47
• No. ​ The initial thing I noticed was that you have the quantifiers in the wrong order. $\hspace{1 in}$ The next thing I noticed ​ (although this change wouldn't matter if you don't also make my next sentence's change) ​ is that you're missing $\;\;\;\;\;\;\;$ "$\;\;\; x\in A \: \iff \;\;\;$" $\;\;\;\;\;\;\;$ before $\;\;\;$ "$\; f(x) \in B\;$" $\;\;\;$ . $\hspace{1 in}$ The last thing I noticed is that your universal quantifier is only over elements of $A$ rather than over elements of ​ $\{\hspace{-0.02 in}0,\hspace{-0.05 in}1\hspace{-0.04 in}\}^{\hspace{-0.02 in}*}$ . $\hspace{2 in}$ – user12859 Sep 14 '17 at 4:15

## 2 Answers

From what I read, a many-to-one reduction $A \leq_m B$ means that $\forall x \in A$, there exists a computable function $f$ s.t. $f(x) \in B$.

No. It's not "for each element $x\in A$ there exists a computable $f$ ...", but "there exists a computable total $f$ s.t. for each $x\in A$ we have $x \in A \iff f(x) \in B$".

Your definition is wrong because:

1. it allows us to pick a different function for each $x\in A$, when we must pick only one;
2. it only states $x\in A \implies f(x)\in B$, when we need the double implication $\iff$;
3. $f$ must be total (maybe this is supposed to be implicit when you don't say "partial", but it's important)

However, $f$ is not necessarily surjective (i.e. not all elements in $B$ have to be mapped).

Correct.

Where $f$: On input $(i,w)$, if Turing Machine $i$ accepts $w$, then a Turing Machine $M$ outputs a Graph $g$ that has a 2-vertex cover (any arbitrary graph with a valid 2-node vertex cover), and does otherwise.

How do you check that TM $i$ accepts $w$? I guess you are simply suggesting to simulate TM $i$. If you do that, there is a possibility of non termination here: precisely, every time $i$ diverges. Hence, $f$ is not total in this case: since its implementation diverges on some inputs.

• But hasn't it been done a lot of times (i.e. Sipser's textbook on Complexity) that instances $(i,w)$ of$ATM$, (where $ATM$ is the set where $TM$ $i$ accepts $w$) are reduced (simulated) to instances of another set such as $HALT_{TM}$ or $REGULAR_{TM}$. Here, they assumed that $x \in ATM$ and that a $TM$'s inherent possibility of looping is not a factor to consider - since the domain is already in $ATM$ and $f$ is meant to halt. – Link L Sep 14 '17 at 9:29
• @LinkL No, it is a possibility to consider IF you actually run that TM. It is not to be considered if given a TM $M$ the function returns another TM $N$, where $N$ simulates $M$ internally. This is a big difference, since in such case the function does not need to run $M$ to produce $N$. You can compare to this: a compiler takes a program as input (say, in C) and produce another program as output (e.g. in assembly). The compiler will halt even if the C program diverges, so that's OK, and can be used for a reduction. If we used an interpreter which actually runs the program, we could diverge. – chi Sep 14 '17 at 10:52
• That makes a lot of sense. – Link L Sep 16 '17 at 1:00

Your function $f$ has to be computable, meaning $f(x)$ must be defined for all $x\in \Sigma^*$, such that $x\in ATM \text{ iff } f(x) \in VC$. But you don't describe how you are going to map $x$ to $VC$, which of course is impossible. In other words you still need to decide if $x\in ATM$ before you map $x$ into $VC$.

• Thanks, but what if a Turing machine M is 'inside' $f$, such that it outputs a valid VC element $g$ iff $(i,w) \in ATM$ ? – Link L Sep 14 '17 at 3:45
• Then ATM would be decidable. But, you know ATM is not decidable and so such TM computing $f$ does not exists. Again, you don't provide a TM computing $f$. So, can't deduce $f$ is computable. – fade2black Sep 14 '17 at 3:50