Skip to content

4 不可判定性

myc智云 2023-11-22 到11-29

Church-Turing Thesis

算法(非形式化的概念) 对应于图灵机（数学对象)

不是数学命题，不能被证明。

通用图灵机

编码

UTM

把图灵机用字符串表示 （相当于一个“程序”），在另一个图灵机上进行。用一个图灵机去“模拟"图灵机。

记为"M""w" “M”相当于把图灵机表示为“程序” "w"是程序的输入

Undecidability

递归语言(Recursive,REC) \(\subseteq\) 递归可数(RE) \(\subseteq\) ?

下面的说法含义是一样的：

  • decidable=recursive
  • undecidable=not recursive(可能RE,也可能not RE)

规约

定义: 存在一个recursive 的函数 \(f:\Sigma_A^* \to \Sigma_B^*\) 使得\(\forall x \in \Sigma_A^*,x \in A \Leftrightarrow f(x)\in B\) 则称把A规约到B，记为\(A\leq B\)

Tip

问题A能规约到问题B, 说明问题B一定不比问题A简单。所以用\(A\leq B\) 表示A的"难度"<=B

若\(A\leq B\), 则\(\bar{A}\leq \bar{B}\)

RE但非递归的语言/非RE的语言

存在性:

  • 所有 TM 的集合是可数的，但所有语言的集合是不可数的(利用对角化)
  • 每个TM只能半判定一种语言 (RE)
  • 所以一定存在不是RE的语言

构造：

Warning

$H_d=${"M": M is a TM that does not halt on "M"} 不是RE

H={"M""w", M is a TM that halts on w} 是RE但不是REC $\bar{H}=${"M""w",M is a TM that does not halts on w} 不是RE

证明H是RE的。只需要构造UTM run M on w

证明H不是REC的 构造$H_d=${"M": M is a TM that does not halt on "M"} 把图灵机M自身的编码(字符串“M”) 放在M上跑, 不停机

  1. 假设H是递归的, 那么\(H_d\)也是递归的。 证明: 因为H是递归的，存在\(M_H\)判定H, 那么run \(M_H\) on "M""M" (相当于 w是M的编码) . 如果\(M_H\) 接受"M""M", 那就说明M is a TM that halts on w, 不符合\(H_d\)的条件, 那就拒绝"M"。反之就接受"M"。 因为H递归, \(M_H\)能在有限时间内接受或拒绝, 所以\(H_d\)也是递归的
  2. \(H_d\)不是RE的。 证明： 如果\(H_d\)是RE的, 那么存在\(M_D\)半判定H. run \(M_D\) on "\(M_D\)" 如果停机, 根据半判定的定义,字符串 "\(M_D\)" \(\in H_d\) 但是根据语言\(H_d\)的定义 那么\(M_D\) is a TM that does not halt on "\(M_D\)" 矛盾
  3. 因为2 \(H_d\)不是递归语言, 那么根据1 H不是递归语言。

这个证明的思想也可以用对角化来理解 因为图灵机是可数的，可以按照1,2,3列出所有的图灵机。把对角线取反,得到D=0 0 1 ... D(就是上面证明中的图灵机\(M_D\)) 不跟任意一行相同, 所以D不是图灵机

证明不是REC

Warning

如果存在一个规约\(A\leq B\)
- 如果B是REC,那么A是REC - 如果A不是REC，那么B不是REC - 如果B是RE,那么A也是RE

证明A不是REC：

  • 找到 \(B\leq A\), 其中 B不是REC。 (比如B是H)
  • Rice's Theorem
  • 定义 对角化

注意方向! A的“难度”至少跟B相当 是把B规约到A

常见的不可判定问题(但是RE)

L1={"M", M is a TM that halts on e} \(H\leq L_1\)

L2={"M", M is a TM that halts on some input} \(H\leq L_2\)

L3={"M", M is a TM that halts on every input} \(H\leq L_3\)

L4={"M1""M2": M1 and M2 is a TM, L(M1)=L(M2)} 两个图灵机半判定同一个语言. 那么 \(L_3\leq L_4\)

L1证明: 对于H中的M,w 构造图灵机M 无论输入是什么,都相当于出run M on w。如果M halts on e,就说明 M* halts on w. 反之同理。
证明: 构造一台机器M2 不管输入什么都直接停机 那只需要判断M和M2是不是一样就可。
所以L1-L4都不是recursive的

注意L3是非RE的

  • 把\(\bar{H}\)规约到L3

Tip

把A规约到B： 假设有一个图灵机能判定B , 怎么用这个图灵机解决问题A？

Rice's Theorem

\(R_{TM}\)={"M": M is a TM with L(M) regular} 是不可判定的 {"M": M is a TM with L(M) CFG} 是不可判定 {"M": M is a TM with L(M) Recursive} 不可判定

尝试把H规约到\(\bar{R_{TM}}\) 因为H不是正则的。 证明: 构造TM M‘ : 对于输入x 1) run M on w (这一步与输入x无关) 如果停机,接着 2) run U on x, U是通用图灵机

$$ L(M')=\begin{cases} \emptyset,\text{M does not halts on w} \ L(U)=H, \text{M halts on w} \end{cases} $$ 然后run " M' " on \(\bar{R_{TM}}\)对应的图灵机

  • 如果接受,就说明\(L(M')\)不是正则的。 考虑L(M')的两种情况。空集一定是正则语言。而下面的语言是H。那就说明M halts on w
  • 否则就说明M does not halts on w 这样就把H规约到 \(\bar{R_{TM}}\)

这些问题本质上都是在问图灵机M半判定的语言 L(M) 具有什么性质

Rice's Theorem

\(R(P)=${"M", M is a TM with L(M) having property P} 令\)\mathcal{L}(P)$ 为具有性质P的所有 RE 语言的合集 - 如果\(\mathcal{L}(P)\) 是RE语言的 非空真子集, 那么 R(P) 不是recursive(不可判定) - 如果\(\mathcal{L}(P)\) 是空集或者包含所有RE语言 那么 R(P)是recursive的

该定理只能判断不是Recursive, 不能判断是不是RE

  • 从补集 \(\bar{H}\) 规约

证明不是RE

证明A不是RE

  • 找到\(B\leq A\) 其中B不是RE (比如Hd)
  • 使用定理 \(A\)是REC当且仅当\(A\)和\(\bar{A}\)都是RE

证明是REC

证明A是RE

  • 找到\(A\leq B\) B是REC
  • 证明\(A\)和\(\bar{A}\) 都是RE
  • 用定义构造图灵机

证明是RE

证明A是RE

  • 找到\(A\leq B\) B是RE
  • 用定义构造图灵机

A={"M", M is a TM that halts on some input} 是RE的

总结

思路

  • Rice定理只能判定不是REC。 不能判定是不是RE。如果要证明not-RE 还是要用规约的方法
  • 把\(H,\bar{H}\) 规约到\(L\) 本质上是找一个函数\(f(M,w)=M'\) 讨论图灵机\(M'\)输入\(x\) \(L(M')\)是什么,是否满足\(L\)的性质P
    • 一般是找性质P的特例(充分条件) 比如接受所有长度为偶数的字符串=>接受所有字符串

常见的构造:

\(f(M,w)=M'\)
\(M'\) on input x: run M on w(注意不是x!!) . 如果停机就accept.

  • "M""w" \(\in H\) 则\(L(M')=\)所有字符串
  • "M""w" \(\notin H\), 则\(L(M')=\emptyset\)

\(M'\) on input x: run M on w for |x| steps 如果停机就reject, 否则accept

  • "M""w" \(\in \bar{H}\) 则\(L(M')=\)所有字符串
  • "M""w" \(\notin \bar{H}\), 则\(L(M')=\emptyset\)

空集\(\emptyset\) 是finite的

一般集合大小>= xxx 是RE 如果是=或者< 就not-RE

Turing enumable

L是图灵可枚举的当且仅当他是RE的

左推右: 假设M枚举L: 构造自动机M‘ 对于输入x:

  1. run M to enumerate L
  2. 对于M枚举的字符串w 如果w=x则停机。 M'半判定L

右推左: 假设M半判定L, 构造自动机M'

  1. M’ 在M字母表的第1个字符串(按字典序) 运行M 1步
  2. M‘ 在前2个字符串 运行M 2步
  3. M‘ 在前2个字符串 运行M 3步 以此类推... 当M’找到M接受字符串wi之后，转到状态q里显示w,并把wi记录下来。然后重新开始,如果新找到的字符串与之前找到的相同,就继续找，直到找到一个没出现过的。

Tip

在前i个字符串 run M i步 判断是否接受 - 比如证明{"M"| M 在所有上输入上都停机 }是RE -

P/NP

P跟NP都是可判定的。

闭包性质

Example

4个选项都是对的

(3) (4) (5) 思路: 用RE的封闭性、且REC一定RE, 可推出\(\bar{L_1}\)是RE的
(6) \(L\leq \bar{H}\) 可以推出\(\bar{L} \leq H\) H是RE, 那么\(\bar{L}\)也是RE. 因为L和它的补都是RE，所以L是recursive

Comments