Theory of Computation ReView

计算的要义就是在有限步内找到准确的解。

读书就是在识词，了解定义，尤其是形式化的那些。

Chapter One 正则语言

Q: 为什么大多数计算模型是受限的

有穷自动机

是状态集，是字母表， ,是起始状态, 是接受状态集

特别的， 包含每一个状态与每一个字母对应的转化。

语言

若A是机器M接受的全部字符串集，则称A是机器M的语言，记作L(M)=A,又称M识别A。一台机器可能接受若干字符串，但只会接受一个语言。

正则语言

如果一个语言被一台有穷自动机识别，则称它是正则语言(Regular Language).

计算

设是一台有穷自动机，是一个字符串并且其中任意是字母表的成员，若存在Q中的一个状态序列满足下述条件：

则称M接受w。

正则运算

设和是两个语言，我们可以定义得到正则运算并(union)，连接(concatenation)和星号(star)。

需要注意，正则运算的定义对象是语言即自动机。进一步证明了正则语言类在正则运算下的完备性，通过连接运算部分证明的困难引出了非确定性。

非确定型有穷自动机

Q是状态集，是字母表，是起始状态, 是接受状态集

引入非确定型有穷自动机后，我们可以轻易证明正则语言类在正则运算下的封闭性。

DFA与NFA的等价性

考虑基于NFA 构建一个新的DFA , 的状态集，即可完成所有模拟。 相应的，我们构建出了。

• 从R出发沿着0个或多个 箭头可以到达q
• 包含的一个接受状态

一个语言是正则的，当且仅当有一台非确定型有穷自动机识别他。

正则表达式

称R是一个正则表达式，若R是：

4. 都是正则表达式
5. 都是正则表达式
6. 是正则表达式

正则表达式与NFA的等价性以及NFA向正则表达式的转化

一个语言是正则的，当且仅当可以用正则表达式描述它。

如果一个语言可以用正则表达式描述，则它是正则的。

该引理的证明是显然的，该引理的过程就是从正则表达式向NFA的转化。

如果一个语言是正则的，则可以用正则表达式描述它。

该引理的过程就是从NFA向正则表达式转化的过程，详见Page:42。

非正则语言

若A是一个正则语言，则存在一个数p(泵长度)使得，如果s是A中任一长度不小于p的字符串，那么s可以被分成三段，s=xyz，满足下述条件：

1.对每一个

证明思路：其中p=自动机状态数，因为s长度不小于p，，若能计算，则计算历史为长度一定大于自动机状态数，根据，一定至少。

特别地，只能用泵引理证明语言不是正则的，若需证明语言是正则的，需找到相应的正则表达式。

Chapter Two 上下文无关文法

上下文无关文法

上下文无关文法是一个四元组,且：

1. 是一个有穷集合，称为变元集。
2. 是一个与不相交的有穷集合，称为终结符集。
3. 是一个有穷规则集。
4. 是起始变元。

歧义性

如果字符串在上下文无关文法中有两个或两个以上的最左派生，则称G歧义地产生某个字符串，则称G是歧义的。

某些上下文无关语言只能用歧义文法产生，称这样的语言为固有歧义的。

Chomsky Normal Form

称一个上下文无关文法为Chomosky Normal Form，如果它的每一个规则具有如下形式:

下推自动机

六元组，其中都是有穷集合。

1. 是状态集。
2. 是输入字母表。
3. 是栈字母表。
4. 是非确定性的转移函数。
5. 是起始状态。
6. 是接受状态集。

PDA 的计算过程

PDA接受输入，若存在状态序列,和字符串序列 ，满足下述条件:

1. ，该条件表示从起始状态和空栈开始。
2. 对于有其中
3. ，该条件说明在输入结束时出现一个接收状态。

非确定性PDA与CFL的等价性

1. 如果一个语言是上下文无关的，则存在一个下推自动机识别它。

$eg. S abSxy (q,a,S)={(q_1,)},(q_1,b,)={(q_2,)},(q_2,,)={(q_3,y)},\(q_3,,)={(q_4,x)},(q_4,,)={(q,S)}$

2. 如果一个语言被一台下推自动机所识别，则它能被CFG 派生。

使用变元代表从的p状态及空栈，转移到q状态以及空栈所派生的字符串。则：

• , if

非上下文无关语言

如果是上下文无关语言，则存在数p（pumping length），使得中任何一个长度不小于p的字符串都能被划分成5段，使得：

1. 对每一个

有一个显然的例子， 是因为使用泵引理进行分析，发现都不能含有两种符号，不然会发生顺序错乱，但若仅含有一种符号，又不能保证三种字母的数量相同。

Chapter Three 丘奇-图灵论题

图灵机是一个7元组，其中都是有穷集合，且：

1. 是状态集。
2. 是输入字母表，不包括特殊空白符号
3. 是带子字母表，其中
4. 是转移函数
5. 是起始状态
6. 是接受状态
7. 是拒绝状态

格局 Configuration

显见，上文所定义的图灵机仅有三个自由度，分别是当前状态，当前带子内容和当前读写头位置。故此，这三者组合在一起称为图灵机的格局，对于状态，和状态字母表上的两个字符串，以代表如下格局：当前状态是q，当前带子内容是uv，读写头的当前位置是v的第一个符号。

对于任意输入，图灵机有三种可能的表现：接受，拒绝及循环，其中我们认为拒绝和循环都是不接受。若某图灵机对所有字符串要么接受，要么拒绝（有限时间内给出结果）则称该图灵机为判定器。

如果一个语言能被某一图灵机识别，则称该语言是图灵可识别的(Turing-recognizable)。

如果一个语言能被某一图灵机判定，则称该语言是图灵可判定的(Turing-decidable)。

非确定型图灵机

等价性

等价于确定型图灵机：我们可以使用一个确定性图灵机广度优先搜索的模拟一台非确定型图灵机。

已经证明：任何可以无限制地访问无限的存储器，且在一步中只能执行有限的工作量的计算模型的能力都是等价的。

算法的定义

希尔伯特第10问题：通过有限多次运算决定一个多项式方程有没有整数根。

是否是图灵可判定的。

既然算法是用图灵机定义的，实则每个图灵机也对应一个被准确形式化描述的算法。

Chapter Four 可判定性

不可判定性

是不可判定的。

不可识别性

存在不能被任何图灵机识别的语言。

图灵机的个数是可数的，因为构成其的都是有穷集合。但要识别的语言是不可数的，字符串个数为不可数，对应产生的语言为。

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

1. 语言是可判定的补是图灵可识别的。

2. 它和它的补是图灵可识别的语言是可判定的。

Chapter Five 可归约性

如果A可归约到B，就可以用B的解来解A。说明解B的难度比解A更大。

当A可归约到B时，如果B是可判定的，则A是可判定的。如果A是不可判定的，则B是不可判定的。

映射可归约性

可计算函数

如果存在一个判定器，对于函数，使得在每一个输入上都接受，且只有留在带子上。

映射可归约性

归约性的一种定义。

语言是映射可归约到语言的，如果存在可计算函数使得对每个:。记作。

特别的，在用于证明非图灵可识别过程中，有一个典型手段。

如果，且不是图灵可识别的，则也不是图灵可识别的。

而一个标志性的非图灵可识别的例子是，而可知，所以为证明非图灵可识别，可证。

Chapter Six 可计算性理论的高级专题

递归原理

Chapter Seven 时间复杂性

复杂性的度量

设是两个函数，。称，若存在正整数和，使得对所有有： 当时，称的上界，或更准确的说，渐进上界。

令是一个函数，定义时间复杂性类为由时间的图灵机判定的所有语言的集合。

设是一个函数，$t(n)n t(n)O(t^2(n))t(n)$时间的非确定性单带图灵机都与某一个时间的确定性单带图灵机等价。

P类问题

P是确定型单带图灵机在多项式时间内可判定的语言集。换言之，。

其重要性在于：

• 对于所有与确定型单带图灵机多项式等价的计算模型来说，P是不变的。
• P大致对应于在计算机上实际可解的那一类问题。

NP类问题

语言A的验证机是一个算法V，这里 ，多项式时间验证机在的长的的多项式时间内运行。若语言A有一个多项式时间验证机，则称他为多项式可验证的。

NP是具有多项式时间验证机的语言类。

NP-Complete

多项式时间可归约性

若存在多项式时间图灵机，使得在任何输入上，停机时恰好在带子上，则称为多项式时间可计算函数。

语言A称为多项式时间可归约到B，记为，若存在多项式时间可计算函数，对于每个都有，函数称为到的多项式时间归约。

如果语言B满足下面两个条件，就称为NP完全的：

库克-列文定理

SAT是NP完全的。

使用SAT可以模拟得到，其公式。

Appendix

Turing Machine Encoding

$ Encode_{Beginning} = 0ⁱ¹⁰j10^k10m10ⁿ¹⁰r10^t i=|Q|$, ,, Blank Symbol is

. Where for each transition function:

where