一、函数和语言

在本课程里，我们讲探讨这样一个问题：

计算机能解决什么问题？

问题的定义

我们知道，计算机程序有输入和输出。

我们对研究的问题范围进行限定：

输入为二进制字符串，也就是 ${0, 1}^{*} = ⋃_{n \geq 0} {0, 1}^{n}$ 中的元素
输出为“是”或“否”，即 ${0, 1}$ 中的一个元素

集合的并：
${x} \cup {y} = {x, y} 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} = {ϵ}$
其中 $ϵ$ 表示长度为零的字符串（即空串）

我们管这类只有一个输出，且输出为“是/yes/true”或“否/no/false”的问题叫判定性问题（decision problems）。

如果输入包含多种符号，怎么办？

如果输入有 $k$ 种符号，那么我们可以用 ${0, 1}^{⌈ l o g k ⌉}$ 来表示每个符号。即我们可以把 $k$ 种符号构成的字符串 $S^{*} = {0, \dots, k - 1}^{*}$ 嵌入到 $({0, 1}^{⌈ l o g k ⌉})^{*}$ 中去。

例如，当 $k = 3$ ，有 ${0, 1, 2}$ 三种符号时：

0 \to 00 1 \to 01 2 \to 10

如果输出为多个 bits，怎么办？

将输出限制为“是、否”是一个相当严重的限制，很多我们感兴趣的问题不能简单地用“是、否”来回答。然而，理解判定性问题的可计算性常常是理解更一般问题的关键。

此外，如果输出为 $m$ bits，我们可以把问题分解为 $m$ 个判定性的子问题，每个子问题回答答案中的一个 bit。这样，我们就可以把更一般的问题转化为一组判定性问题。

函数和语言

布尔函数

一个输入都是长度为 $n$ 的字符串的判定性问题可以表示为以下的布尔函数：

f : {0, 1}^{n} \to {0, 1}

语言

任何判定性问题都可以用语言 $L$ 表示，其中

L \subseteq {0, 1}^{*}

也就是说，对任一 $n \geq 0$ ，语言 $L$ 中长度为 $n$ 的输入可由函数 $f : {0, 1}^{n} \to {0, 1}$ 判定，其中 $f (x) = 1$ 当且仅当 $x \in L$ 。当输入长度可取任意自然数时，我们可以用一系列的布尔函数 ${f_{n}}_{n \geq 0}$ 其中 $f_{n} : {0, 1}^{n} \to {0, 1}$ 来表示语言 $L$ 。

类似地，任一布尔函数的集合 ${f_{n}}_{n \geq 0}$ 也都有其对应的语言：

L = n \geq 0 ⋃ f_{n}^{- 1} (1)

所有语言 $L$ 和所有布尔函数的集合 ${f_{n}}_{n \geq 0}$ 之间存在一一对应。

一个例子

考虑这样一个语言

L = {x : x 仅由 1 组成} = {1}^{*} = {1^{n}}_{n \geq 0}

那么

L = {ϵ, 1, 11, 111, \dots}

f_{n} (x) = {10 (x = 1^{n}) (otherwise)

第一个“不可计算”结果

我们感兴趣的是，计算机能解决哪些问题。在了解了语言的概念，知道了我们可以把很多问题表示为语言后，我们不由得想问：所有这些表示特定问题的语言都可由计算机进行计算吗？

我们说一个语言 $L$ 是可计算的，如果可以用你最喜欢的编程语言（如 Haskell）编写一段程序，给定任一输入 $x \in {0, 1}^{*}$ ，经过有限时间的运行后，当且仅当 $x \in L$ 时输出 $1$ ，当且仅当 $x \neq \in L$ 时输出 $0$ 。下面，我们将从数量出发，得出我们的第一个结论。

字符串和语言的数量（基数）

如果一个集合只有有限个元素，则集合是有限的，否则是无穷的。

如果集合中的元素可以和正整数一一对应起来，则是可数的，否则是不可数的。例如，整数、有理数是可数的，实数是不可数的。不可数集合中元素的数量远远多于可数集合。

字符串的数量是可数的。即 ${0, 1}^{*}$ 是可数的。因为它是可数个有限集的并。

为了方便理解，对二进制字符串 $x$ ，可以把它对应到 $1 x_{2}$ 所表示的数，其中 $1 x_{2}$ 的意思是把 $1 x$ 看作是一个数的二进制形式。例如

ϵ \to 1_{2} \to 1 0 \to 1 0_{2} \to 2 1 \to 1 1_{2} \to 3 00 \to 10 0_{2} \to 4 \dots

所有语言的组成的集合 ${L : L \subseteq {0, 1}^{*}}$ 是不可数的。如果你熟悉集合论中关于基数的理论，你可以由 $2^{{0, 1}^{*}} = 2^{N}$ 看出它是不可数的。

下面我们用对角线法说明为什么所有语言组成的集合是不可数的：

	$ϵ$	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；反之亦然。这样产生矛盾，因此原假设不成立。

定理：存在不可计算的语言

我们在前面已经通过语言的概念描述了判定性问题，即：我们可以用语言来表示判定性问题。通过分析字符串和语言的基数，我们可以得出本课程中的第一个结论：存在不可计算的语言。

存在不可用 Haskell（或者任何你喜欢的编程语言）计算的语言，即，存在语言 $L \subseteq {0, 1}^{*}$ ，不存在一段 Haskell 程序，给定输入 $x \in {0, 1}^{*}$ ，经过有限的时间运行后输出 $1$ 当且仅当 $x \in L$ 。

由于 Haskell 程序可以表示为二进制字符串（只需取程序代码的 Unicode 编码），所以合法的 Haskell 程序只是可数集 ${0, 1}^{*}$ 的子集。然而，所有语言的集合是不可数的，所以必然存在语言无法找到其对应的字符串，也就无法用 Haskell 程序计算。

可计算语言的数量为可数无穷多。

遗憾的是，绝大多数语言 $L \subseteq {0, 1}^{*}$ 都是不可计算的。这是因为 ${0, 1}^{*}$ 中子集的数量太多了，远超过编程语言能定义的程序的数量。下一节课，随着对图灵机的学习，我们将介绍一些具体的不可计算的语言，这些语言无法被任何计算机或编程语言计算。

课后练习

简要说明为什么可计算语言的数量为可数无穷多。

其他

订阅课程

订阅课程后可以及时收到开课通知。

日历链接: https://outlook.live.com/owa/calendar/00000000-0000-0000-0000-000000000000/6402f78a-8c81-4f83-91e7-f2ae343077ee/cid-D8FD15B2A646FB32/calendar.ics

以 Outlook 为例，登录后进入日历，点“添加日历”，然后选择“从网络订阅”，粘贴链接并导入。

完成之后开启对应日历的通知功能，就可以及时收到开课提醒了！

一、函数和语言

问题的定义

函数和语言

一个例子

第一个“不可计算”结果

字符串和语言的数量（基数）

定理：存在不可计算的语言

相关知识

课后练习

其他

订阅课程

课程讨论群