1
$\begingroup$

Consider $\mathsf{REGULAR_{TM}} = \{\langle M \rangle \mid \text{$M$ is a TM and $L(M)$ is a regular language}\}$.

Let $S$ be the following algorithm, which solves $\mathsf{A_{TM}}$: “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$ (a machine solving $\mathsf{REGULAR_{TM}}$) on input $\langle M_2 \rangle$.

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

I am trying to understand this proof, but I am really confused with step 1 of $M_2$.

The book says "$M_2$ works by automatically accepting all strings in $\{0^n1^n \mid n ≥ 0\}$. In addition, if $M$ accepts $w$, $M_2$ accepts all other strings."

But I don't understand how could $M_2$ accept all strings. If $x$ is not of the form $0^n 1^n$ and $M$ does not accept $$, wouldn't $L( M_2 )$ be empty?. Or can we assume there are many different $x$ as an input to $M_2$?

$\endgroup$
  • $\begingroup$ The Turing machine $M_2$ accepts an input $x$. The input could be any binary word whatsoever. $\endgroup$ – Yuval Filmus Dec 15 '18 at 23:47
0
$\begingroup$

First, note that $M$ and $w$ in $M_2$ are fixed. So whatever is the input, $M$ always accepts or rejects $w$. Second, note that $M_2$ is not built to run.

Then:

You want to map $<M,w>$ to a regular language $L$ if and only if $M$ accepts $w$. Fix $L$, in that case you choose $\Sigma^*$. However, if $M$ rejects $w$ you don't want $L$ regular (otherwise $R$ will accepts), so you choose $L'\subset L$ such that $L' = \{0^n1^n\}$ which is not regular.

Now you have two cases:

1) if $M$ rejects $w$, then $M_2$ will accepts only the strings of the form $0^n1^n$, then $R$ will reject.

2) if $M$ accepts $w$, then $M_2$ will accepts all the strings of the form $0^n1^n$ and all other strings in $\Sigma^*-0^n1^n$, so $R$ will accept.

However in poor words, it consists to map an "yes istance" of $<M,w>$ to a single "yes instance" of $L$. Let me do an example:

You want to prove that $L=\{M |\ if\ M\ accepts\ w\ then\ M\ accepts\ flip(w) \}$, where $flip(w)$ is the bitwise of all the string $w$ (For example if $w$ = $100$ then $flip(w) = 011$.), is undecidable with a reduction from $A_{tm}$.

Suppose $L$ is decidable, then exists a $TM$ $R$ that decides $L$. So we can build a new $TM$ $S$ that decides $A_{tm}$.

We will doing something like this:

$S$ on input $<M,w>$: "build a new $TM$ where $M$ and $w$ are constants. Call it $N_{<M,w>}$, then run $R$ on input $N_{<M,w>}$ and do what $R$ does."

Inside $N_{<M,w>}$ we have our reduction. Take in mind we want this:

$M$ accepts $w$ if and only if $R$ accepts $L(N_{<M,w>})$

First, we fix $L(N_{<M,w>})$ = $\{100,011\}$ (This is just an "yes instance" of $L(N_{<M,w>})$

Now our $N_{<M,w>}$

$N_{<M,w>}$ on input $x$:

if $x$ = $100$ then accepts

else if $x$=011 then run $M$ on $w$ and do what $M$ does.

Then "run" $R$ on $N_{<M,w>}$ and $S$ will accept if $R$ does:

if $M$ rejects $w$, the only string could be accepted by $N_{<M,w>}$ is $100$ then both $R$ and $S$ will reject.

Otherwise if $M$ accepts $w$, $N_{<M,w>}$ will accept both $100$ and $011$ then both $R$ and $S$ will accept.

So $S$ can decide $A_{TM}$ which is impossible, the "error" was to suppose the existance of $R$.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.