可判定性读书笔记 (1)：可数集和不可数集和 $A

您所在的位置：网站首页 › 可数集和无限集 › 可判定性读书笔记 (1)：可数集和不可数集和 $A

可判定性读书笔记 (1)：可数集和不可数集和 $A

2024-07-16 21:14| 来源: 网络整理| 查看: 265

可数集和不可数集和 $A_{TM}$ 不可判定实数集是不可数集合

将实数以无限小数的形式定义，$(0.999.. = 1.000..)$，那么证明实数为不可数集合如下：

假定存在一个映射 $f:\N \to \R$ ，记 $A = f(\N)$，只需总是构造出一个 $x \in \R$ ，使 $x$ $\notin A$

取出一个 $a_1\in A$ ，使实数 $b$ 的第1个小数位不等于 $a_1$ 的第1个小数位取出一个 $a_2\in A$ 且 $a_2 \ne a_1$ ，使实数 $b$ 的第2个小数位不等于 $a_1$ 的第2个小数位取出一个 $a_3\in A$ 且 $a_3 \ne a_1, a_2$ ，使实数 $b$ 的第3个小数位不等于 $a_1$ 的第3个小数位 ..

无限执行这个过程，得到一个实数 $b \in \mathcal{R}$ 使得 $\forall a_i \in A, a_i \ne b$，因此 $b \in A$ ，故而得证。（我对这个过程其实有点不太懂，总感觉有哪里没有定义清楚）

任意「语言 $L$ 」是可数集合

语言是由有限字符集 $\Sigma$ 排成的有限长字符串组成的集合 $\Sigma^*$，因而长度为 $n$ 的字符串最多只有 $|\Sigma|^n$ 个，故而可以与 $\N$ 一一对应。

「任意集合 $A$ 」的幂集 $\mathcal{p}\{A\}$ 与 $A$ 不等势

我感觉这个证明有哪里不对劲，但我说不出来

「无限长二进制字符串」的集合 $\mathcal{B}$ 是不可数集合

这个用证实数集的方法来证

「所有「二进制语言 $L_B$ 」」的集合 $S_{L_B}$ 与 $\mathcal{B}$ 等势

$L_B$ 的字符集为 $\Sigma_B = \{0, 1\}$，那么 $L_B\sub \Sigma_B^*$

由于 $L_B$ 可数，故而可列。

例如 $L_{B1}$ 是以 $0$ 开头的 $0, 1$ 字符串，与 $\Sigma_B^*$ 一同排列如下，这样就可以构造出一个无限长的二进制序列 $\mathcal{X_{B1}}$

\[\begin{matrix} \Sigma_B^*= & \{ & \epsilon, &0, &1, &00, &01, &10, &11, &000, &001, &... & \} \\ L_{B1}= & \{ & &0, & &00, &01, & & &000, &001, &... & \} \\ \mathcal{X_{B1}} = & &0 &1 &0 &1 &1 &0 &0 &1 &1 &... & \} \\ \end{matrix} \]

这样 $\mathcal{X_{B1}} \in \mathcal{B}$，且显然每个$\mathcal{X_{B1}}$ 与 $L_{B1} \in S_{L_B}$ 是一一对应的关系，因此得证。

$S_{L_B}$ 是不可数集合

$\mathcal{B}$ 是不可数集合，所以 $S_{L_B}$ 是不可数集合

「所有语言」的集合 $S_L$ 是不可数集合

$S_{L_B} \sub S_L$，所以 $S_L$ 是不可数集合

$A_{TM}$ 不可判定

这里首先补充一下定义：

语言 $A$ 是可识别的 $(recognizable)$ 当且仅当存在图灵机 $M$ 使得 $M$ $accept$ $A$ 中的任意字符串语言 $A$ 是可判定的 $(decidable)$ 当且仅当存在图灵机 $M$ 使得对于任意字符串 $S$ , a. 当 $S\in A$ 时， $M ~ accept ~ S$ b. 当 $S\notin A$ 时， $M ~ reject ~ S$

著名的「图灵停机问题」可以规约到这里要证明的「语言 $A_{TM}$ 」不可判定

\[A_{TM} = \{\lang M, w\rang ~|~ M~is~a~TM~and~M~accepts~w\} \]

假定 $A_{TM}$ 可判定，那么存在它的判定器 $H$

\[H(\lang M, w\rang) = \begin{cases} accept & if ~M ~accepts~ w\\ reject & if~ M ~does~ not~ accept~ w \end{cases} \]

构造图灵机 $D(\lang M\rang) = opposite~H(\lang M, \lang M \rang \rang)$，那么 $D$ 应该有如下的表现

\[D (\lang M\rang) = \begin{cases} accept & if~ M ~does~ not~ accept~ \lang M\rang\\ reject & if ~M ~accepts~ \lang M\rang \end{cases} \]

所以

\[D (\lang D\rang) = \begin{cases} accept & if~ D ~does~ not~ accept~ \lang D\rang\\ reject & if ~D ~accepts~ \lang D\rang \end{cases} \]

也就是说，

\[if \begin{cases} D~accept~\lang D\rang, then~D~reject~\lang D \rang\\ D~reject~\lang D\rang, then~D~accept~\lang D \rang \end{cases} \]

用集合的语言来说，就是:

若 $\lang D, \lang D \rang \rang \in A_{TM}$，则 $\lang D, \lang D \rang \rang \notin A_{TM}$ 若 $\lang D, \lang D \rang \rang \notin A_{TM}$，则 $\lang D, \lang D \rang \rang \in A_{TM}$ 停机问题（halting problem）

\[HALT_{TM} = \{\lang M, w\rang ~|~ M~is~a~TM~and~M~halts~on~w\} \]

停机问题是「 $HALT_{TM}$ 是不可判定的」

反证法：假定有一个 $R$ 能判定 $HALT_{TM}$，那么构造图灵机

\[S (\lang M, w\rang) = \begin{cases} accept & if ~ R ~reject \lang M, w\rang ~\&\&~M~accept~w\\ reject & if ~ R ~accepts~ \lang M, w\rang ~\|~M~reject~w \end{cases} \]

显然 $S$ 判定 $A_{TM}$，故而矛盾。因此 $HALT_{TM}$ 不可判定。

意义

停机问题可规约到「语言 $A_{TM}$ 」不可判定，但「语言 $HALT_{TM}$ 」其实是可识别的。

换言之，不存在「计算机」上能写出来的程序 $H$ 使得能判定一个程序 $M$ 是不是对于一个输入数据 $w$ 一定会停机。但是，存在一个程序 $P$ 能够模拟其他程序 $M$，如果 $M$ 对于输入数据 $w$ 会停机，那 $P$ 也会停机。

类比的话，这个 $P$ 可以说就是我们现在的「 $CPU$ + 内存」了，编译器汇编器把程序 $M$ 和输入 $w$ 翻译成机器码 $\lang M , w\rang$ , 传递给 $P$ 来模拟执行。只不过图灵盖棺定论：不存在一个能判定 $\lang M , w\rang$ 是不是会死循环的程序。

麻了

若 $A$ 可识别，且 $\bar{A}$ 可识别，那么 $A$ 可判定

我不知道反过来是否正确：如果 $A$ 不可识别， $\bar{A}$ 是否一定可识别？

【本文地址】

可判定性读书笔记 (1)：可数集和不可数集和 $A

可判定性读书笔记 (1)：可数集和不可数集和 $A

今日新闻

推荐新闻