计算理论笔记

计算理论导引

Michael Sipser 著

三个核心领域：自动机、可计算性、复杂性

🍨 证明的类型

构造性证明：许多定理说明存在一种特定类型的对象。证明这种定理的一个方法是说明如何构造这样的对象。这种技术就是 构造性证明。

反证法：假设定理为假，然后证明此假设导致了一个明显错误的结论，即矛盾。

归纳法：归纳法是证明无穷集合的所有元素都有一种特定性质的高级方法。

自动机与语言

正则语言

什么是计算机？现实的计算机相当复杂。为了易于处理问题，我们采用称作 计算模型 的理想计算机。和科学中的任何模型一样，每种计算模型可能准确刻画了一些情况，但在另一些情况可能是不准确的。根据想要关注的特性，我们将采用几种不同的计算模型。最简单的叫有穷状态机或有穷自动机。

有穷自动机

有穷自动机是关于存储量极其有限的计算机的很好的模型。这么小的存储能做什么？能做很多有用的事情！事实上，它们广泛用于各种机电设备。如自动门有两个状态记录开关情况，然后根据前后是否有人来决定状态转换。

有穷自动机和它们的对照物 马尔科夫链 在识别数据中的模式时是有用的。这类装置用在语音处理和光学字符识别中。马尔科夫链甚至已经被用来对金融市场的价格变化进行建模和预测。

定义 有穷自动机 是一个5元组 $（Q,\Sigma,\delta,q_0,F ）$，其中

1）$Q$ 是一个有穷集合，叫做状态集。

2）$\Sigma$ 是一个有穷集合，叫做字母表。

3）$\delta:Q\times\Sigma\to Q$ 是转移函数。

4）$q_0\in Q$ 是起始状态。

5）$F\subseteq Q$ 是接受状态集。

设 A 是机器 M 接受的全部字符串集，称 A 是机器 M 的语言，记作 $L(M)=A$。又称 M 识别 A 或 M 接受 A。

由于在说机器接受字符串和机器接受语言时接受一次有不同的涵义，所以我们对语言倾向于使用识别二字以避免混淆。

一台机器可能接受若干字符串，但是它永远只能识别一个语言。如果机器不接受任何字符串，那么它仍然识别一个语言，即空语言 $\emptyset$。

定义 如果一个语言被一台有穷自动机识别，则称它是 正则语言。

正则运算： 设 A 和 B 是两个语言，定义正则运算 并、联结 和 星号 如下：

• 并：$A\cup B={x|x \in A 或 x \in B}$

• 联结：$A\circ B={xy|x\in A 且y\in B}$

• 星号：$A^*={x_1x_2\cdots x_k|k\ge0且每一个x_i\in A}$

正则语言类在3种正则运算下封闭。

两个正则语言的并也是正则语言：因为两个正则语言对应两台有穷自动机，我们需要构造一台新的来识别新语言。这台新的有穷自动机的状态数可以是之前两台状态数的乘积。（可以类似证明在交运算下也封闭）

为了证明在联结运算下封闭，假设 M1 识别 A1，M2 识别 A2，设计 M 的一大难点是 M 不知道在什么地方把输入分开（即，在什么地方第一段结束和第二段开始）。为了解决这个问题，我们引入所谓 非确定性 的新技术。

🍬 非确定性： 在非确定型机器中，在任何一点，下一个状态可能存在若干选择。

确定型有穷自动机（DFA）和非确定型有穷自动机（NFA）的区别显而易见。NFA 的一个状态对于某个符号可能有多条射出的箭头（也可能是0条），标号也可能不是字母表中的符号，而是 $\varepsilon$。NFA 进行计算时，遇到多个分支时就进行“分裂”，同时向前推进（并行）。最后只要有一个被接受，则结果就是接受。

非确定型有穷自动机在几个方面是有用的。每一台 NFA 可以转换成一台等价的 DFA，而构造 NFA 有时比直接构造 DFA 容易。一台 NFA 可能比与它等价的 DFA 小得多，或者它的功能更容易理解。

确定型和非确定型有穷自动机识别相同的语言类。这个等价性既出人意料，又是很有用的。

如果两台机器识别相同的语言，则称它们是 等价 的。每一台非确定型有穷自动机都有一台等价的确定型有穷自动机。

构造的过程使用了 幂集 。如果说你在模拟 NFA 时使用了很多手指，那么每个时刻所有手指的状态就可以作为 DFA 的一个状态。

有了 NFA，证明 联结运算 和 星号运算 将变得很简单，这里不再赘述。

🍭 正则表达式： 算术中可以用加号乘号构造表达式，如 (5+3)×4。类似地，可以用正则运算符构造描述语言的表达式，称为 正则表达式。例如 $(0\cup1)0^*$ 。算术表达式的值是 32，而正则表达式的值是一个语言，比如这个表达式的值是由一个 0 或一个 1后面跟着任意个 0 的所有字符串组成的语言。和代数中省略乘号一样，这里也经常省流联结符号。优先级最高是星号，其次是联结，最后是并运算。除非用括号改变顺序。

正则表达式和有穷自动机是等价的。

🍟 非正则语言： 要了解有穷自动机的能力，你必须同时了解它们的局限性。有些语言不可能用有穷自动机识别，如 $B={0^n1^n|n\ge0}$。

值得小心的是，有些看起来需要“无限存储”的语言其实是正则的，如 $C={\omega|\omega中0和1的个数相等}$

证明非正则性的技术源于一个关于正则语言的定理，通常把它称作 泵引理。定理指出所有正则语言都具有 泵性质：

语言中的所有字符串只要长度不小于某个特定的值——泵长度,就可以被“抽取”。它的意思是每一个这样的字符串都包括一段子串，把这段字串重复任意次，得到的字符串仍在这个语言中。

如果能够证明一个语言没有这种性质，则保证它不是正则的。

泵引理： 设 A 是一个正则语言，则存在一个数p（泵长度）使得，如果 s 是 A 中任一长度不小于 p 的字符串，那么 s 可以被分成 3 段，s=xyz，满足

1）$对于每一个i\ge0,xy^iz\in A$

2）$|y|>0$

3）$|xy|\le p$

思路是如果把 p 选为状态数，不难发现长度不小于 p 的字符串至少会经过 p + 1 个状态。其中肯定有环。

为了使条件3 成立，我们确保选择的重复状态是序列中第一个重复状态。根据鸽巢原理，序列的前 p + 1 个状态中肯定有重复，因此 $|xy|\le p$。

上下文无关语言

上下文无关文法 是一种能力更强的描述语言的方法。能够描述某些具有递归结构的特征。首先被用来研究人类语言。名词短语可以出现在动词短语之中，反之亦然。上下文无关文法的一个重要应用是程序设计语言的规范说明和编译。设计人员在编写程序设计语言的编译程序和解释程序时，常常是首先获取该语言的文法。

大多数编译程序和解释程序包含一个语法分析器，它在生成编译代码或完成解释执行前，提取程序的意思。只要能使用上下文无关文法，就有若干套方法使得构造语法分析器的工作变得很容易。某些工具甚至能从文法自动地生成语法分析器。

与上下文无关文法有关的一类语言叫做 上下文无关语言（Context-Free Language）。它们包括所有的正则语言以及许多新添加的语言。如 $G_1$:
$$
A\to0A1\
A\to B\
B\to #
$$
一个文法由一组 替换规则 组成，替换规则又叫产生式。

产生的所有字符串构成该文法的 语言。

设计上下文无关文法（Context-Free Grammar）： 可以考虑把复杂的文法拆成多个部分，每个部分分别设计，再加入一个规则 $S\to S_1|S_2\cdots $

其次，如果这个语言碰巧是正则的，可以先构造 DFA，再构造 CFG（上下文无关文法） 就容易了。把每个状态设为一个变元即可。

下推自动机

这种机器很像非确定型有穷自动机，但是它有一个额外的设备，叫做栈。栈在控制器的有限存储量之外提供了附加的存储，使得下推自动机可以识别某些非正则语言。下推自动机的能力与上下文无关文法等价。所以在证明一个语言是上下文无关的时候，可以给出它的上下文无关文法，或者给出识别它的下推自动机。

下推自动机（Pushdown Automaton，PDA）可以把符号写到栈上，然后再读它。写一个符号，然后把栈中其他所有符号“下推”。也可以进行“弹出”。栈能保存的信息量没有限制。

下推自动机可以是非确定性的。与有穷自动机不同，非确定性会带来额外的能力。

下推自动机多一个 栈字母表。转移函数的输入是当前状态、当前输入符号和栈顶符号三个。当前输入符号和栈顶符号可以为空，意味着机器能够在不读输入符号或栈顶符号的情况下做动作。

每一个正则语言都是上下文无关语言

非上下文无关语言

每一个上下文无关语言都有一个特殊的值，叫做 泵长度，使得这个语言中所有长度等于或大于这个值的字符串都能被 抽取。这一次抽取的意思要复杂一些，它是指字符串能被划分成 5 段，其中第 2 段和第 4 段可以同时重复任意次，并且所得到的字符串仍然在这个语言中。

1）对于每一个 $i$，$uv^ixy^iz\in A$

2）$|vy|>0$

3）$|vxy|\le p$

可计算性理论

丘奇-图灵论题

前面介绍的有穷自动机和下推自动机都有很多局限性，不能作为计算机的通用模型。

图灵机，由图灵在1936年第一次提出，与有穷自动机相似，但图灵机有一个无限的存储。图灵机是一种精确得多的通用计算机模型，能做实际计算机能做的所有事情。

然而也存在图灵机不能解决的问题，事实上，这些问题已经超出了计算的理论极限。

图灵机模型用一个无限长的带子作为无限存储，它还有一个读写头，这个读写头能在带子上读、写和移动。开始时，带子上只有输入串，其他地方都是空的。为了读已经写下的信息，它可能将读写头往回移动。机器不停地计算，直到产生输出。机器事先被设置了两种状态：接受或拒绝状态。如果进入这两种状态，就立即产生输出 接受 或 拒绝。如果不进入这两种状态，就继续执行下去，永不停止。

图灵机计算时，当前状态、当前带内容和读写头当前位置都会发生改变，这三项构成的整体叫做图灵机的 格局。

如果图灵机能合法的从格局 $C_1$ 一步进入 $C_2$，则称格局 $C_1$ 产生 $C_2$。

当读写头处于左端点，左移不会离开纸带，保持原地不动。右端点的右侧默认都是空格，或者说没有真正的右端点。

对于图灵机 M ，如果一个字符串能让它从起始格局合法走到接受格局，就说它接受这个输入。M 接受的字符串的全体称为 M 的语言，记为 L(M)。

如果有图灵机识别一个语言，则称该语言是 图灵可识别 的。（有些课本称为 递归可枚举语言）

在输入上运行一个 TM 时，可能出现三种结果：接受、拒绝或循环。这里 循环 仅仅指机器不停机，而不一定如字面那样永远重复相同步骤。循环动作可能是简单的，也可能是复杂度，但都不会导致停机状态（接受状态和拒绝状态都是 停机状态）。

对于一个输入，图灵机有两种方式不接受它：一种是进入拒绝状态而拒绝它，另一种是进入循环。有时候，很难区分机器是进入了循环还是需要耗费长时间运行。因此，我们更喜欢对所有输入都停机的图灵机，它们永不循环。称这种机器为 判定器 。也称某个语言的判定器 判定 该语言。

称一个语言是 图灵可判定的，或简单地讲，是 可判定的，如果有图灵机判定它。

图灵可判定语言都是图灵可识别的，但某些图灵可识别语言不是可判定的。

图灵机的变形

其他形式的图灵机还有很多，例如有多个带子的或非确定性的。它们被称为图灵机模型的 变形。原来的模型与它所有合理的变形有着同样的能力——识别同样的语言类。虽然它们的定义有了变化，但它们的能力却没有改变，这种变化中的不变性称为 稳健性。

一个可以允许读写头不移动的图灵机会更强大吗？不会。我们可以把之前的图灵机改为先向右后向左移动。这个例子告诉我们证明各种变形图灵机间的等价性的一个关键——为了证明两个模型是等价的，只要证明它们能互相模拟即可。

多带图灵机 有多个带子，每个带子有自己的读写头。每个多带图灵机都有一个与之等价的单带图灵机。 可以设想在带子上的字母上加标记来模拟多个读写头的位置。

非确定型图灵机 在任何时刻，机器可以在多个可能性中选择一种继续进行。可以用三条带子的图灵机来模拟。第一条保留原始输入。第二条每次复制一份原始输入。第三条记录每一次的分支选择。

枚举器 。有人用 递归可枚举语言 来代指图灵可识别语言。这个术语起源于称为 枚举器 的机器，它也是一种图灵机的变形。粗略地说，枚举器是带有打印机的图灵机，图灵机将打印机当作输出设备，从而可以打印串。每当图灵机想在打印序列中增加一个串时，就把此串送到打印机。

枚举器以空白输入带开始运行，如果不停机，它可能会打印出串的一个无限序列。枚举器 E 所枚举的语言是最终打印出的串的集合。枚举器可能以任意顺序生成这个语言中的串，还可能有重复。

定理 一个语言是图灵可识别的，当且仅当有枚举器枚举它。

这些图灵机的变形都有图灵机的本质特征——可以无限制地访问无限的存储器。

已经证明，有此特点的所有模型在能力上都是等价的，只要满足一些合理的必要条件（如 在一步中只能执行有限的工作量）

算法的定义

非形式地说，算法是为实现某个任务而构造的简单指令集 。

虽然算法在数学中历史很长，但在 20 世纪之前，算法的概念本身一直没有精确的定义。当时数学家对下列问题只有直观的认识：什么是算法？在使用和描述算法时应依赖什么？这种直观认识对深入理解算法是不够的。

希尔伯特问题 1900 年，数学家希尔伯特提出了 23 个数学问题，第 10 问题就是关于算法的。

该问题要设计一个算法来测试多项式是否有整数根。他没有用 算法 这个术语，而是说 “通过有限多次运算就可以决定的过程”。有意思的是，看这个描述，希尔伯特是想要一个算法，他假设这样的算法是存在的，人们只是要找到它。现在我们知道，这个任务没有算法，它是算法上不可解的。

直观的概念或许可以用来寻找一些算法，但若将之用于证明某个特定任务不存在算法，就毫无用处了。证明算法不存在需要给出算法的明确定义。

在丘奇和图灵于 1936 年写的文章中，这样的定义终于出现了。丘奇使用称为 λ-演算 的记号系统来定义算法，图灵使用机器来做同样的事。

1970 年，人们终于证明检查多项式是否有整数根的算法是不存在的。现在用新的术语来重新陈述这个问题：
$$
D={p|p是有证书根的多项式}
$$
本质上，希尔伯特第 10 问题是问：集合 D 是不是可判定的？答案是否定的。

可判定性

可判定语言

与正则语言相关的可判定性问题： 如 DFA 接受问题，检测一个特定的自动机是否接受一个事先给定的串，此问题可以表示成语言 $A_{DFA}$，它包含了所有 DFA 及其接受的串的编码。问题 DFA B 是否接受一个输入ω，就是在问 <B，ω> 是否是语言 $A_{DFA}$ 的元素。

$A_{DFA}$ 是可判定的，也就是说“一个给定的有穷自动机是否接受一个给定的串是可判定的”。

定理：检查一个 DFA 是否不接受任何串是可判定的。

定理：检查两个 DFA 是否识别同一个语言是可判定的。可以构建对称差，用上个定理判断对称差是否为空。

但是，证明两个上下文无关文法是否派生同一个语言的问题是不可判定的。

停机问题

什么样的问题是计算机不能解的呢？是不是那些很深奥的问题呢？不，已经证明，一些人们非常希望解决的普通问题都是计算上不可解的。

不可解问题之一是：假设你有一个计算机程序，还有一个说明书说明了程序将做什么（例如分类串），你想要验证说明书是否正确。一般的软件验证问题用计算机是不可能解决的。

现在介绍第一个不可解性定理：检查一个图灵机是否接受一个给定的串问题。

有着不可数的语言，但只有可数的图灵机，所以有些语言是不可判定的，甚至是不可识别的。

现在证明下列语言是不可判定的
$$
A_{TM} = {<M,\omega>|M是一个TM,且M接受\omega}
$$
证明：假设其可判定，设 H 是判定器。令 M 是一个 TM，ω 是一个串，在输入 $<M,\omega>$ 上，如果 M 接受 ω ，则 H 停机且接受 ω ；如果 M 不接受 ω ，则 H 也会停机，但拒绝 ω 。

现在来构造一个新的图灵机 D，它以 H 作为子程序，当 M 被输入它自己的描述 <M> 时，TM D 就调用 H，以了解 M 将做什么。一旦得到这个信息，D 就反着做，即：如果 M 接受，它就拒绝，如果 M 不接受，它就接受。下面是 D 的描述：

D = “ 对于输入 <M>，其中 M 是一个 TM：

1）在输入 <M, <M>> 上运行 H

2）输出 H 输出的相反结论，即，如果 H 接受，就拒绝，如果 H 拒绝，就接受。

当以 D 的描述 <D> 作为输入来运行 D 自身时，会发生什么呢？我们得到
$$
D()={接受, 如果D不接受;拒绝， 如果D接受}
$$
这是矛盾的，多以 TM D 和 TM H 都不存在。

如果用对角化来思考，可以把图灵机放在列，它们的描述放在行，图灵机对它的判定结果为接受或不接受，作为表格元素。由于 D 也是图灵机，它也会出现在一行。它的这一行元素，就是对对角线元素的取反。这时，它遇到它自己的描述就会出现问题。

定理 如果一个语言和它的补都是图灵可识别的，则此语言也是可判定的。因此，任何不可判定的语言，它或它的补至少有一个不是图灵可识别的。一个语言的补是由不在此语言中的所有串所构成的语言。如果一个语言是一个图灵可识别语言的补集，则称它是 补图灵可识别的。

定理 一个语言是可判定的，当且仅当它既是图灵可识别的，也是补图灵可识别的。

一个图灵不可识别的语言 所以，$A_{TM}$ 的补不是图灵可识别的。