从有穷自动机到图灵机：计算理论的能力阶梯与工程边界

简介这份《计算理论知识点.docx》面向准备计算理论期末考核的本科生尤其适合哈尔滨工程大学相关课程的学习者临考背诵与查漏补缺。文档按自动机理论、图灵机、语言理论、计算复杂度等模块串联要点逐条整理正则语言与有穷自动机的等价关系、正则语言的封闭性、格局与判定器的定义、图灵可识别与图灵可判定的区别、可判定性由补集图灵可识别刻画等结论并收录丘奇-图灵论题、映射可归约与多项式时间归约、P与NP、SAT与3SAT归约等常考内容还标注ADFA、ATM、HALTTM、EQTM等典型语言的判定性归属便于对照记忆与自测。压缩包内含1个docx文档大小约18KB体量轻巧手机或电脑均可直接翻阅。目前已有553人学习下载适合考前快速梳理概念与定理脉络也可作为课堂笔记的补充索引。1. 从一台只会数数的机器说起计算理论到底在算什么很多人第一次听到计算理论会以为它在讲怎么让代码跑得更快。其实它反过来问的是更直接的问题一件事到底能不能算以及要花多少代价才算得完。打个比方别人在造更快的车它却蹲在路边研究路最多能修到哪儿、哪儿压根就没有路。这门学问把计算这件事抽象成几台想象中的机器有穷自动机、下推自动机、图灵机。机器越强能认出来的语言就越多每往上一级台阶就有一批问题被解决也有一批问题被证明永远解不了。搞懂这条阶梯你手里那些正则表达式、编译原理、复杂度记号就不再是散落一地的碎片而是同一张地图上不同的海拔。2. 有穷自动机与正则语言为什么认得出来就等于写得出来2.1 一台只有有限个记忆格子的机器先想一个生活场景地铁闸机。它只记得很少几件事——有没有投币、闸门开没开、有没有人过去。它不可能记住今天第 37 位乘客穿了什么颜色的鞋因为它没有那个格子。有穷自动机就是这样一台机器。它一个字符一个字符地读输入串脑子里只有一件事我现在站在哪个状态。读完最后一个字符如果停在接受状态就说这个串被接受了。教材里有句话很朴素如果一个语言被有穷自动机识别那么这个语言是正则语言。状态的数量是固定的、有限的这就是有穷两个字的全部含义。它没有草稿纸没有计数器也没有栈所有记忆都压在那几个状态里。确定型有穷自动机DFA的规矩很死每个状态遇到每个字符只能走一条固定的出边。非确定型有穷自动机NFA就散漫多了同一个状态遇到同一个字符可以走向好几个地方甚至还能不读字符就凭空跳一步。听起来 NFA 更像是作弊可教材的第二条结论把这件事摆平了每一台非确定有穷自动机都等价于一台确定型有穷自动机。下面这段代码能让你直观看到状态即记忆是什么意思。它识别的是二进制串里 1 的个数为偶数# 识别二进制串中 1 的个数为偶数的 DFA # 状态 0 表示目前看到偶数个 1状态 1 表示奇数个 1 delta { (0, 0): 0, (0, 1): 1, (1, 0): 1, (1, 1): 0, } start_state 0 accept_states {0} def run(s): state start_state for ch in s: # 逐字符读入机器不回头 state delta[(state, ch)] # 转移函数决定下一站 return state in accept_states # 读完整串才看落点 print(run(1011), run(1100)) # 输出 False Truedelta就是转移函数给定当前状态 读到的字符返回下一个状态start_state是起点accept_states是准许通关的状态集合。注意代码里一个计数变量都没有——偶数个 1这个性质完全是靠两个状态轮流切换记住的。这就是有穷机器的精妙也是它的天花板它只能记住有限种情况再多就装不下了。2.2 为什么识别和描述是一回事教材里那句话第一次读很像同义反复一个语言是正则的当且仅当有一个正则表达式描述它。换个说法就好懂了——凡是能用一台小机器认出来的东西一定能用一行符号写出来反过来凡是能用一行符号写出来的东西也一定有一台小机器认它。机器和符号是同一件事的两个侧面。举例正则表达式(0|1)*11(0|1)*描述的是含有子串 11 的所有 0/1 串。你也可以画一台三状态的 DFA 来认它一开始停在还没见到 11的状态见到第一个 1 就挪到见到一个 1的状态再见到 1 就进入已经见过 11的接受状态之后一直待在那儿。两条路径描述的是同一个语言。所以教材里其实有三个等价说法得放在一起看说法直觉理解适合的场景被 DFA 识别一台规矩死板的机器认得它需要实际跑起来、要求确定性时被 NFA 识别一台可以同时走多条路的机器认得它设计思路、证明构造时更省事被正则表达式描述一行符号能写出来写规则、做匹配、查日志时最顺手这三者互相等价不是差不多是严格的双向等价。工程上你写一条正则理论上就等于画了一台 NFA再就等于画了一台 DFA。理解这一点你看到正则引擎内部把表达式编译成状态机就不会觉得神秘了。2.3 封闭性正则语言的三把锁教材第二条正则语言在并运算、连结、星号运算下封闭。这三个词听着抽象翻成大白话就是三种拼装方式并两个语言任选其一A ∪ B。就像商场的两个入口从哪个进都算进来了。连结先走完 A 再接着走 BAB。就像换乘两段行程拼成一段。星号把 A 重复任意次包括零次A*。就像这道菜可以加零份、一份、十份辣。封闭的意思是你拿两个正则语言去做这三种拼装拼出来的结果仍然是正则语言不会跑出这个圈子。这件事的价值在于省事——你验证了两个小语言是正则的那它们的并、连接、任意重复也一定是正则的不用每次都从头画机器。反过来说这条性质也常常被当免画图的捷径用在证明题里题目给一个看起来复杂的语言你把它拆成几个已知正则语言的并、连、星组合直接一句由封闭性可知就推完了比老老实实画状态图快得多。但封闭性也给不了你想要的一切。它管的是拼装之后还在圈内管不了某个具体语言到底在不在圈内。这就引出下一章要处理的麻烦有些语言压根不是正则的。2.4 正则机器记不住层数为什么正则语言有天花板因为状态数量有限。你让它数这个串里到底有几个左括号没闭合它做不到因为层数可以是 1、10、10000而它的状态只有那么几个装不下无限的计数。这件事在工程里翻车的例子很多。有人想用正则表达式去匹配嵌套的括号、嵌套的 JSON、嵌套的 HTML 标签写到一半发现怎么写都不对。不是你的正则写得不够努力是这类任务需要的记忆量无上限超出了有穷自动机的装备范围。要数层数你得给它配一个可以无限往下堆的草稿本。这就是下一章的主角。3. 从下推到图灵机语言的能力阶梯是怎么一级级爬上去的3.1 下推自动机给机器配一个草稿本正则机器缺什么缺一个能随手记、随手擦的地方。给它配一个栈问题就缓解了一大半。栈这个东西很好理解像食堂里叠起来的一摞盘子只能往顶上放也只能从顶上拿。放进去的最后拿出来先进后出。有了它机器就能数层数了——见到一个左括号就压一个记号进去见到右括号就弹一个出来最后栈空了就说明配对成功。这就是下推自动机。教材里对应的结论是一个语言是上下文无关的当且仅当存在一台下推自动机识别它反过来说如果一个语言被下推自动机识别那它就是上下文无关的。同一个语言类又一次出现了机器和描述两个等价说法。经典例子是形如a...ab...b的语言前面若干个 a后面同样多个 b两边数量必须相等。正则机器没辙因为它得记住前面到底来了多少个 a下推自动机可以一边读 a 一边往栈里压读到 b 就开始弹最后栈空就接受。还有一条结论很关键别漏掉每一个正则语言都是上下文无关的。这句话说明两个类不是并列关系是包含关系正则语言坐在上下文无关语言里面。教材里那句如果一个语言是正则的则可以用正则表达式描述它配合这一条一起看整条阶梯的骨架就出来了。3.2 文法与标准范式为什么文法可以统一改写描述上下文无关语言还有另一条路上下文无关文法。它由一组产生式组成每条规则长成把一个非终结符替换成一串符号的样子从左边的起始符号出发一步步推导出最终的串。写文法比画机器更像在写规则一不留神就写得五花八门。教材里的结论说任何一个上下文无关语言都可以用标准范式的上下文无关文法产生。所谓标准范式是把规则统一整理成两种固定形状要么把一个非终结符拆成两个非终结符要么把一个非终结符换成一个终结符。这个整理过程的意义打个比方各家菜谱本来写法五花八门有写少许的有写看着放的。标准范式就是强制规定——每道菜只写放一克盐或者再加一道工序这样的句子。菜还是那道菜但格式统一了机器和证明就能按一个套路处理下去不用每次面对新花样重新想办法。顺带说一条好用的结论每一个上下文无关语言都是可判定的。也就是说给一台机器一个文法和一个串问这个串能不能由这个文法推导出来这个问题是有确定答案、并且一定能停机回答的。上面说的统一格式正是这类判定流程能跑通的前提。3.3 图灵机与格局黑匣子里的一帧画面再往上爬一级就是图灵机。它的构造很朴素一条无限长的带子一个读写头一个有限状态的控制器。读写头在带子上左右移动读一个符号、写一个符号、挪一格、换个状态。图灵机跑起来的时候怎么描述它现在到哪一步了教材给了一个词格局。格局是当前状态、当前带内容和读写头当前位置这三样东西的组合。你可以把它想成录像带暂停时的那一帧画面——按这一帧就能完整还原机器此刻的全部处境。把一帧帧连起来就是计算历史一个格局序列第一个是起始格局最后一个是接受格局中间每一帧都是前一帧按规则走一步的结果。拒绝计算历史同理只是最后一帧落在拒绝格局上。这里有个区分挺重要计算历史都是有限序列。如果一台机器在某个输入上永不停机那它既没有接受历史也没有拒绝历史——不是历史很长而是根本没有历史可写。确定型机器在任何给定输入上最多只有一条计算历史因为它每一步只有一个选择。非确定型机器就不一样了一个输入可能对应多条计算历史每条对应它分头探索的一个分支。这个一对多的关系是后面理解非确定性复杂度的一把钥匙。3.4 等价性多带、非确定、单带为什么能互相顶替教材里连着好几条都是等价性结论读的时候容易滑过去其实它们撑起了整座理论的地基每一台多带图灵机都等价于一台单带图灵机。非确定型图灵机都等价于确定型图灵机。一个语言是图灵可识别的当且仅当存在非确定型图灵机识别它。等价在这里指认得出的语言集合完全一样不是效果差不多。多带可以模拟成单带办法是把多条带的内容交错编码到一条带上再用标记记住每条虚拟带读写头的位置——麻烦但可行。非确定可以模拟成确定办法是让机器系统性地把每一个分支都走一遍。这些等价性说明加带子、允许瞎猜都不会让机器认得出更多语言只是让描述变方便、让某些构造变自然。真正决定能力的是有没有无限带子这件事而不是带子有几条。配套的还有图灵论题。它的通俗版本是任何能按步骤机械执行的过程都能用图灵机实现。这不是一条能证明的定理而是一个被广泛接受的约定——它给了算法这个词一个明确的落脚点也让后面所有不可判定的结论有了意义不是我们没想到办法而是这类问题压根不存在机械步骤的解法。教材还提到描述图灵机的三种水平最底层是形式化描述把状态、转移函数一条条写清楚往上一层是实现描述用日常语言说清楚它怎么做再往上是高水平描述只讲算法思路连带子和读写头都不提。做题时选哪一层看题目要你证明什么——要严谨就写底层要讲清思路就用高层。4. 可识别与可判定机器也会卡住这件事到底多要命4.1 三种结局接受、拒绝、循环一台图灵机在某个输入上跑起来可能出现三种结局接受、拒绝或者循环。这里的循环要小心理解。它只指机器不停机不一定是永远重复同样的步骤。有些机器是在原地打转有些是在带子上越跑越远、看起来一直在干活但就是不进接受态也不进拒绝态。对外部观察者来说这两种情况都表现为等不到结果。这个区别为什么重要因为一旦你把循环当成我还没想明白就会有个很自然的错觉再等等说不定就出结果了。教材里那句话点破了这件事——判定器有时候很难区分进入循环还是仅仅需要耗费很长时间运行。等多久算久没人能给你一个上界。4.2 判定器为什么我们偏爱一定停机的机器正因为分不清卡住和慢教材更愿意讨论一类更乖的机器判定器。它有一个硬性承诺——所有输入上都停机永远不循环。给它任何输入它总能在有限步内给出接受或拒绝。于是有了两个必须分清的词图灵可识别也叫递归可枚举语言存在某台图灵机它能在属于这个语言的串上停机并接受。注意它没说在不属于的串上会怎样可能拒绝也可能一直跑。图灵可判定也叫递归语言存在某台图灵机它在该语言的所有输入上都停机并且正确回答是否属于。判定要求更严不光要认得出对的还要认得出错的而且不能卡住。教材里那句每一个可判定语言都是图灵可识别的说的就是这个包含关系——可判定的圈子更小坐在可识别的圈子里面。4.3 补集视角可判定 可识别 补可识别语言的补定义很直白把所有不在这个语言里的串收集起来构成的语言就是它的补。教材给了一条很漂亮的判据一个语言是可判定的当且仅当它既是图灵可识别的也是补图灵可识别的。这句话值得琢磨。直觉上是这样如果你有一台机器专门认是还有一台机器专门认不是那么把两台一起跑——并行地交替执行它们的步数——总有一台会在有限步内停机开口。谁先开口就听谁的于是你就有了一个永远能给出答案的判定器。但要注意这条判据反过来也划了一条线如果一个语言可识别、但它的补不可识别那它就一定不可判定。这正是后面 A_TM 的处境。4.4 不可判定的名单A_TM、停机问题与它们的亲戚教材把这些语言分成两堆一堆是可判定的一堆是不可判定的。分堆本身就很有信息量。可判定这一堆A_DFA确定型有穷自动机是否接受某个串、A_NFA、A_REX正则表达式是否产生某个串、E_DFA判定 DFA 的语言是否为空、EQ_DFA两台 DFA 是否认同一个语言、A_CFG、E_CFG还有 A_LBA。线性有界自动机是一种受限的图灵机它的读写头不许离开输入所占的那段区域想往外走就原地不动——限制一加判定性就回来了。不可判定这一堆就热闹了A_TM图灵机是否接受某个串、停机问题、HALT_TM图灵机在给定输入上是否停机、E_TM图灵机是否不接受任何串、REGULAR_TM、EQ_TM、E_LBA、ALL_CFG还有 PCP 问题。另外A_TM 的补是不可识别的EQ_TM 更特别它既不是图灵可识别的也不是补图灵可识别的。初学的人容易在这里产生一种挫败感怎么一堆问题都不可判定其实换个角度想这份名单恰恰是理论的收获。它不是在说我们还不够聪明而是在说这类问题的机械解法压根不存在。知道一条路走不通比在死胡同里撞十年更有价值。5. 常见误区与易混概念这五组词别再混着用5.1 误区一正则语言和上下文无关语言是并列的易混点两个名字都带语言教材里又分开讲看起来像同一层的两个分类。为什么混很多人背结论时把它们并列成正则语言有 A 性质上下文无关语言有 B 性质脑子里就默认二者互不包含。怎么区分记住那条单向包含关系——每一个正则语言都是上下文无关的。楼梯是从下往上走的不是左右并排。所以你要证明某个语言是上下文无关的如果它同时是正则的那这句话当然成立但反过来你证明了它是上下文无关的绝不能顺手说它是正则的。判断某个具体语言属于哪一层标准做法是看它需不需要数层数数不了层的是正则能用一个栈数层的是上下文无关还要更多记忆的就得往上爬。5.2 误区二可识别和可判定是一回事易混点两个词都带可都表示机器能处理。为什么混课堂上讲图灵机识别一个语言讲得太多导致识别变成了一个泛称好像只要机器能处理就叫识别于是可判定也被当成可识别的一种口语说法。怎么区分抓一个字——停。可识别只保证属于这个语言的串机器最终会停下来接受不属于的串机器可能拒绝也可能永远跑下去。可判定则保证所有输入都停机且答案正确。用一句话记住可判定 一定会给你答复可识别 只说是的时候一定会给答复。这两者的差距就是会不会卡住。5.3 误区三P 和 NP 是简单问题和难题易混点P 常被翻译成容易NP 常被理解成困难。为什么混教材里 P 类的定义是多项式时间内可判定NP 的定义是能被非确定型多项式时间图灵机判定后者读起来就很费劲于是大家偷懒用简单/困难来记。怎么区分P 是成员可以快速判定的语言类NP 是成员可以快速验证的语言类。注意验证两个字给你一个候选答案你能在多项式时间内检查它对不对这个语言就在 NP 里。教材里列的 HAMPATH、CLIQUE、SUBSET-SUM、SAT、3SAT、UHAMPATH 都属于 NP它们未必难只是我们目前没找到快速判定的办法。另外一定要记住包含方向P 在 NP 里面。P 是否等于 NP至今是个开放问题教材里那条关于 SAT 的结论说的正是这件事。5.4 误区四语言可判定 函数可计算易混点两个概念都跟能不能算有关教材里还挨着出现。为什么混可判定和可计算在中文里语感太接近读快了会当成同义词。怎么区分看问句的形式。可判定说的是一个是非题——这个串属不属于这个语言答案是是或否。可计算说的是一个问答题——给一个输入输出一个结果。教材里对可计算函数的定义是存在一台图灵机在每个输入上都停机且停机时目标结果恰好在带上。注意它要求每个输入都停机比可识别严格得多。做映射归约时你会频繁用到可计算函数这个词指的就是这种一问一答、必定停机的转换器。5.5 误区五NP 完全和 PSPACE 完全是同一层难度易混点名字里都带完全都表示这个类里最难的那批。为什么混完全这个词本身没有说明它挂在哪个类上看名字看不出楼层。怎么区分完全性是相对于某个类说的。NP 完全是指属于 NP且 NP 里所有问题都能多项式时间归约到它PSPACE 完全是指属于 PSPACE且 PSPACE 里所有问题都能归约到它。楼层关系是 L ⊆ NL ⊆ P ⊆ NP ⊆ PSPACE而且 PSPACE NPSPACE。教材里列出的 PSPACE 完全问题包括 TQBF、FORMULA-GAME、GGNL 完全问题里则有 PATH。一个 PSPACE 完全问题大概率不在 NP 里——别看见完全就以为它们是难兄难弟。6. 归约与复杂度什么时候该搬出这套工具什么时候别硬套归约是这套理论里最实用的一件工具但它的方向性极易搞反搞反了整道题就白做。教材的定义是用映射可归约性把问题 A 归约为问题 B指的是存在一个可计算函数把 A 的实例转换成 B 的实例有了这个转换函数就能用 B 的解法来解决 A。写成符号是 A ≤m B。注意箭头的意思A 归约到 B说明 B 至少和 A 一样难因为解了 B 就顺手解了 A。于是有两条直接可用的推论如果 A ≤m B 且 A 是不可判定的那么 B 也是不可判定的如果 A ≤m B 且 B 是图灵可识别的那么 A 也是图灵可识别的。第一条是用来往下压——已知 A 难推出 B 也难第二条是用来往上抬——已知 B 好对付推出 A 也好对付。方向反了结论就完全相反。复杂度那一侧同理只是把可计算函数换成多项式时间可计算函数符号写成 A ≤p B。教材里说 3SAT 多项式时间可归约到 CLIQUE意思就是团问题接住了 3SAT 的难度。什么时候该用这套东西我列个粗略的判断表你手上的问题该搬的工具别做的事一个具体串能不能被某台自动机接受直接模拟属于可判定的那一堆别去证不可判定方向错了一个语言看起来比已知难问题还复杂从已知不可判定问题归约过来别从简单问题往下归约一个语言看起来比已知简单问题还复杂归约到已知可识别语言别用我觉得它简单当论据判断两个语言的难度关系看 ≤ 的方向再套两条推论别把 A ≤ B 读成 B 比 A 简单判断空间复杂度问题想 NSPACE(f(n)) 与 SPACE(f²(n)) 的关系别拿时间复杂度的直觉硬套空间最后说个边界这套工具是用来做定性判断的回答能不能和属于哪个类不回答具体多快。你在工程里写一个正则引擎不会去算它的时间复杂度属于哪个类但你要判断这个需求能不能用正则搞定第 2 章那套记忆有限的分析就立刻派上用场。用错了场合理论就变成了背名词。我大二那年就栽过一次。考试前把A 可归约到 B背成了B 可归约到 A觉得反正都是归约方向无所谓。结果证明题写到最后一步把B 不可判定推成了A 不可判定整道题十几分全没。那之后我每次写归约都强制先在草稿纸上画一个箭头标清楚难问题 → 简单问题的指向确认两端的角色再动笔。这个习惯后来做任何依赖关系的推理都用得上比记住那一堆结论本身更值钱。希望帮到你。本文还有配套的精品资源点击获取