[Solved]: How a reduction can help up solve a problem?

ignougroup
Problem Detail: I am studying the basics of Computation Theory and I came up with an example I can’t understand. Let’s have a language $L = {langle Mrangle mid L(M) = Sigma^{ast} }$, so $L$ contains codes of all Turing machines which generate all the words from $Sigma^{ast}$. It’s been said that we can reduce $H$ (the halting problem) to $L$, so $H leq_m L$. A mapping $f(langle M, xrangle) = langle Nrangle$ was defined, where $N$ is a Turing machine coded as shown below: 

N(y):     if (M(x) accepts):         accept     reject

Now my problem is: I thought that if $H leq_m L$ then if we could solve $L$, we would be able to solve $H$ as well. By this I supposed that if we have a TM deciding on language $L$, we would be able to build a TM deciding on language $H$. But as for me, the machine above does not help me solve $H$ at all. It acually looks like if we could solve $H$, then we could solve $L$, but I can only see the machine above generate $Sigma^{ast}$, but not decide on it. If any of my intuition is correct, a Turing machine $M_L$ deciding on $L$ would work like: take the code of another Turing machine $M_A$ and accept if $M_A$ generates all words from $Sigma^{ast}$ or reject when $M_A$ does not generate all words from $Sigma^{ast}$. How would this machine help me build a Turing machine deciding on the Halting problem?

Asked By : 3yakuya

Answered By : Luke Mathieson

This is a natural trap that almost everyone falls into when encountering this style of reduction for the first time – you have your logic inverted, but in an understandable way. To start with, note a couple of things:

  1. If $N$ accepts at least one string, it accepts every string, so $L(N)$ is either $emptyset$ or $Sigma^{ast}$, nothing in between.
  2. $langle N rangle$ is an encoding of a Turing Machine, and what we want to know is whether we can decide if $langle N rangle$ is in $L$ or not.

So the argument is by contradiction. Imagine that we did have a TM $X$ that decided $L$, then we could give it $langle N rangle$ and, as it decides $L$, it would say, correctly, $mathrm{Yes}$ or $mathrm{No}$. But if it says $mathrm{Yes}$, then we know that $M$ halts on $x$, because that’s how we built $N$, and similarly if it answers $mathrm{No}$, $M$ doesn’t halt on $x$. So having $X$ (i.e. being able to decide $L$) allows us to decide the Halting Problem, and hence we have a contradiction. Note that we’re not trying to ‘run’ $N$, we’re asking if there can possibly be an $X$ that looks at $langle Nrangle$ and says something about it (for every $N$).

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/35136  Ask a Question  Download Related Notes/Documents