CSCI3130 L10 · Part 3 非确定性、通用机与可数性

课程：CSCI3130 Formal Languages and Automata Theory · 资料包，学期待核 本讲：L10 · Part 3 非确定性、通用机与可数性 · 原件 L10-图灵机变体-资料包.pdf（本地课件） p.56–124 定位：从多条计算分支的模拟，走到机器与语言的数量比较。 前后：上一份 L10-P2-多带与多维存储.md · 下一份 L10-P4 有界带与构造练习

一个配置可以有多个后继（p.56–58）【新】

图（p.56–57）：同一状态读同一个符号时分成两条合法边。 元素：$q_1$ 读 $a$，可写 $b$ 左移进入 $q_2$，也可写 $c$ 右移进入 $q_3$。 看什么：分支选择改变的是整个后继配置，包括带内容、读头位置和状态。

p.57 初始片段 abc 的第一格是 $a$：选第一条变成 bbc，头移至原第一格左边；选第二条变成 cbc，头移到中间的 $b$。不能把两条边理解为先写 $b$ 再写 $c$；它们属于不同计算。

p.58 的接受条件是存在一条有限计算到终态。其他分支即使拒绝或永远运行，也不抵消已经存在的接受分支。非确定性不是随机概率，更不是要求多数分支接受。

为什么必须照顾所有分支（p.59–61）

p.60 Keeps track of all possible computations

p.59 确定性机器每个配置至多一个后继，所以本身就是非确定性机器的特例。困难在反向：怎样用确定性机器保持所有可能性？p.60 提出记录全部当前计算，p.61 把这些记录组织成树。根是初始配置，每条边是一合法步，同一层对应相同已执行步数。

补充：若只沿最左分支走到底，它可能死循环，使右边两步就能接受的分支永远没被检查。逐层展开则在检查完有限多个深度小于 $d$ 的节点后，必能到达深度 $d$ 的接受节点。这是后面模拟法需要的公平性。

把计算树写到带上（p.62–64）

p.62 继续展开上一页的树，提醒节点不能只写状态：相同状态配不同带内容仍是不同配置。p.63 用二维存储把多条计算分开保存；上一 Part 已说明二维带可以由标准带模拟，因此这只是方便设计的表示。p.64 先写入初始输入 abc，再用专门标记保留当前头位置及状态。

每一行是一个完整快照，不是该分支的输入副本而已。否则执行一次写带后，下一步就无法知道应该读取哪个新符号。

复制配置，再执行分支的一步（p.65–67）

p.67 NonDeterministic Machines have the same power with Deterministic machines

p.65 对存在两个后继的配置先复制。p.66 在各副本上分别执行相应转移：更改一个带格、移动头标记、替换状态；没有可用转移的分支从待展开表中去掉。若任何副本到终态，模拟机接受。所有副本都有限失败时可以拒绝；若永远存在未结束分支，模拟也可能不停。

这证明识别语言的能力相同。反向包含已由 p.59 给出，两边合起来才是 p.67 的相等，不应只写“可以模拟”而漏掉另一方向。

能力相同不等于代价相同（p.68–70）

p.68 The simulation in the Deterministic machine takes time exponential time compared to the NonDeterministic machine

若每步至多 $b$ 个后继，运行到深度 $t$ 时最多要处理 $1+b+\cdots+b^t$ 个节点。补充算例（数字为演示自取）：$b=2,t=3$ 时各层 $1,2,4,8$，共 15 个节点；单一路径只走 3 步。这个逐层模拟可能指数膨胀，但这不是证明任何确定性算法都必须指数时间。

p.69 是 Universal Turing Machines 分节页。p.70 把问题从“机器有哪些硬件变体”转成“能否固定一台机器，把不同程序当输入”。此前每张状态图都是一个硬接线的程序。

通用机接收程序与数据（p.71–73）【新】

p.71 Simulates any other Turing Machine

p.71 的“可重编程”不是运行中任意改数学定义，而是固定解释器，改变交给它的机器描述。p.72 输入包含目标机器 $M$ 的描述和 $M$ 的初始带内容。p.73 以三带布局区分这三种信息：第一带存转移表编码，第二带存被模拟的带，第三带存被模拟的当前状态。

通用机反复查找“当前状态、当前符号”对应的规则，在第二带执行写入和移动，并更新第三带。若 $M$ 在输入上不停，通用机也不凭空给出答案；通用性不等于能判断所有程序何时停止。

有限对象怎样编码成二进制串（p.74–76）

p.74 要把有限状态集合、字母表和转移表写成有限串。p.75 给符号依次用 1、11、111、1111 编码，p.76 给状态编号同样用一元串，左、右方向分别用 1、11。不同类别可以重复编码，因为各字段的位置告诉解释器它应读成状态、符号还是方向。

连续的一串 1 本身没有边界，因此必须补分隔符。有限编码的关键不是压缩效率，而是能够机械地辨认边界并恢复原来的转移规则。

单条规则与整台机器的分隔符（p.77–79）

题面（L10-图灵机变体-资料包.pdf · 编码算例 · p.77；公式按讲义重排）

p.77 Transition: $\delta(q_1,a)=(q_2,b,L)$

五字段依次为当前状态、所读符号、下一状态、所写符号、方向。代入 p.75–76 编码得到 1 0 1 0 11 0 11 0 1。四个单 0 分隔五个非空的一元字段。p.78 下一条 $\delta(q_2,b)=(q_3,c,R)$ 得到 11 0 11 0 111 0 111 0 11；两条规则之间用 00，所以不会与字段边界混淆。p.79 把这些块连接便得到整台机器的有限二进制描述。

机器描述本身组成一种语言（p.80–82）

p.80 把合法机器描述看成二进制字母表上的语言，p.81 用一些二进制串作示意。并非每个串都合法：字段数不对、分隔符放错、引用未定义的编号，都可能不符合选定编码规范。检查这些有限语法条件能够在有限时间结束。

p.82 是 Countable and Uncountable Sets 分节页。下面只需“每台机器有某个有限描述”，不要求不同描述必代表不同的计算功能；允许多台编码不同却行为相同的机器。

p.81 原页列出的示意码是 010100101、00100100101111、111010011110010101 等。它们用于说明机器可以用有限二进制串表示，并不都是 p.77 五个非空一元字段规则下的合法串：例如第一串以0开始，没有首个状态字段。因此练习编码应使用 p.75–79 的明确规则，不能由这些装饰性示例反推另一个分隔约定。

可数的意思是能排进自然数位置（p.83–85）【新】

p.84 Any finite set or Any Countably infinite set

p.83 区分可数与不可数，p.84 规定有限集合也算可数；可数无限集合的每个元素能与一个自然数一一对应。p.85 用 $0,2,4,\ldots$ 对应 $1,2,3,\ldots$，规则是 $2n\mapsto n+1$，这里 $n\ge0$。这张图实际列出的是非负偶数；“所有偶整数”还包括负数，需要另安排其位置。

无限集合可以与自己的真子集等势，所以不能直接沿用有限集合“少了一半，数量就减半”的直觉。

为什么按行数分数会漏掉下一行（p.86–88）

p.86 提出有理数可数。p.87 若先把 $1/1,1/2,1/3,\ldots$ 全列完，再列分子为 2 的一行，第二行没有有限起始位置，因为第一行永远列不完。p.88 把正分子、正分母排成二维格：格 $(r,s)$ 放 $r/s$。

修复目标是让每一个指定格都在有限步内被访问，而不是追求把某一条无限长的行先做完。这与非确定性模拟里的公平展开是同一种调度需求。

用有限的对角层推进（p.89–91）

这三页连续展示分数网格的枚举推进。按 $r+s=2,3,4,\ldots$ 的对角层走，每层只有有限格。任何指定的 $r/s$ 位于第 $r+s$ 层，前面只有有限格，因此不会被饿死。

补充算一遍（取讲义网格中的数）：$2/3$ 在和为 5 的层；先经过和为 2 的1格、和为3的2格、和为4的3格，再到这一层，最迟第10格已被访问。方向怎么来回折返不影响有限到达。

分数重复不妨碍先枚举，再去重（p.92–94）

p.92–93 延伸相同的对角访问，p.94 展示 $1/1,1/2,2/1,1/3,2/2,\ldots$。其中 $1/1=2/2$，所以格子与有理数值尚不是一一对应。要得到不重复的序列，可约分后跳过此前出现的数，或只输出互质分子分母。

补充：这个网格覆盖正有理数。要覆盖整个 $\mathbb Q$，先列0，再把正值与其负值交替输出。遗漏负数不影响正有理数可数的论证，却不能直接叫作完整 $\mathbb Q$ 的清单。

枚举程序与可数性（p.95–97）

p.95 the set of rational numbers is countable by describing an enumeration procedure

p.95 总结分数的构造；p.96 把枚举程序表成持续打印元素的图灵机；p.97 要求每个元素 $s_i$ 都在某个有限时刻 $t_i$ 被输出。这里不要求存在一个统一的有限时间把无限集合全部打印完。

需要同时证明不漏与不乱入：每个集合元素最终出现，输出的每个元素也确实属于集合。允许重复不妨碍“覆盖所有成员”，若讨论一一对应则再去重。

输出状态怎样标记一个元素完成（p.98–100）

p.98 从空白带开始，进入指定输出状态 $q_s$ 时，分隔符后区域是已打印的 $s_1$；p.99 对 $s_2,s_3$ 重复。这是在定义哪些时刻算正式输出，不意味着工作带每个中间字符串都是集合成员。p.100 得出有枚举程序的集合可数。

反向不可在没有条件时补上：抽象地能排成序列，不代表存在图灵机能计算这个序列。下文每一种语言都是可数集合，却并非每一种语言都能被图灵机识别，这正说明两种“可列出”的区别。

有限串要先按长度排序（p.101–103）

p.101 讨论 $\{a,b,c\}^{+}$。p.102 的普通字典序会先走 $a,aa,aaa,\ldots$ 而迟迟到不了 $b$。p.103 改为长度优先、同长度再字典序，亦称 proper order。

长度 $n$ 只有 $3^n$ 个串，故写完这一层一定能进下一层。指定长度 $n$ 的串前面至多有 $3+3^2+\cdots+3^n$ 个位置，不会被无限长前缀链挡住。

枚举有限串，再过滤合法机器（p.104–106）

p.106 Check if the string describes a Turing Machine

p.104 序列先 $a,b,c$，再 $aa,ab,ac,ba,bb,bc,ca,cb,cc$，然后长度3。p.105 把同一办法用于所有图灵机：每台机器有有限二进制编码。p.106 按长度优先生成二进制串，检查语法，合法就输出，非法就跳过。

这里检查的是“是不是机器描述”，不是“这台机器是否停止”。前者看有限语法就能结束；后者恰是下一讲要证明一般无解的问题。即使一个编码对应永不停机的程序，它仍然是合法机器描述。

幂集为何可能比原集大得多（p.107–109）【新】

p.109 Let $S$ be an infinite countable set The powerset $2^S$ of $S$ is uncountable

p.107 是不可数分节页，p.108 说明不可数就是无法和自然数一一配对。p.109 的幂集 $2^S$ 是“所有 $S$ 的子集”组成的集合；其中一个元素可能本身含无穷多个元素。

补充算例（集合为演示自取）：若 $S=\{a,b\}$，幂集有 $\varnothing,\{a\},\{b\},\{a,b\}$ 四个元素。无限版本不能只写“$2^\infty>\infty$”，必须排除任何可能的一一编号。

用无限位向量表示一个子集（p.110–112）

p.110 先把 $S$ 写成 $s_1,s_2,\ldots$。p.111 每个 $t\subseteq S$ 都选择其中某些元素；p.112 第 $i$ 位记1当且仅当 $s_i\in t$，否则记0。于是每个子集对应一个无限二进制序列。

不要与 p.79 的有限机器码混淆：一个子集可能需要无穷多位描述。正是从有限串到任意无限选择，集合大小才发生变化。

假定已经把所有子集列成表（p.113–115）

p.113 反证假设所有子集可列为 $t_1,t_2,\ldots$；这是假设某个数学列表存在，并未额外要求计算机可生成。p.114 第 $i$ 行写 $t_i$ 的位向量。p.115 只观察第1行第1位、第2行第2位，依次形成对角线。

设表项为 $b_{ij}\in\{0,1\}$，构造新序列 $d_i=1-b_{ii}$。每位定义都明确，所以它确实定义了 $S$ 的一个子集，而不是表外的不合法对象。

p.114–116 原对角表：

每行还有无穷后续位。前四个对角位为1100，逐位取反得到0011；第五位要查看尚未展示的第五行第五列，不能从前四行猜它。

每一行都被一个专门位置排除（p.116–118）

p.116 的示意新序列以 0011… 开始。p.117 证明它不等于任何第 $k$ 行：在第 $k$ 列，它的位是 $1-b_{kk}$，恰与那一行相反。即使其他所有位碰巧相同，这一位不同已足够排除相等。

p.118 得出假定的完整列表漏掉了这个合法子集，矛盾。所以幂集不可数。这里不是只攻击某一种排序；从任意假定完整的列表都能现场制造一个漏项。

字符串可数，所有语言不可数（p.119–121）

p.119 把 $\Sigma^{\ast}$ 以 $\lambda,a,b,aa,\ldots$ 的长度优先顺序列出，故它可数。p.120 每一种语言 $L$ 是其中一个子集；p.121 所有语言构成 $2^{\Sigma^{\ast}}$，由前一定理不可数。这里假设字母表非空，因而有限串集合是可数无限的。

一个语言里的串有可数多个，与有多少种语言是两层不同的问题。混淆“集合的元素”与“集合的子集”，就会错误地推出语言只有可数多种。

计数论证能证明存在，但没给显式例子（p.122–124）

p.123 There are some languages not accepted by Turing Machines

p.122 比较可数多台机器与不可数多种语言。每台机器只能识别一个语言，即使不同机器可以识别相同语言，总共也只能覆盖可数多种。p.123 因此有语言连识别器都不存在；p.124 图示把图灵机可识别的语言放在全部语言中的较小部分。

这是不可识别性的存在证明，比“有语言不能由总停机程序判定”更强；但没有指出某个具体语言的成员条件。下一讲通过对角化与停机问题填补这个缺口。

考试角度：（A 级：HW05-2025T1-题目.pdf Q4，对应可数与不可识别。）见附录 A1。

考试角度：（A 级：Final-Exam-2024T1-题目.pdf Q8；期末-2024未核-资料包.pdf Q8；Final-Exam-2025T1-题目.pdf Q7，对应自然数对可数与幂集不可数；扫描件视觉读取。）见附录 A2。

同样是“列出”，三个量词不能换位（补充）

可数性说存在一个数学编号，使每个元素占据某个自然数位置；计算枚举进一步要求有一台有限程序，在有限时刻逐个输出这些元素；判定还要在给定任意候选对象后，总能停机回答是否属于集合。第二种能推出第一种，却不能仅凭第一种取得程序；有枚举器也不能靠“等它打印到我”为非成员给出有限的否定结果。

对角集合 D 的构造只需要每一位都有明确的数学定义，不需要声称能有效算出那一位。特别是把“第 i 台机器是否接受第 i 个串”作为位值时，直接模拟可能永不结束。正是这一步的不可计算性，使“D 定义清楚”与“D 有判定器”没有冲突。不要在证明完不可数后，又把对角定义当成一个会返回答案的程序。

本讲核心考点

• 非确定接受是存在有限接受分支；公平逐层模拟给出识别能力等价（p.56–68，C 级）。
• 通用机把机器描述作为数据，模拟程序不意味着判断停机（p.69–81，C 级）。
• 可数、计算枚举、长度优先枚举不可混用（p.83–106，C 级）。
• 对角化在第 k 位排除第 k 行，证明幂集不可数（p.109–118，C 级）。
• 机器可数而语言不可数，因此存在不可识别语言（p.119–124，C 级）。

附录

本部分没有需要另列的推导；定义与算例在相应页段内。

A1 作业/往年题演练（非讲义内容）：HW05-2025T1-题目.pdf Q4

题面来自作业p.1；下面涉及辅导图及原解的页码均指 T07-2025T1.pdf（本地课件），不是作业的页码。完整过程同时写入本附录，便于在本讲练习。

题面块（HW05-2025T1-题目.pdf（本地课件） · Q4 · PDF p.1；与该辅导原题一致）：

p.1 Let $\Sigma$ be a finite alphabet. 1) Prove that $\Sigma^{\star}$ is countable. 2) Prove that the set of all languages over $\Sigma$, i.e., $\mathcal P(\Sigma^{\star})$, is uncountable. 3) Conclude that some languages cannot be recognized by any Turing machine.

第一问按长度升序、同长度按字典序枚举。有限字母表的每个长度层有限，每个有限串会在有限层出现。自取Σ={a,b}，开头为λ,a,b,aa,ab,ba,bb,…，因此可数。

第二问假设全部语言能列成L1,L2,…，串列成s1,s2,…。造D，使 $s_i\in D\iff s_i\notin L_i$。对任何i，D与Li在第i个串处恰好相反，因此D不是列表中任何语言，却仍是Σ上语言，矛盾。自取前三行对角成员位为1、0、1时，D对应位为0、1、0；其余位同样逐项定义，有限示例仅展示反转规则。

第三问TM是有限转移表，可编码成有限串，所以机器集合可数；每台机器识别至多一个语言，可被识别的语言至多可数，而全部语言不可数，因此必有不可识别者。不是说每种语言对应唯一机器；许多机器可以识别同一语言，这只使可识别语言更少。

补充（原题边界）：结论2、3需要字母表非空。课程通常把alphabet定义为有限非空集合；若字面允许Σ=空集，则Σ星仅{λ}，其幂集只有两个成员，谈不上不可数。原题只写finite时应补明采用课程的非空惯例。可数性证明只说明存在不可识别语言，并未由此给出某个具体语言的判定过程。

回到正文：HW05-2025T1-题目.pdf Q4

A2 作业/往年题演练（非讲义内容）：自然数对可数与幂集不可数

题面块（Final-Exam-2024T1-题目.pdf（本地课件） · Q8 · p.1；期末-2024未核-资料包.pdf（本地课件）同题）：

p.1 Recall that the union of two countable sets is also countable. Prove that the set ℕ × ℕ is countable, where ℕ is the natural set.

采用自然数从0开始的约定，按两坐标和s逐层枚举：(0,0)；(0,1),(1,0)；(0,2),(1,1),(2,0)；依此类推。任意(i,j)在有限层s=i+j出现，各层有限、层次有序，因此给出一个覆盖全部且无重复的数列。具体编号可为 $(i+j)(i+j+1)/2+i$，从0编号，层前共有三角数项。若自然数从1开始，将两坐标先减1再用同一构造。仅引用“两可数集之并可数”不能直接跳到无限并而不解释，本题的逐层枚举补上了可操作的次序。

题面块（Final-Exam-2025T1-题目.pdf（本地课件） · Q7 · p.3）：

p.3 Prove that the power set: (a) [10 points] $\mathcal P(\mathbb N)$ is uncountable.

反设幂集能列A0,A1,…，定义D={n∈ℕ:n不属于An}。D是ℕ的子集，故假设中应等于某Ak。但看k：k在D当且仅当k不在Ak；如果D=Ak，就变成k在D当且仅当k不在D，矛盾。因此无这样的枚举。它不否认每个单独子集至多可数；不可数的是全部子集组成的集合。自取前3个对角位1、1、0，D的前3位0、0、1，保证逐行至少一处不同；后续无限行同理。

回到正文：自然数对可数与幂集不可数

来源与证据

历史版本考试证据（本次未重新读取全部试卷）：读了 HW01-2025T1-题目.pdf、HW01-2026T1-题目.pdf、HW02-2025T1-题目-更新.pdf、HW03-2025T1-题目.pdf、HW04-2025T1-题目.pdf、HW05-2025T1-题目.pdf、期中练习-含解答-学期待核.pdf、期末-2022T1-资料包.pdf、Final-Exam-2023T1-题目.pdf、Final-Exam-2024T1-题目.pdf、Final-Exam-2025T1-题目.pdf、期末-2023T1-资料包.pdf、期末-2024未核-资料包.pdf；未识别用途的 PDF：无

• 原件：L10-图灵机变体-资料包.pdf（本地课件），PDF p.56–124。

• 本次独立学习修订：核对本讲131页文本，并视觉复核 p.20、38、45、53、81、114、128、130–131。