patternMinor
Prove REGULAR_TM is undecidable
Viewed 0 times
proveundecidableregular_tm
Problem
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
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
Solution
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.
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.
Context
StackExchange Computer Science Q#48637, answer score: 4
Revisions (0)
No revisions yet.