5
$\begingroup$

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?

$\endgroup$
5
$\begingroup$

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$).

$\endgroup$
  • $\begingroup$ Thank you, that clears quite everything. The last doubt I have is what contradiction do you mean? Do you assume we can't decide H? (I know we can't, at least today, but you did not write it explicitly as your assumption, so I am just trying to get it correctly) $\endgroup$ – 3yakuya Dec 11 '14 at 12:42
  • $\begingroup$ @Byakuya The contradiction is in the assumption that $X$ can decide $L$. $\endgroup$ – Luke Mathieson Dec 11 '14 at 12:44
  • $\begingroup$ So what did it actually proove? What is an assumption that X can decide L contradictory to? $\endgroup$ – 3yakuya Dec 11 '14 at 12:50
  • 1
    $\begingroup$ @Byakuya, in order, (1) Assume $X$ decides $L$, (2) then we could run $X$ on any $\langle N \rangle$ as constructed above, (3) but then we'd know if $M$ halted on $x$ or not, (4) we already know we can't work that out in general, so (5) we have a contradiction, and (6) the original assumption is wrong - there can be no $X$ that decides $L$, which is the same as saying $L$ is undecidable. $\endgroup$ – Luke Mathieson Dec 11 '14 at 12:56
  • $\begingroup$ Ok, so one of your assumptions (or known facts) here is that we can't work out the H problem in general. And if our assumption (1) was correct, we could work H out - contradiction. Thank you very much. $\endgroup$ – 3yakuya Dec 11 '14 at 13:00

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.