3
$\begingroup$

I'm trying to understand reduction, this is from my textbook and is not a homework problem or even any exercise, just trying to understand an example they present.

This is the reduction they give:

PROOF We let R be a TM that decides REGULARTM and construct TM S to decide ATM . Then S works in the following manner.

S = “On input $M$, $w$ , where M is a TM and w is a string:

  1. Construct the following TM $M_{2}$ .

    $M_{2}$ = “On input x:

    1. If x has the form $0^{n} 1^{n}$ , accept .

    2. If x does not have this form, run M on input w and accept if M accepts w.”

  2. Run R on input $M_{2}$ .

  3. If R accepts, accept ; if R rejects, reject .”

So, we start with a machine that decides whether a language of a TM is regular. And we want to use that to decide if a TM halts on a given input.

My question: What if $w$ does have the form $0^{n} 1^{n}$? Well, $M_{2}$ accepts that string just cause of the form. But we never actually run $M$ on $w$. So how can we say that it will accept or reject it? We have no idea what it does because we never ran it on $w$.

$\endgroup$
  • $\begingroup$ Is that the whole proof? $\endgroup$ – Karolis Juodelė Dec 11 '13 at 20:37
  • $\begingroup$ Yes, that is all of the formal proof. They also state: "The idea is for S to take its input M, w and modify M so that the result- ing TM recognizes a regular language if and only if M accepts w. We call the modified machine M2 . We design M2 to recognize the nonregular language {0n 1n | n ≥ 0} if M does not accept w, and to recognize the regular language Σ∗ if M accepts w. We must specify how S can construct such an M2 from M and w. Here, M2 works by automatically accepting all strings in {0n 1n | n ≥ 0}. In addition, if M accepts w, M2 accepts all other strings." $\endgroup$ – Zach Dec 11 '13 at 20:42
  • 1
    $\begingroup$ So, as it's explained, M2 accepts a regular language only if M accepts w. Note that x and w are unrelated. M2 never runs on w. $\endgroup$ – Karolis Juodelė Dec 11 '13 at 20:51
  • 1
    $\begingroup$ M2 has exactly that, but written from the other end. It will accept 01 always, and accept anything else, if M accepts w. $\endgroup$ – Karolis Juodelė Dec 11 '13 at 21:02
  • 1
    $\begingroup$ Strings are not regular, languages are. $0^n1^n$ is in the language $\{0^n1^n\}$ and it is also in the language $\Sigma^*$. Why should it not be accepted? $\endgroup$ – Karolis Juodelė Dec 11 '13 at 21:52
4
$\begingroup$

Here's the key: work out what $L(M_2)$ is.

Notice that $M_2$ takes a string $x$ as input, so we are trying to identify which strings $x$ will cause $M_2$ to accept.

There are two cases:

  • Case 1: If $M$ accepts on input $w$. Then $L(M_2)=\Sigma^*$.

    In other words, in this case, it doesn't matter what $x$ is. $M_2$ will always accept on input $x$. If $x$ has the form $0^n 1^n$, then $M_2$ accepts (in step 1). If $x$ does not have the form $0^n 1^n$, then $M_2$ also accepts (in step 2). $M_2$ accepts either way; it accepts on every possible input.

  • Case 2: If $M$ does not accept on input $w$. Then $L(M_2) = \{0^n 1^n : n \in \mathbb{N}\}$.

    Let's look at why this is. If $x$ has the form $0^n 1^n$, then $M_2$ accepts in step 1. If $x$ does not have the form $0^n 1^n$, then $M_2$ runs step 2 and doesn't accept (since $M$ doesn't accept on input $w$).

So, $L(M_2)$ is one of two possibilities: it is either $\Sigma^*$ (everything) or $\{0^n 1^n : n \in \mathbb{N}\}$. Which of those two possibilities it is will depend upon $M$ and on $w$ (and in particular on whether $M$ accepts on $w$). Remember that implicitly $M_2$ is dependent upon $M$ and $w$: it's got them hard-coded into its code.

Moreover, $\Sigma^*$ is regular, but $\{0^n 1^n : n \in \mathbb{N}\}$ is not regular. So if we have a way to tell whether the language of a TM is regular or not, we have a way to tell whether $L(M_2)$ is $\Sigma^*$ or $\{0^n 1^n : n \in \mathbb{N}\}$ -- which in turn means we have a way to distinguish Case 1 from Case 2, or in other words, we have a way to tell whether $M$ accepts on input $w$ or not.

That means, if we have a way to tell whether the language of a TM is regular or not, we have a way to solve the halting problem. (It's not the same TM; it's a related TM. The way we tell whether $M$ accepts on $w$ is not by analyzing whether the language of $M$ is regular; we construct some new TM that is related to $M$ and $w$ in a crazy way, and then test whether the language of that new TM is regular or not.)


It's important to remember that $w$ is not an input to $M_2$. Instead, $w$ is just a constant that is hard-coded into the source code of $M_2$. It would be like hard-coding the value of pi as 3.1415927 in your code, except here the hardcoded constant is going to be whatever $w$ is. Each different $w$ corresponds to a different $M_2$.

P.S. I'll also repeat a crucial point from Karolis Juodelė: "Strings are not regular, languages are."

$\endgroup$
  • $\begingroup$ I suppose my confusion is because strings of the form $0^{n} 1^{n}$ are in the language even if $M$ does not accept $w$. $\endgroup$ – Zach Dec 11 '13 at 21:47
  • $\begingroup$ @Zach, one thing that might help you clear up your confusion is to be very explicit about which language you are talking about. The language $L(M_2)$ is completely different from the language $L(M)$. See my edited, extended answer. $\endgroup$ – D.W. Dec 11 '13 at 21:49

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.