「 图灵机识别语言是否正则 」不可判定

所有证明都偷自 《计算理论导引》(Micheal Sipser)

正则图灵机不可判定 \(REGULAR_{TM}~is~undecidable\)

\[REGULAR_{TM} = \{ \lang M \rang ~|~ L(M) ~is~regular\} \]

证明思路：假设 \(R\) 判定 \(REGULAR_{TM}\) ，构造一个 \(S\)：

\[ S~decide~A_{TM} \iff R ~ decide ~REGULAR_{TM} \]

之前判定 \(E_{TM}\) 的关键在于利用 \(R\) 消除任意 \(\lang M, w \rang\) 的所有非停机状态，而这里是一种看起来不太一样的问题规约思路

对任意输入 \(\lang M, w \rang\) ，构造 \(M_w\) ：

\[M_w = \begin{cases} accept & if~x~has~the~form~0^n1^n \\ M(w) & otherwise \end{cases} \]

注意这里 \(M\) 接收的是 \(w\)。那么 \(R\) 判定这样的 \(M_w\) 是什么结果呢？

1. 若 \(M~accpet~w\)，则 \(M_w~accept\) 所有输入 \(x\), 因此 \(L(M_w)=\Sigma^*\) 是正则语言
2. 若 \(M~doesn't~accept~w\)，那么 \(L(M_w)=0^n1^n\)，不是正则语言

所以可以将 \(M~accept~w\) 转化为 \(R~decide~M_w\):

\[R(\lang M_w\rang) = \begin{cases} accept & if~M~accept~w \\ reject & if~M~doesn't~accept~w \end{cases} \]

假设 \(C~decide~0^n1^n\) (\(C\) 显然是存在的)

bool M_w(x){
	if(C(x)) return true;
	return M(w);
}

bool S(<M,w>){
	if(R(M_w)){
		return true;
	}
	else{
		return false;
	}
}

这样就得到了一个 \(S~decide~\lang M, w \rang\)， 因而矛盾