CSCI3130 T07 · Part 4 可数与不可识别

课程：CSCI3130 · 2025T1 本讲：第4部分 / 共4部分 · T07-2025T1.pdf（本地课件） p.11–12 定位：完整区分可枚举字符串、不可数语言族和有限描述的机器。 前后：上一份 Part 3 承接：#L10-09 枚举、#L10-10 对角化、#L10-11 不可识别语言

串可数，串集合的集合不可数（p.11–12）【已会】

p.11导航，p.12题面与解答。

题面块（T07 · Problem 4 · PDF p.12；公式按讲义重排）：

p.12 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时应补明采用课程的非空惯例。可数性证明只说明存在不可识别语言，并未由此给出某个具体语言的判定过程。

原解第一问的集合式为 $\Sigma^*=\bigcup_{n=0}^{\infty}\Sigma^n$。每层大小 $|\Sigma|^n$ 有限，n=0层是{λ}；按层连接这些有限列表，就是正文给出的可数枚举。它避免了纯字典序 λ,a,aa,aaa,… 一直不到 b 的问题。

不可数的是候选语言的总集合（补充）

每一个单独语言 $L\subseteq\Sigma^*$ 都至多可数，因为它是可数串集的子集。但把所有这样的子集作为对象收集起来，$\mathcal P(\Sigma^*)$ 不可数。自取一元字母表 {a}，串仍可列为 λ,a,aa,…；一个语言相当于对这列每个位置选择“收/不收”，即一条无限0/1成员序列。不同的无限选择构成不可数多的语言，字母种类只有一个也不妨碍该结论。

机器编码论证还有一个方向细节：每台机器确定一个接受语言，所以从机器到语言是函数，但并不要求它是单射。同一语言有多台机器，只会让可识别语言的数量更少。不能反过来说“每个语言都有一个有限描述，只是尚未找到”：绝大多数子集根本不在有限程序所能识别的范围内。

本讲核心考点

• 对角语言与列表第i项在第i个串上不同；非空字母表是边界条件（p.11–12，C 级）。

附录

正文包含本辅导原题的完整推导；图像页已目视核对，不采用手写作答作答案依据。

来源与证据

历史版本考试证据（本次未重新读取全部试卷）：读了 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：无

• 原件：T07-2025T1.pdf（本地课件），PDF p.11–12。

• 本次独立学习修订：核对对应辅导原件全部文本与本篇题面，保留完整规则、转移与证明。视觉复核物理页7、10的全部转移。