可判定性读书笔记 (3)

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

所有证明都偷自 《计算理论导引》(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\), 因而矛盾

上一篇:时间和日期例程(个人理解的笔记)


下一篇:能混也TM是一种本领