Prove REGULAR_TM is undecidable

Question

I am studying the proof of the following theorem:

Given the language

$\mathit{REGULAR}_\mathit{TM} = \{\langle M \rangle | M $ is a turing machine and $\mathit{Accept}(M)$ is regular$\}$

$\mathit{REGULAR}_\mathit{TM}$ is undecidable.

---

The proof given in Sipser shows that if we already have a machine $R$ that decides $\mathit{REGULAR}_\mathit{TM}$ then we can make a machine $S$ that decides the halting problem:

$$\mathit{Accept}_\mathit{TM} = \{\langle M, w \rangle | M \mbox{ is a turing machine and }w \in \mathit{Accept}(M) \}$$

I am having trouble understanding the proof. Here's how I understand it:

When $M$ (any turing machine) and $w$ (any string) is fed to the machine $S$, we construct a machine $M_2$ that takes a string $x$ as input, but first runs machine $M$ on $w$. First case, if $w$ $\in $$\mathit{Accept}(M)$, then $M_2$ simply accepts x. That is $\mathit{Accept}(M_2) = \sum^*$ in this case - i.e a regular language. Otherwise, second case, $M$ rejects $w$, then $M_2$ checks if the input $x$ is of the form $0^n1^n$, and accepts if it is so - i.e $ \mathit{Accept}(M_2) $ is not a regular language. Inside $S$, for both these cases if we run $R$ on $M_2$ returns the appropriate result which $S$ can directly return.

The case I am confused about, the third case, is when $M$ does not halt on $w$. Then $\mathit{Accept}(M_2) = \{\}$, which is a regular language, and $R$ will therefore return ACCEPT, which $S$ cannot directly return as $w \notin \mathit{Accept}(M)$. But the description of the solution sounds to me like $S$ returns ACCEPT even in this case(pseudocode below). So what am I doing wrong? There's probably a very basic idea I am missing. Here's the pseudo-code for the machine $S$, and inside $S$, as you can see, there's the machine $M_2$ that $S$ creates.

machine S(M, w):
    // Construct an instance of machine M2 which uses M and w
    machine M2(x):
        r := M(w)  // Might hang here
        if r == ACCEPT:
            return ACCEPT
        else:
            if x is of form 0^n.1^n:
                return ACCEPT
            else:
                return REJECT

    // Run R on M2 (always returns, never hangs)
    r1 = R(M2)
    if r1 == ACCEPT:
        return ACCEPT
    else:
        return REJECT

Answer 1

Look up Rice's teorem. Its proof is quite short and sweet. It says that any non-trivial property of a TM language (i.e., one that not all TM languages share) is undecidable, in the sense that it can't be decided by looking at the TM if the language it accepts has the property.

The property of being regular (or a context free language, or the empty language, or the language of all strings, or...) is non-trivial, so if a particular TM accepts a language with the property is undecidable, by Rice's theorem.

Answer 2

Your pseudocode is wrong, the following is the correct one:

machine S(M, w):
    // Construct an instance of machine M2 which uses M and w
    machine M2(x):
        if x is of form 0^n.1^n:
            return ACCEPT
        else:
            r := M(w) // If LOOP, M2 accept 0^n.1^n
            if r == ACCEPT: 
                return ACCEPT // M2 accept Sigma* (Only this case make M2 accept regular language if only if M(w) accept)
            else if r == REJECT: 
                return REJECT // M2 accept 0^n.1^n

    // Run R on M2 (always returns, never hangs)
    r1 = R(M2)
    if r1 == ACCEPT:
        return ACCEPT
    else:
        return REJECT

@David Richerby Here is more explanation:

1. vonbrand is right
   He used Rice's teorem, it says that any non-trivial property of a TM language is undecidable. That's OK, but...in Sipser's book, this example is to demonstrate Mapping Reducibility.
   So we should use reduction to resove this problem instead of Rice's teorem.

2. What is wrong with the proposed answer?
   The wrong is:
   When M(w) LOOP in M2, R(M2) will return ACCEPT. Why? Because in this case L(M2) is {}, which is a regular language.But when M(w) LOOP, R(M2) must not return ACCEPT.
   Imagine:
   If R(M2) return ACCEPT, What will happen?
   There will be two possibilities for M2 to make R(M2) accept.
   (1)M(w) return ACCEPT.
   (2)M(w) LOOP.
   Obviously,"two possibilities" does not meet the definition of Reduction.
   What is the definition of Reduction?

   Please note <=>, that is "if only if".

3. What does my answer do to correct it?
   The key thing is: There is only one possibility to for M2 to make R(M2) accept, that is M(w) return ACCEPT! That meet the definition of Reduction.

4. Another solution for this problem:

   machine S(M, w):
       // Construct an instance of machine M2 which uses M and w
       machine M2(x):
           r := M(w)
           if r == ACCEPT:
               if x is of form 0^n.1^n:
                   return ACCEPT
               else:
                   return REJECT
           else if r == REJECT:
               return REJECT
   
       // Run R on M2 (always returns, never hangs)
       r1 = ComplementOfR(M2) // use Complement Of R
       if r1 == ACCEPT:
           return REJECT
       else:
           return ACCEPT
   

   In this solution, I use ComplementOfR instead of R.
   The benefits of this is:
   Now, in M2 we can run M on w first.
   Why we can use ComplementOfR?
   If R is decidable, then ComplementOfR is also decidable. Thus we can use ComplementOfR.