# 一、函数和语言 在本课程里，我们讲探讨这样一个问题： **计算机能解决什么问题？** ## 问题的定义 我们知道，计算机程序有输入和输出。 我们对研究的问题范围进行限定： * 输入为二进制字符串，也就是 $\{0,1\}^{*}=\bigcup_{n\geq 0}\{0,1\}^{n}$ 中的元素 * 输出为“是”或“否”，即 $\{0,1\}$ 中的一个元素 > 集合的并： > > $$ > \{x\}\cup\{y\}=\{x,y\} \\ > \bigcup_{n\geq 0}\{0,1\}^n=\{0,1\}^0\cup\{0,1\}^1\cup\{0,1\}^2\cup\dots > $$ > > 笛卡尔积： > > $$ > \{a,b\}\times\{c,d,e\}=\{(a,c),(a,d),(a,e),(b,c),(b,d),(b,e)\} \\ > \{0,1\}^2=\{0,1\}\times\{0,1\}=\{00,01,10,11\} \\ > \{0,1\}^3=\{000,001,010,011,100,101,110,111\} \\ > \{0,1\}^0=\{\epsilon\} > $$ > > 其中 $\epsilon$ 表示长度为零的字符串（即空串） :::info 我们管这类只有一个输出，且输出为“是/yes/true”或“否/no/false”的问题叫**判定性问题（decision problems）**。 ::: **如果输入包含多种符号，怎么办？** 如果输入有 $k$ 种符号，那么我们可以用 $\{0,1\}^{\lceil\log k\rceil}$ 来表示每个符号。即我们可以把 $k$ 种符号构成的字符串 $S^*=\{0,\dots,k-1\}^*$ 嵌入到 $(\{0,1\}^{\lceil \log k\rceil})^*$ 中去。 例如，当 $k=3$，有 $\{0,1,2\}$ 三种符号时： $$ 0\rightarrow 00 \\ 1\rightarrow 01 \\ 2\rightarrow 10 $$ **如果输出为多个 bits，怎么办？** 将输出限制为“是、否”是一个相当严重的限制，很多我们感兴趣的问题不能简单地用“是、否”来回答。然而，理解判定性问题的可计算性常常是理解更一般问题的关键。 此外，如果输出为 $m$ bits，我们可以把问题分解为 $m$ 个判定性的子问题，每个子问题回答答案中的一个 bit。这样，我们就可以把更一般的问题转化为一组判定性问题。 ## 函数和语言 **布尔函数** 一个输入都是长度为 $n$ 的字符串的判定性问题可以表示为以下的**布尔函数**： $$ f:\{0,1\}^{n}\rightarrow\{0,1\} $$ **语言** 任何判定性问题都可以用**语言** $L$ 表示，其中 $$ L\subseteq\{0,1\}^{*} $$ 也就是说，对任一 $n\geq 0$，语言 $L$ 中长度为 $n$ 的输入可由函数 $f:\{0,1\}^{n}\rightarrow\{0,1\}$ 判定，其中 $f(x)=1$ 当且仅当 $x\in L$。当输入长度可取任意自然数时，我们可以用一系列的布尔函数 $\{f_n\}_{n\geq 0}$ 其中 $f_n:\{0,1\}^{n}\rightarrow\{0,1\}$ 来表示语言 $L$。 类似地，任一布尔函数的集合 $\{f_n\}_{n\geq 0}$ 也都有其对应的语言： $$ L=\bigcup_{n\geq 0}f_n^{-1}(1) $$ :::tip 所有语言 $L$ 和所有布尔函数的集合 $\{f_n\}_{n\geq 0}$ 之间存在一一对应。 ::: ### 一个例子 考虑这样一个语言 $$ L=\{x:x\text{~仅由~}1\text{~组成~}\}=\{1\}^*=\{1^n\}_{n\geq 0} $$ 那么 $$ L=\{\epsilon,1,11,111,\dots\} $$ $$ f_n(x)=\left\{ \begin{array}{ll} 1 & (x=1^n) \\ 0 & (\text{otherwise}) \end{array} \right. $$ ## 第一个“不可计算”结果 我们感兴趣的是，计算机能解决哪些问题。在了解了语言的概念，知道了我们可以把很多问题表示为语言后，我们不由得想问：所有这些表示特定问题的语言都可由计算机进行计算吗？ 我们说一个语言 $L$ 是**可计算**的，如果可以用你最喜欢的编程语言（如 Haskell）编写一段程序，给定任一输入 $x\in\{0,1\}^*$，经过有限时间的运行后，当且仅当 $x\in L$ 时输出 $1$，当且仅当 $x\not\in L$ 时输出 $0$。下面，我们将从数量出发，得出我们的第一个结论。 ### 字符串和语言的数量（基数） 如果一个集合只有有限个元素，则集合是有限的，否则是无穷的。 如果集合中的元素可以和正整数一一对应起来，则是可数的，否则是不可数的。例如，整数、有理数是可数的，实数是不可数的。不可数集合中元素的数量远远多于可数集合。 :::tip 字符串的数量是可数的。即 $\{0,1\}^{*}$ 是可数的。*因为它是可数个有限集的并。* ::: 为了方便理解，对二进制字符串 $x$，可以把它对应到 $1x_2$ 所表示的数，其中 $1x_2$ 的意思是把 $1x$ 看作是一个数的二进制形式。例如 $$ \epsilon\rightarrow 1_2\rightarrow 1 \\ 0\rightarrow 10_2\rightarrow 2 \\ 1\rightarrow 11_2\rightarrow 3 \\ 00\rightarrow 100_2\rightarrow 4 \\ \dots $$ :::tip 所有语言的组成的集合 $\{L:L\subseteq\{0,1\}^*\}$ 是不可数的。*如果你熟悉集合论中关于基数的理论，你可以由* $2^{\{0,1\}^*}=2^{\mathbb{N}}$ *看出它是不可数的。* ::: 下面我们用对角线法说明为什么所有语言组成的集合是不可数的： | | $\epsilon$ | 0 | 1 | 00 | 01 | 10 | … | |-----|----------|-----|-----|-----|-----|-----|-----| | $L_1$ | 0 | 0 | 0 | 0 | 0 | 0 | … | | $L_2$ | 1 | 0 | 1 | 0 | 1 | 0 | … | | $L_3$ | 0 | 1 | 1 | 0 | 0 | 0 | … | | … | … | … | … | … | … | … | … | 在上表中，每行表示一个语言，每列表示一个字符串。表格中 $0$ 值代表对应的字符串不属于对应语言，$1$ 代表对应的字符串属于对应语言。 假设所有语言组成的集合是可数的，也就是说，我们可以把语言与正整数一一对应起来。把对应到 $n$ 的语言记为 $L_n$。然后我们构造以下语言，从上表的对角线中选取字符串，若对角线上的值为 0，则将对应字符串包括在构造的语言中；反之则不包括。由于我们假设，语言都是可数的，那么我们应可以在表中找到我们构造的语言。不妨设我们构造的语言在第 $k$ 行，也就是我们构造的是 $L_k$。此时，若其第 $k$ 列为 1，按照定义，该字符串应该不在 $L_k$ 中，即其值应为 0；反之亦然。这样产生矛盾，因此原假设不成立。 ### 定理：存在不可计算的语言 我们在前面已经通过**语言**的概念描述了判定性问题，即：我们可以用语言来表示判定性问题。通过分析字符串和语言的基数，我们可以得出本课程中的第一个结论：存在不可计算的语言。 :::tip 存在不可用 Haskell（或者任何你喜欢的编程语言）计算的语言，即，存在语言 $L\subseteq \{0,1\}^*$，不存在一段 Haskell 程序，给定输入 $x\in\{0,1\}^*$，经过有限的时间运行后输出 $1$ 当且仅当 $x\in L$。 ::: 由于 Haskell 程序可以表示为二进制字符串（只需取程序代码的 Unicode 编码），所以合法的 Haskell 程序只是可数集 $\{0,1\}^*$ 的子集。然而，所有语言的集合是不可数的，所以必然存在语言无法找到其对应的字符串，也就无法用 Haskell 程序计算。 :::tip 可计算语言的数量为可数无穷多。 ::: 遗憾的是，绝大多数语言 $L\subseteq \{0,1\}^*$ 都是不可计算的。这是因为 $\{0,1\}^*$ 中子集的数量太多了，远超过编程语言能定义的程序的数量。下一节课，随着对图灵机的学习，我们将介绍一些具体的不可计算的语言，这些语言无法被任何计算机或编程语言计算。 ## 相关知识 在继续进行接下来的学习之前，我希望介绍一下，本课所涉及内容的应用等相关知识。本课程算是计算机科学和数学中非常基础的内容，以下方向与计算复杂度理论相关 **学完本课程之后，可以继续学习哪些内容？** * 算法：复杂度理论在算法中有重要应用，学完本课程后可以继续学习近似算法、随机算法等内容。 * 密码学：计算复杂度理论是密码学的重要基础。本课程将会简单地介绍，我们为什么认为一些密码学协议是安全的。 * 博弈论：$\textbf{PH}$ 类与博弈论当中的 Minimax 函数有一定关联。 需要注意的是，本课程更多地偏向理论，不包含数据结构等偏向实用的内容。 ## 课后练习 简要说明为什么可计算语言的数量为可数无穷多。 ## 其他 ### 订阅课程 订阅课程后可以及时收到开课通知。 日历链接: 以 Outlook 为例，登录后进入日历，点“添加日历”，然后选择“从网络订阅”，粘贴链接并导入。 完成之后开启对应日历的通知功能，就可以及时收到开课提醒了！ ### 课程讨论群 ![](https://minio.outline.bleatingsheep.org/outlinefixing/uploads/8682f6d2-0f23-4aae-b075-aa3805b8ee99/d3fbbd94-4b46-49a0-8dd0-d443c4d43144/qrcode_1716104244926.jpg?X-Amz-Algorithm=AWS4-HMAC-SHA256&X-Amz-Content-Sha256=UNSIGNED-PAYLOAD&X-Amz-Credential=460a9d18e7106f67%2F20261022%2Fcn-homelab-1%2Fs3%2Faws4_request&X-Amz-Date=20261022T034500Z&X-Amz-Expires=86400&X-Amz-Signature=7378ff23a1261c574772eb51fb0faf0274813c283657035c0f22a87266a6a5c7&X-Amz-SignedHeaders=host&x-amz-checksum-mode=ENABLED&x-id=GetObject " =280x498") --- **Documents** - [一、函数和语言](https://notes.bleatingsheep.org/s/complexity-theory/doc/5lia44cb5ye95pww5zkm6kt6kia-9vOx5Di3Qh)