3
$\begingroup$

I'm reading through Sipser's Intro to the Theory of Computation for a class, and I'm having trouble understanding one of the examples in the book.

The example shows how $REGULAR_{TM}$, defined as the problem of determining if a Turing machine recognizes a regular language, is undecidable. The way they do it is by showing a reduction from $A_{TM}$, which is the acceptance problem for Turing Machines (the acceptance problem for some computational model is the task of determining whether or not it accepts a given input string).

From what I understand, all that needs to be done is show that if $REGULAR_{TM}$ was decidable by some TM $R$, then another TM could use $R$ to decide $A_{TM}$, which would be a contradiction, since $A_{TM}$ is undecidable.

They construct a TM $S$ that can be used to decide $A_{TM}$. Where I'm lost is through their use of an intermediate TM, $M_2$. Here is the full description:

  • $S$ = "On input $\langle M, w\rangle$, 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 $\langle M_2 \rangle$.
    3. If $R$ accepts, accept; if $R$ rejects, reject."

My two main questions are:

  1. Why are we allowed to do step 2 in the construction of $M_2$? If we could just say "run $M$ on $w$ and accept if $M$ accepts", then wouldn't that be a way to show that $A_{TM}$ is decidable?
  2. What exactly is the role of step 1 in the construction of $M_2$? The book says that the purpose of this TM is not to be run, but just to feed its description into $R$. The TM recognizes $\{0^n1^n\mid n \ge 0\}$ if $M$ does not accept $w$, and $\Sigma^*$ if it does, but I don't see how it does that from the description. Also, I don't see how $A_{TM}$ can be decided by using this (I'm thinking it's that the TM $M_2$ only outputs a regular language if the TM $M$ accepts $w$, but I don't understand how it can do that).

Any help is greatly appreciated, thanks!

$\endgroup$
  • $\begingroup$ Please provide all the definition to make your question self contained. What is $A_{TM}$? $\endgroup$ – Ariel May 17 '16 at 18:05
  • $\begingroup$ Thanks! Updated the question with this info: $A_{TM}$ is the acceptance problem for Turing machines. It determines whether or not a Turing machine accepts a given input string. While the acceptance problem for both DFAs and CFGs is decidable, it is not for TMs. $\endgroup$ – Andrew DiNunzio May 17 '16 at 18:10
4
$\begingroup$

This proof assumes, for the purpose of contradiction, that there exists a Turing machine $R$ deciding $R_{TM}=\left\{\langle M\rangle | \hspace{1mm} L(M) \text{ is regular}\right\}$, and uses the existence of $R$ to construct a Turing machine deciding $A_{TM}=\left\{\langle M,w\rangle | \hspace{1mm} M \text{ accepts $w$}\right\}$.

$R$ halts on every input (since it decides $R_{TM}$), so there is no problem running it (it will finally halt and either accept or reject the input). This avoids the problem of running $M$, some arbitrary Turing machine, on some input $w$, since we do not know that $M$ will finally halt.

Now, Sipser constructs a new Turing machine, $M_2$, such that:

$L(M_2) \text{ is regular} \iff M \text{ accepts $w$}$

If the above holds, then you would have $\langle M_2\rangle\in L(R) \iff M \text{ accepts $w$}$, so you could find out if $M$ accepts $w$ simply by running $R$ (which always halts) on $M_2$.

To see why this property holds, note that $M_2$ always accepts strings of the form $0^n1^n$, and it accepts any string not of this form iff $M$ accepts $w$. This means that $L(M_2)=\left\{0^n1^n | n\ge 0\right\}$ if $M$ does not accept $w$, and $\Sigma^*$ (which is regular) otherwise.

$\endgroup$
  • $\begingroup$ Okay thanks, so when constructing something to be encoded and used by $R$ (like $M_2$) we are not required to make it decidable? Also, the last sentence seems a bit confusing to me. Do you mean $L(M_2)=\{0^n1^n \mid n \ge 0\}$ if $M$ does not accept $w$? From what I understand, the purpose of $M_2$ is to accept if $M$ recognizes $w$ and reject if $M$ does not accept $w$. But it also has to align with regularity, so if $M$ accepts $w$, it should decide a regular language, and if $M$ does not, it should decide a non-regular language (which arbitrarily is $0^n1^n$)? $\endgroup$ – Andrew DiNunzio May 17 '16 at 21:51
  • $\begingroup$ We can give any input to $R$. Regardless of what the machine $M_2$ does, we can input it's encoding $\langle M_2 \rangle$ to $R$ and get an answer. As for your second question, you are correct, I meant $L(M_2)=\left\{0^n1^n | n\ge 0\right\}$ if $M$ does not accept $w$, now fixed. $\endgroup$ – Ariel May 17 '16 at 21:59

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.