7
$\begingroup$

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
$\endgroup$
  • 2
    $\begingroup$ Perhaps a better approach would be to look up and understand Rice's Theorem, which tells why any non-trivial property of a Turing Machine's language is undecidable. $\endgroup$ – jmite Oct 23 '15 at 16:55
  • $\begingroup$ OK, jmite, will do. $\endgroup$ – slnsoumik Oct 23 '15 at 17:14
  • 1
    $\begingroup$ @jmite, the proof of Rice's theorem is essentially the same as you'd give for this. Sure, once you have that, this (and a raft of similar questions) become trivial. $\endgroup$ – vonbrand Jan 12 '16 at 20:26
  • $\begingroup$ I've found the following useful here: Since Sigma* (Sigma = alphabet set) is a regular language, for R to decide whether M2 accepts a regular language it must consider all possible inputs (Sigma ), including 0^n1^n and other nonregular languages. So if M accepts w, M2 accepts not only 0^n1^n kind of inputs but Sigma. But if M does not accept w, M2 will accept just 0^n1^n strings. Hope it helps. $\endgroup$ – Ali Shakiba Jun 15 '16 at 13:05
4
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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?

    enter image description here 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.

$\endgroup$

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.