第四章：可判定性
4 Decidability
关于其他章节的内容，请点这：《计算理论导引》学习笔记
4.1 Decidable Languages
几个可判定的语言
acceptance problem for DFA
the acceptane problem for DFAs of testing whether a particular deterministic finite automaton accepts a given string can be expressed as a language\( A_{DFA}\).
\( A_{DFA} = \{\langle B,w \rangle | \text{ B is a DFA that accepts input string w}\}\).
The problem of testing whether a DFA B accepts an input w is the same as the problem of testing whether <B,w> is a member of the language \( A_{DFA}\).
We simply need to present a TM M that decides \( A_{DFA}\).
M = “on input <B,w>, where B is a DFA and w is string:
1. Simulate B on input w.
2. If the simulation ends in an accept state, accept. If it ends in a nonaccepting state, reject.”
acceptance problem for NFA
\( A_{NFA} = \{\langle B,w \rangle | \text{ B is a NFA that accepts input string w}\}\).
N = “on input <B,w>, where B is a NFA and w is string:
1. Convert NFA B to an equivalent DFA C.
2. Run TM M on input <C,w>.
2. If M accepts, accept; otherwise, reject.”
acceptance problem for REX
\( A_{REX} = \{\langle B,w \rangle | \text{ B is a regular expression that generates string w}\}\).
P = “On input <R,w>, where R is a regular expression and w is a string:
1. Convert regular expression R to an equivalent NFA A.
2. Run TM N on input <A,w>.
3. If N accepts, accept; if N rejects, reject.”
emptiness testing for DFA
\( E_{DFA} = \{\langle A \rangle | \text{ A is a DFA and } L(A) = \emptyset\}\).
T = “On input <A>, where A is a DFA:
1. Mark the start state of A.
2. Repeat until no new states get marked:
3. Mark any state that has a transition coming ino it from any state that is already marked.
4. If no accept state is marked, accept; otherwise, reject.”
whether two DFAs recognize the same language
\( EQ_{DFA} = \{\langle A,B \rangle | \text{ A and B are DFA and } L(A) = L(B)\}\).
\( L(C) = (L(A) \cap \overline{L(B)}) \cup (\overline{L(A)} \cap L(B))\).
We can construct C form A and B with the sonstructions for proving the class of regular languages closed under complementation, union, and intersection.
\( L(C) = \emptyset \iff L(A) = L(B)\).
F = “On input <A,B>, where A and B are DFAs:
1. Condtruct DFA C as described.
2. Run TM T on input <C>.
3. If T accepts, accept. If T rejects, reject.”
acceptance problem for CFG
\( A_{CFG} = \{\langle G,w \rangle\} | \text{ G is a CFG that generates string w }\}\).
直接枚举会得到recognizer而不是decider
If G were in Chomsky normal form, any derivation of w has 2n-1 steps, where n is the length of w.
In that case, checking only derivations with 2n-1 steps to determine whether G generates w would be sufficient.
S = “on input <G,w>, where G is a CFG and w is a string:
1. Convert G to an equivalent grammar in Chomsky normal form.
2. List all derivations with 2n-1 steps, where n is the length of w; except if n = 0, then instead list all derivations with one step.
3. If any of these deravation generate w, accept; if not, reject.”
emptiness testing for CFG
\( E_{CFG} = \{\langle G \rangle | \text{ G is a CFG and } L(G) = \emptyset\}\).
转化为可达性问题，目的地是terminal symbols，起点是start variable
R = “On input <G>, where G is a CFG:
1. Mark all terminal symbols in G.
2. Repeat until no new variables get marked:
3. Mark any variable A where G has a rule \( A \longrightarrow U_1U_2\dots U_k\) and each symbol \( U_1,\dots,U_k\) has already been marked.
4. If the start variable is not marked, accept; otherwise, reject.
whether two CFGs generate the same language
\( EQ_{CFG} = \{\langle G,H \rangle | \text{ G and H are CFGs and } L(G) = L(H)\}\).
在这里，\( EQ_{DFA}\)的套路用不了了
因为，The class of context-free languages is not closed under complementation or intersection.(Exercise 2.2)
事实上，这是不可判定的🙂
every context-free language is decidable
\( M_G\) = “On input w:
1. Run TM S on input <G,w>.
2. If this machine accepts, accepts, if it rejects, reject.”
4.2 Undecidability
对角线法
接下来讲了一波无穷大集合之间怎么比较大小，就是为了引入对角线法？
简单的说，如果两个集合之间存在一个双射函数使其一一对应，那么两个集合大小相等
比如偶数集与自然数集、直线与平面🙂，局部与整体等大，是不是很神奇，这就是无穷大的魅力
在这基础上定义了可数（countable）这个概念：
A set A is countable if either it is finite or it has the same size as N.
我们日常在数数（count）的时候“1，2，3，。。。”其实就是在被数的对象与自然数集N之间建立一一对应关系
于是按一个套路把有理数排列起来后，发现可以一个不漏地数下去，就证明有理数可数了
很自然地，我们会想，无理数呢？实数呢？复数呢？
很遗憾，这些都是不可数的，这时就要用对角线法证明了
反证法：
假设R与N之间存在双射函数f(n)
那么我们可以构造出一个不在f(n)值域的实数出来，这就破坏假设了，证毕。
这个数是这样的：
小数点后第i位与f(i)的的小数点后第i位不同，如图
这个数的每一位都和对角线上对应位不同，所以叫对角线法。
很容易证明，代数数是可数的，而复数是不可数的，复数又由代数数与超越数组成
于是就证明了超越数的存在性，却没证明一个数是超越数，康托尔就是迪奥
类似的思路，图灵机是可数的，语言是不可数的
所以必定存在some languages are not Turing-recognizalbe
一个不可判定的语言
\( A_{TM} = \{\langle M,w \rangle | \text{ M is a TM and M accepts w }\}\) is undecidable.
不妨先证一下\( A_{TM}\)是可被图灵识别的：
只需构造一个图灵机出来就可以了：
U = “On input <M,w>, where M is a TM and w is a string:
1. Simulate M on input w.
2. If M ever enters its accept state, accept; if M ever enters its reject state, reject.”
不可判定的证明：
（还有个更简洁的证明在第六章）
假设\( A_{TM}\)是可判定的 \( \longrightarrow\) 存在decider H \( \longrightarrow\) 存在decider D \( \longrightarrow\) 存在悖论
所以假设不成立，证毕。
其中，
H就是\( A_{TM}\)的decider
\( H(\langle M,w \rangle) =
\begin{cases}
accept & \text{if M accepts w} \\
reject & \text{if M does not accept w}
\end{cases}\)
D = “On input <M>, where M is a TM:
1. Run H on input <M,<M>>.
2. Output the opposite of what H outputs. That is, if H accepts, reject; and if H rejects, accept.”
\( D(\langle M \rangle) =
\begin{cases}
accept & \text{if M does not accepts }\langle M \rangle \\
reject & \text{if M accepts }\langle M \rangle
\end{cases}\)
是不是很像“理发师悖论”？所以接下来：
\( D(\langle D \rangle) =
\begin{cases}
accept & \text{if D does not accepts }\langle D \rangle \\
reject & \text{if D accepts }\langle D \rangle
\end{cases}\)
当对D输入<D>的时候,D既不可以accept，又不可以reject，也不可以其他，所以矛盾出现。
是不是感觉没用对角线法？其实人家用了，你看不出来而已，有图有真相：
另外，有个问题：
如果D里面不运行H，而是运行U，好像也有矛盾啊，那不就证明了U不存在？
这个问题我纠结了几个钟ORZ。。。最后我的答案是这样的：（欢迎到评论区和我讨论）
首先明确D修改后是这样的：
E = “On input <M>, where M is a TM:
1. Run U on input <M,<M>>.
2. If U ever enters its accept state, reject; if U ever enters its reject state, accept.”
也就是说，与D不同的是，E有可能会死循环，这就是关键
现在再对E输入<E>看看：
同样，E既不可以accept，又不可以reject
但是，现在E可以死循环，所以我的结论是：E(<E>)会死循环
所以E并不像D那样是一个矛盾的不可能存在的图灵机，答毕。
定理4.0
A language is decidable iff it is Turing-recognizable and co-Turing-recognizable.
(We say that a language is co-Turing-recognizable if it is the complement of a Turing-recognizable language.)
证明很简单，略去
推论：
\( \overline{A_{TM}}\) is not Turing-recognizable.
证明很简单，略去
但是，不妨设法构造一个识别\( \overline{A_{TM}}\)的图灵机出来，看看问题在哪
\( \overline{A_{TM}} = \{\langle M,w \rangle | \text{ M is a TM and M does not accept w }\}\)
Z = “On input <M,w>, where M is a TM and w is a string:
1. Simulate M on input w.
2. if M ever enters its accept state, reject; if M ever enters its reject state, accept.
3. if M loops, accept.”
这个并不能作为证明，但是，从第三点可以看出，因为停机问题不可判定，所以\( \overline{A_{TM}}\)不可被图灵识别