How a reduction can help up solve a problem?

Question

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 M\rangle \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, x\rangle) = \langle N\rangle$ 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?

Answer 1

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 N\rangle$ and says something about it (for every $N$).