[备考笔记] THEORY OF COMPUTATION

好课。本科大四的时候还主动选修了的课。老师高高的。挺帅。却挑了个实在不怎么好的时间上课。周一大早。我总醒不来，醒来了也想着去了反正迷糊还是多睡会养好精神下午好干活就又躺下了。然后转眼就要考试了。再看书，那些本科时不懂的依旧不懂。却又有些大四时备考数值分析时热血沸腾的感觉。

对那些曾经Make Me无比Confused的概念和理论一一罗列解析：

• 可数无穷Countably Infinite及对角化论证Diagonal Argument
  这是计算理论里第一个十分纠结的概念。可数无穷很难在脑子里成像，书上给出的定义是“可数无穷集合A与N之间存在一个双射f ”，也就是说，A的元素与N存在一一对应的关系。我们可以像数自然数一样枚举它，如果你活得像宇宙一样长，就可以永远抱着数完它的信心。
  Cantor的对角化原理可以用来证明某集合是不可数的，通常假设某集合是可数的，并罗列其与N间的双射关系为一列，那么若集合不可数，则可以按照对角原则构造一些元素，使其属于该集合但按照其构造规则不能被罗列。WIKI上给出了十分详细的证明，关于可数无穷集的幂集和实数的不可数问题。
  那么，我们可以对不可数无穷做以下描述：就是那些比可数无穷还要长的数列们，即使你活得像宇宙一样长，也还是放弃吧。
   
• 确定型有穷自动机DFA与非确定性有穷自动NDFA的等价
  等价，指的是其接受相同的语言。如果对于某类语言，有一台NDFA按照非确定的规则转换状态接受它，那么就存在一台DFA以NDFA每读入一段输入串后的可能状态集合为状态，按照确定的规则接受它。并且，这样的构造是指数的。
   
• 正则Regular与非正则语言以及泵定理Pumping Lemma
  正则语言可以用表达式写出来，可以被FA接受，其中可能用到组合字符串是可以穷举的；非正则语言是难以预料的，只能用文字来表述，比如根据前端决定后段的字符串。
  泵定理描述正则语言中某些字串可以被无限重复（Kleene）的特性，相应地，可以用来反证某些语言是非正则，即假设其正则，但举例一个带n的特殊字符串，其长度大于n，无论怎么分解为xyz，y≠e，|xy|≤n，但重复y段i次后得到的xy^iz不属于该语言。（PS：其实泵定理只对不可穷举且存在环的正则语言成立。）这里有两个技巧：第一是如何选一个特殊的字符串，a^nb^n、ww^r之类是最常想到的；第二是如何证明“无论怎么分解”，通常最简单的方法就是分情况讨论。当然，证明本身就带有艺术性，需要因地制宜。
  正则语言在并、连接、Kleene、补、交下封闭的，也可以此反证语言非正则，如交，使某语言与某正则语言相交得到非正则语言。将封闭性和泵定理结合，是一种比较方便的证明非正则的方法。
   
• 等价类和状态最小化
  一个正则语言的等价类为它本身、续尾后能被接受的字符串和续尾后不能被接受的字符串。
  状态间的等价，≡是说对于状态p和q，想要到达最终状态，要走的路是一样的（当然，走不通的路也是一样的）。带下标n的≡则是说如果只走n步或更少，那状态p和q是≡的。那么其实，≡就是≡下标∞。
  用状态最小化算法寻找FA的标准型状态，就是从下标0开始，不断分裂寻找等价状态（以相同的字符串走到终点），直到不可分。
   
• 下推自动机PDA的转移关系们
  ((p, a, β), (q, γ)) 当状态为p且输入带读入a且β在栈顶时，抛出β，推入γ，且转换状态为q；
  ((p, a, e), (q, b)) 当状态为p且输入带读入a时，推入b，且转换状态为q；
  ((p, a, b), (q, e)) 当状态为p且输入带读入a且b在栈顶时，抛出b，且转换状态为q；
  ((p, e, e), (q, e)) 当状态为p时，转换状态为q。
   
• 上下文无关语言Context-free与非上下文无关语言以及泵定理二世
  上下文无关语言CFL是一种可以从某一个种子开始向两边无限蔓延开的语言，生成什么字串只与文法相关，而与种子当前的上下文无关。
  泵定理二世基于语法分析树描述CFL中某些推导规则可被无限重复（S→aSb）的特性，可用来证明某些语言非上下文无关，即假设其上下文无关，但举例一个带n的特殊字符串，定义n与φ(G)之间的关系使得字符串长度大于φ(G)，分解为uvxyz，v≠e，y≠e，重复v、y段i次后得到的uv^ixy^iz不属于该语言。其技巧与泵定理一世大同小异。
  CFL在并、连接、Kleene下封闭，交和补下不封闭。CFL包含正则语言，其与正则语言的交仍是CFL。因此，也可用封闭性证明。
   
• Chomsky范式
  Chomsky范式要求每条规则的右边必须小于2，见wiki。普通CFL可按如下步骤转换为Chomsky范式：
  1. 对所有的结束字符串a，引入一个非借助状态A，增加规则A→a，那么X→a就变为X→A；
  2. 消去e规则：a) 寻找所有可能推导出e的状态集合Λ，包括X→e，Y→X，Z→XY；
                         b) 对所有含有n个属于Λ的状态的规则，替换为2^n条新规则，
                             如X→AYZBY，Y∈Λ替换为X→AYZBY、X→AZBY、X→AYZB和X又AZB；
                         c) 消去所有e规则。
  3. 分割所有长规则（右边大于2），如X→ABCD变为X→YD、Y→ZC和Z→AB。
  4. 消除规则中的单链，即若存在规则X→Y，而Y总是推出Z，且Z有规则Z→a，则替换X→Y为X→a。
  用动态规划的方法确定字符串是否能被某CFG输出，其前提是该CFG以备Chomsky化。
   
• 判定Decide与半判定Semidecide、递归Recursive与递归可枚举Recursively Enumerable、递归函数
  对于w∈L，图灵机M始终生成接受格局；对于w∈L，M始终生成拒绝格局。这时，就称M判定L，而L是递归的，即可判定的。若只满足前半部分，则称M半判定L，L是递归可枚举的，即可半判定的。
  对于所有w∈Σ*，有M(w)=f(w)，即M在输入w上停机并在带上写f(w)，称M计算f，f为递归函数。
  半判定的M不是算法。存在非递归的递归可枚举语言。
  如果一个问题和它的补都是递归可枚举语言，则其实递归语言。
   
• 几种扩展图灵机与标准图灵机间的等价性
  k带图灵机：标准图灵机M'将带形式化地分为2k条轨道（间隔排序），其中k条用来记录k带图灵机M相应条带上的信息，另k条来用来模拟带头的位置。M的t步，M'需要O(t*(|x|+t))步来完成，|x|为输入的长度。
  双向无穷带图灵机：可以用2带图灵机模拟，再推到标准图灵机，模拟花费线性时间，因为这种图灵机每步只有一条轨道是活动的。
  k带头图灵机：将标准图灵机的带形式化地分为k+1条轨道，1条用来记录信息，其余用于模拟带头的位置。那么，每步的模拟将带来两次扫描，一次确定带头位置，一次改变符号或移动带头。这样的模拟需要花费平方时间。
  非确定型图灵机：由于非确定性图灵机可能产生的格局是有限的，设最大为r，那么设计3带图灵机，第1条带存储输入w且永远不变使得每种计算可在相同的输入上重新开始，每一次计算按照{1, 2,.., r}*生成的顺序转移格局，第2条拷贝第1条的数据赞着第3条中记录的顺序模拟计算，两次模拟计算间生成新的顺序存储于第3条中。这样的模拟至多会在r+r^2+…+r^n次失败尝试后，才会产生对应NTM的选择。因此，这样的模拟需要花费指数级的时间。
   
• 通用图灵机对任意图灵机的模拟
  对任意一台图灵机M=(K, Σ, δ, s, H)，可以通过二进制编码的方式描述其所有的状态、符号和状态转移表。其每个状态表示为以q开头，长度为i，2^i≥|K|的二进制字符串；每个字符表示为以a开头，长度为j，2^j≥|Σ|+2（2为←和→符号）的二进制字符串。那么状态转移表就可表示为相应的多个二进制四元组，并以字典升序排列，如(q, a, s, a)表示为(q01, a100, q00, a100)。注意：停机状态不会出现在任意一个四元组的第一分量上，因此在四元组中搜不到的格局就是停机格局。
  那么，设计这样一种3带机器U'：初始化时，第1条带写入输入字符串w，第2条带写入上述形式描述的“M”（应该只是四元组集），第3条带写入q0^i（初始状态）。在每一步对M的模拟中，U'搜索第2条带直到发现“第一分量与第3条带相同”“第二分量与第1条带相同”的四元组。若发现，则“把第3条带上的状态改为第三分量”“完成第四分量编码的操作（写第1带或左右移）”；若未发现，即停机。
  最后，用标准图灵机U模拟U'，就得到了通用图灵机。
   
• 停机问题是递归可枚举的，但是非递归
  任何可以归约到停机问题的问题都是不可判定的，即没有算法。
   
• P类与NP类
  P类问题是存在确定型图灵机在多项式时间O(n^k)内能解决的问题；
  NP类问题是存在不确定型图灵机在多项式时间O(n^k)内能解决的问题，即确定性图灵机需要指数时间O(c^(n^k))。
  P类问题是NP类的子集。
  NP完全问题是最难的NP问题，所有NP问题都可以归约至它，也就是说，NP类等于P类，当且仅当NP完全问题属于P类。
   
   
  # 老师ppt上的两张图，很具象地表达了NP、P、停机问题、SAT、RE、RE补等之间的关系
   

• COOK定理Cook–Levin theorem
  Cook定理说，SAT（Boolean Satisfiability）是NPC问题。简单地说，如果对某一个布尔表达式B.E.，存在使其布尔运算结果为1的组合，其就属于SAT。显然，SAT是一个NP问题。那么，对于任意一个NP问题，即存在一个NTM在P(n)时间内解决它，只要找到其归约到SAT的方法（存在多项式时间的映射F），就可以证明SAT是NPC的。
  我们可以将NTM接受该NP问题的过程画成一张P(n)*P(n)的表格，那么，我们可以定义一个布尔表达式F来表述该表格，F∈SAT当且仅当表格对应的输入被NTM接受。F=φ(cell)∧φ(start)∧φ(move)∧φ(accept)。φ(cell)是对表格中每个单元的值的要求，φ(start)是对表格初始状态的要求，φ(move)是对其转移过程的要求，φ(accept)是对其接受格局的要求。wiki上给出了另一种形式的F定义，或者说是要求的划分，证明过程也很详细。但是无论如何定义，其都有一个准则，即F能够准确地涵盖表格的所有内容，包括初始格局、接受格局、转移的中间格局等等。F=1将生成所有NTM的接受表格。并且，生成F本身的算法复杂度是O(P(n)^2)。
  类似的，SAT可以归约到3SAT，其也是NPC问题。
  Cook定理给出了第一个NPC问题，可以用来证明其他问题是NPC问题（把SAT归约到该问题），不过构造，实在是门技巧，还需要极多的灵感。