English
The theory of computation asks what a procedure can accomplish under an explicit model. Three questions organize it: what operations and memory are available, which problems admit an algorithm that always gives the required answer, and what resources such an algorithm needs. Restricted machines are useful in their own right; general models reveal limits that apply across programming languages.
A decision problem asks for a yes-or-no answer on every permitted input. A recognizer accepts yes-instances but may run forever on other inputs; a decider must terminate on all inputs. A search problem asks for a witness or object, and a function problem asks for a computed value. Distinguishing these tasks prevents many apparently contradictory claims about what is computable.
Start with sets, functions, induction, and simple programs (§2.2). Diagonalization and reductions are techniques to learn here, not prerequisites that must already be mastered. Section 3.3 then examines resource bounds in greater depth.
What Happened When Mathematics Tried to Mechanize Itself
Long before electronic computers, mathematicians asked whether solving a problem could be reduced to following rules. Hilbert’s foundational program and the first-order decision problem gave this question a precise setting. Church’s and Turing’s work in the 1930s supplied different formal accounts of effective calculation and proved limits on what such calculation can decide.
The equivalence of Turing machines, lambda-definability, and appropriate recursive-function formalisms is established by mathematical simulation results. The Church–Turing thesis is the further claim that these formal notions capture effective calculation. The equivalence theorems and the thesis are not the same statement. Nor does the thesis claim that every physical process or every idealized analog model can be simulated efficiently.
Turing’s universal-machine construction made a procedure’s description available as another procedure’s input. This illuminates interpreters and compilers, but those technologies did not require their designers to derive them from Turing’s theorem. Mathematical possibility, historical influence, and an actual engineering design are distinct claims.
Postwar work extended both limits and constructions. Rice’s theorem organized many undecidability results about computed functions; the Davis–Putnam–Robinson–Matiyasevich result showed that Hilbert’s tenth problem has no general decision algorithm. That problem asks whether a polynomial equation with integer coefficients has an integer solution. Individual equations can still be solved; the impossibility concerns one algorithm that always decides every such input. Complexity research was already developing before Cook’s 1971 theorem. Cook, Levin, and Karp helped establish NP-completeness, connecting efficient verification with reductions between problems. These developments sharpened two separate questions: whether a general algorithm exists and whether a useful resource bound is possible.
Models, Undecidability, and Complexity
Choose the model before proving a limitation. Unbounded tape is a mathematical allowance for arbitrarily large finite computations, not a claim that a physical machine owns infinite memory. A fixed finite-state device has a finite configuration graph; allowing input and memory sizes to grow creates the general problems addressed by computability theory.
The Machine Models and What They Establish
A finite automaton remembers one of finitely many states while reading input. A state summarizes the part of the input history needed for future decisions. To accept exactly the bit strings with an even number of 1s, start in an even state, switch between even and odd on each 1, and stay put on 0. Accept if the final state is even. The exact number and positions of earlier 1s no longer matter.
In a deterministic automaton, two input prefixes may share a state only if every possible continuation requires the same accept-or-reject answer for both. The prefixes 0 and 11, for example, can share the even state. This explains the limit for arbitrarily nested parentheses of one kind: different numbers of unmatched opening parentheses require different numbers of closing parentheses. There are unboundedly many depths to distinguish, so finitely many states cannot suffice. If the maximum permitted depth is a fixed k, however, a finite automaton can track depths 0 through k, reject negative depths or depths greater than k, and accept when the final depth is zero. The memory requirement comes from the distinctions the task demands.
A pushdown automaton supplies a stack that can grow with the input; nondeterministic pushdown automata recognize exactly the context-free languages.
A Turing machine has a finite control, a read-write tape, and a head that moves according to rules determined by the current state and scanned symbol. One step changes the state, writes a symbol, and moves the head. Repetition supplies a computation; the tape can grow as needed over larger finite inputs. This simple mechanism can simulate general effective procedures. The usual Chomsky hierarchy is regular, context-free, context-sensitive, and computably enumerable languages. Decidable languages sit strictly between context-sensitive and computably enumerable languages. The hierarchy concerns language classes and corresponding models, not a ranking of the usefulness of programming tools.
Textbook regular expressions describe regular languages; programming libraries may add backreferences or other features beyond that model. Context-free grammars describe much programming-language syntax, but name binding and type correctness require additional rules. A parser accepting a string therefore does not establish that the program is meaningful or safe.
The Technique of Diagonalization
Suppose a total procedure H(p, x) correctly decides whether program p halts on input x. Construct D(p) as follows: if H(p, p) says “halts,” loop forever; otherwise halt. Now apply D to its own description. If H(D, D) predicts termination, D(D) loops; if it predicts nontermination, D(D) halts. Either answer contradicts the assumed specification of H.
The conclusion is that no such decider works for every program-input pair. It does not prevent deciding many particular cases. Nor does it prevent a recognizer from simulating a program until it halts: that procedure succeeds on halting instances, but has no general way to certify nontermination.
Reductions spread this impossibility without repeating the diagonal construction. Suppose a decider could determine whether a program ever prints READY. Given (p,x), construct a wrapper that first simulates p(x) and prints READY only after that simulation terminates, suppressing the simulated program’s output. A decider for the wrapper property would decide halting. The wrapper must be effectively constructible; preserving the yes/no answer is what makes the reduction work.
Rice’s theorem generalizes this pattern to nontrivial extensional properties of partial computable functions. “Extensional” means that the property depends on the function computed, so two programs computing the same function must share it. “Nontrivial” means that some such functions have the property and others do not. The theorem does not cover arbitrary syntactic properties, such as whether a source file contains a loop keyword. Practical analyses can restrict the language, accept incompleteness, or return unknown.
The diagonal pattern predates computation theory. For a proposed list of infinite bit sequences, construct a sequence whose nth bit differs from the nth bit of the nth listed sequence. It differs from every listed sequence somewhere, so the list is incomplete. The halting argument adds an essential computational requirement: the contradicting program must be constructible from the assumed decider. Gödel’s arithmetic encoding provides another route to self-reference, through formulas describing proofs; the incompleteness theorem and the halting theorem still have different statements and hypotheses.
Complexity Classes and the P vs. NP Question
P contains decision problems solvable in polynomial time; NP contains those whose yes-instances have polynomial-size certificates checkable in polynomial time. A satisfying assignment is a certificate for SAT. For a problem to be NP-complete, it must be in NP and every NP problem must reduce to it under the specified polynomial-time reductions. Consequently, a polynomial-time algorithm for any NP-complete problem would give polynomial-time algorithms for all of NP: first apply the reduction, then run that algorithm. This is why one such result would establish P = NP.
The direction is crucial: reducing a known NP-complete problem to a new problem establishes hardness of the new problem, not the reverse. Membership in NP is a separate obligation and is not automatic for every problem with an intuitively describable “solution.” Optimization and counting variants need their own formulations.
The P versus NP question remains open. NP-hardness does not prove an exponential lower bound. Polynomial time is an asymptotic category, not a promise that an algorithm is fast at the sizes of interest. Section 3.3 develops the distinctions among time, space, randomization, approximation, and average-case difficulty.
For example, a decision version of route optimization asks whether a tour of length at most K exists. A proposed tour can be checked by verifying the visited vertices and summing its encoded edge weights. Finding the minimum tour and counting tours are related tasks, but their outputs are different. Input size also means encoded length: an integer written in binary needs roughly its logarithm in bits, so a loop running that integer many times need not be polynomial in the input length.
What Studying This Changes
The useful habit is to diagnose the requested guarantee. Does an analyzer need to answer every question, or may it say “unknown”? Is the input language unrestricted, or does the application use a finite fragment? Does a scheduling tool need an optimum or an adequate solution by a deadline? A limitation becomes a design aid when you identify which requirement can change.
Practice both kinds of reduction: transform a problem into one you can solve, and transform a known impossible or hard problem into a proposed target. Write the input mapping and prove both directions of the answer correspondence. Seeing an exponentially large search space alone proves neither undecidability nor NP-hardness.
Resources
Books and Texts
Sipser’s Introduction to the Theory of Computation (3rd ed.) develops automata, computability, and complexity in sequence. Its proofs and exercises make it a useful primary text after basic discrete mathematics. Pay particular attention to constructing machines and reductions yourself: recognizing a finished proof is easier than supplying the construction it needs.
Boaz Barak’s Introduction to Theoretical Computer Science (free at introtcs.org) is a modern open companion that emphasizes computational phenomena, universality, code-as-data, randomness, cryptography, and complexity with supplementary code notebooks. It is not a replacement for Sipser’s automata-to-computability progression, but it gives contemporary framing and computational examples that many learners find more alive than the traditional syllabus.
For the foundational and logical dimension, Boolos, Burgess, and Jeffrey’s Computability and Logic (5th ed., 2007) is the alternative entry. Where Sipser emphasizes complexity, Boolos-Burgess-Jeffrey emphasizes computability and its connections to Gödel’s incompleteness theorems and modal logic. A reader who wants to understand Gödel’s results as results in the theory of computation — not just as results in mathematical logic — should start here. The two books are genuinely complementary: Sipser for complexity, Boolos-Burgess-Jeffrey for foundational depth.
Arora and Barak’s Computational Complexity: A Modern Approach and Goldreich’s Computational Complexity: A Conceptual Perspective develop the material introduced in §3.3, including randomized computation, interactive proofs, circuit complexity, and approximation hardness. Their treatment of PCP includes the special proof encoding and probabilistic guarantee that a short informal description can omit. Use selected chapters after becoming comfortable with basic reductions.
For computability at depth, Soare’s Turing Computability: Theory and Applications (2016) is the current standard for classical recursion theory — Turing degrees, recursively enumerable sets, oracle computation, and the fine structure of undecidability. This material goes well beyond what Sipser covers and is appropriate only for readers planning serious engagement with the mathematical logic side.
The original papers remain valuable primary sources. Turing’s 1936 paper “On Computable Numbers” provides the original machine model and undecidability argument. Cook’s 1971 paper and Karp’s 1972 paper are the founding documents of NP-completeness theory and are both directly accessible. Davis’s collection The Undecidable assembles the major papers of the founding decade in a single volume.
For the connection to logic, the automata-and-grammars treatment in Hopcroft, Motwani, and Ullman’s Introduction to Automata Theory, Languages, and Computation (3rd ed., 2006) goes deeper than Sipser on the formal language side — useful for readers who need the formal language theory for compiler work or formal methods.
| Book | Role | Type |
|---|---|---|
| Sipser, Introduction to the Theory of Computation (3rd ed.) | Canonical entry; clear and complete | Entry |
| Barak, Introduction to Theoretical Computer Science (free) | Modern open companion with code notebooks | Auxiliary |
| Boolos, Burgess & Jeffrey, Computability and Logic (5th ed.) | Foundationally oriented alternative entry | Entry |
| Soare, Turing Computability | Classical recursion theory at depth | Depth |
| Hopcroft, Motwani & Ullman, Intro to Automata Theory (3rd ed.) | Formal language theory | Reference |
| Turing (1936), Cook (1971), Karp (1972) primary papers | Founding documents | Reference |
| Complexity theory bridge: Arora & Barak, Computational Complexity (free draft) | Bridge forward to §3.3 complexity theory | Auxiliary |
| Complexity theory bridge: Goldreich, Computational Complexity: A Conceptual Perspective | Alternative advanced bridge to §3.3 | Auxiliary |
| Davis, ed., The Undecidable | Original papers collected | Auxiliary |
Courses and Lectures
MIT 6.045J / 18.404 (Theory of Computation, MIT OCW) provides lectures and exercises to accompany the automata-to-complexity sequence. Work through a problem before watching its solution, then compare the construction and proof obligations with your own attempt.
Scott Aaronson’s course materials for his quantum complexity and complexity theory courses (available on his website) provide material for readers who want to engage with the research frontier or the quantum dimension. Aaronson writes with both technical precision and enthusiasm for the material.
MIT 6.046 (Design and Analysis of Algorithms, free on MIT OCW) covers algorithms at the level where complexity theory becomes relevant — NP-completeness reductions, approximation algorithms, randomized algorithms. It complements 6.045 and is the natural next course for readers who want to connect the theory to algorithm design.
| Course | Platform | Type |
|---|---|---|
| MIT 6.045J / 18.404 Theory of Computation (free) | MIT OCW / YouTube | Entry |
| MIT 6.046 Design and Analysis of Algorithms (free) | MIT OCW | Depth |
| Aaronson, complexity and quantum complexity materials (free) | scottaaronson.com | Depth |
Practice, Tools, and Current Sources
JFLAP is an interactive environment for automata, grammars, and Turing machines. Start with a two-state parity automaton and a stack-based balanced-parentheses recognizer. Trace both accepting and rejecting inputs, then explain why the memory models differ. A universal-machine construction can follow after these simpler models are understood.
Automata Tutor v3 (free online) adds an exercise-and-feedback layer for automata and formal languages, including finite automata, regular expressions, context-free grammars, pushdown automata, Turing machines, and conversions between models. It is valuable because automatic feedback makes this part of the subject practiceable at volume; it should supplement, not replace, proofs done by hand.
Implement a small Turing-machine simulator with a visible tape, state, and step counter. A step limit makes experiments terminate, but reaching it means only that the simulated machine has not halted yet. Failed attempts to decide termination are not a proof of undecidability; use the diagonal argument in this section to establish the general result.
Scott Aaronson’s “Who Can Name the Bigger Number?” and “Why Philosophers Should Care About Computational Complexity” (both free on his website) are short essays that engage with the philosophical and mathematical significance of computability and complexity results without requiring technical preparation. Reading them alongside Sipser provides context for why the technical results matter.
The Complexity Zoo (complexityzoo.net, free) is a comprehensive reference for complexity classes and their relationships. As a reference during study, it is useful; as a starting point, it is overwhelming. Use it to look up specific classes as you encounter them.
| Resource | Platform | Type |
|---|---|---|
| JFLAP (free) | jflap.org | Practice |
| Automata Tutor v3 (free) | automata-tutor.model.in.tum.de | Practice |
| Complexity-class lookup via Complexity Zoo (free) | complexityzoo.net | Reference |
| Aaronson essays (free) | scottaaronson.com | Depth |
| Simulated Turing machine implementation | Local | Practice |
Traps
| Trap | Why it misleads | Better response |
|---|---|---|
| Treating the Church–Turing thesis as a simulation theorem | Formal equivalences are proved; identifying them with effective calculation is a further thesis. | Separate the mathematical models from the claim connecting them to informal procedure. |
| Confusing recognition with decision | A simulation may confirm termination without deciding nontermination. | State what must happen on both yes- and no-instances. |
| Treating infinite memory as physical hardware | The model allows arbitrarily large finite instances. | Distinguish an unbounded problem family from a fixed finite device. |
| Reversing a reduction | The direction determines which problem inherits a solver or a hardness result. | Draw the input transformation and hypothetical solver explicitly. |
| Applying Rice’s theorem to syntax | The theorem concerns nontrivial properties of computed functions. | Check whether equivalent computations must share the property. |
| Treating general limits as failure on every instance | Restricted cases can have effective algorithms. | Identify the domain, required guarantee, and acceptable incompleteness. |
中文
计算理论在明确模型下，研究一个过程能完成什么。三个问题组织这一领域：允许哪些操作与存储，哪些问题存在总能给出所需答案的算法，以及算法需要多少资源。受限机器本身就有用途；一般模型则揭示跨编程语言成立的限制。
判定问题要求对每个允许的输入回答是或否。识别器接受肯定实例，却可能在其他输入上永远运行；判定器必须对所有输入都终止。搜索问题要求给出见证或对象，函数问题要求计算一个值。分清这些任务，可以避免许多关于可计算性的表面矛盾。
从集合、函数、归纳法和简单程序开始（§2.2）。对角化与归约是这里要学习的方法，不是必须事先掌握的门槛。§3.3 再深入讨论资源界。
当数学试图机械化自身时发生了什么
早在电子计算机出现前，数学家就在追问：解决问题能否归结为遵循规则？Hilbert 的基础研究计划与一阶判定问题，为这种追问提供了精确场景。Church 和 Turing 在二十世纪三十年代，用不同形式描述有效计算，并证明了这类计算能够判定什么的边界。
图灵机、lambda 可定义性与适当的递归函数形式系统之间的等价，有数学上的模拟结果支持。Church–Turing 论题则进一步主张，这些形式概念刻画了有效计算。等价定理与这个论题并不是同一个陈述。论题也没有声称每种物理过程或理想化模拟计算模型，都能够被高效模拟。
Turing 的通用机构造，让过程的描述能够成为另一个过程的输入。这有助于理解解释器与编译器，但这些技术并不要求设计者先从 Turing 的定理推导出工程设计。数学上的可能性、历史影响和实际工程设计，是不同的主张。
战后研究同时扩展了限制与构造。Rice 定理组织了许多关于所计算函数的不可判定性结果；Davis–Putnam–Robinson–Matiyasevich 的结果说明，Hilbert 第十问题不存在一般判定算法。这个问题询问：一个整系数多项式方程是否具有整数解？具体方程仍然可能求解；不可能的是一个总能判定每个这种输入的算法。复杂性研究在 Cook 1971 年的定理之前就已发展。Cook、Levin 和 Karp 帮助建立 NP 完全性，把高效验证与问题间的归约连接起来。这些发展使两个问题更加清楚：一般算法是否存在，以及有用的资源界是否可能。
模型、不可判定性与复杂性
证明限制前，先选择模型。无界纸带允许讨论任意大的有限计算，并不是声称物理机器拥有无限内存。固定的有限状态装置具有有限的配置图；允许输入和内存规模增长，才产生可计算性理论所讨论的一般问题。
机器模型及其确立的东西
有限自动机在读取输入时，只记住有限多个状态之一。状态概括了此前输入中影响后续判断的信息。若要恰好接受 1 的数量为偶数的比特串，可以从偶数状态出发，每读到一个 1 就在奇数、偶数状态之间切换，读到 0 则保持状态，最后处于偶数状态才接受。此前 1 的确切个数和位置已经不再重要。
在确定性自动机中，两个输入前缀只有在接上任意相同后缀时都需要作出相同的接受或拒绝判断，才能共用一个状态。例如，前缀 0 和 11 可以共用偶数状态。这也解释了为何有限自动机不能识别任意嵌套深度的单类配对括号：未配对的左括号数量不同，所需的右括号数量就不同；要区分的深度没有上界，有限多个状态便不够用。不过，如果允许的最大深度是固定的 k，有限自动机就能记录从 0 到 k 的深度，遇到负深度或超过 k 时拒绝，结束时深度为零才接受。需要多少记忆，取决于任务要求保留哪些区别。
下推自动机提供一个可随输入增长的栈；非确定性下推自动机恰好识别上下文无关语言。
图灵机具有有限控制、可读写纸带，以及依据当前状态和所读符号按规则移动的读写头。一步执行改变状态、写入符号并移动读写头；反复执行便形成计算。面对更大的有限输入，可以按需使用更长纸带。这种简单机制能够模拟一般的有效过程。通常的 Chomsky 层次依次包括正则、上下文无关、上下文有关和可计算枚举语言。可判定语言严格位于上下文有关语言与可计算枚举语言之间。这个层次讨论语言类别及其对应模型，并不是给编程工具的实用性排名。
教材中的正则表达式描述正则语言；编程库可能加入反向引用等超出该模型的功能。上下文无关文法能描述许多程序语言的语法，但名称绑定与类型正确性需要额外规则。因此，解析器接受一个字符串，并不证明程序具有合理含义或安全性。
对角线法
假设存在总能终止的程序 H(p, x)，能够正确判定程序 p 在输入 x 上是否停机。构造 D(p)：如果 H(p, p) 回答“停机”，就永远循环；否则立即停机。现在把 D 的描述作为它自身的输入。如果 H(D, D) 预测终止，D(D) 就循环；如果预测不终止，D(D) 就停机。两种回答都与假定的 H 的规格矛盾。
结论是：不存在对每个程序与输入组合都有效的这种判定器。这不妨碍判定许多具体情形，也不妨碍识别器模拟一个程序直到它停机：模拟在停机实例上会成功，但没有一般方法据此确认不终止。
归约让这种不可能性传播到其他问题，而不必重复对角构造。假设某个判定器能判断程序是否会打印 READY。给定 (p,x)，构造一个包装程序：先模拟 p(x)，屏蔽被模拟程序的输出，只在模拟终止后打印 READY。若能判定包装程序的这个性质，就能判定停机。包装必须可以有效构造；保持是非答案的对应关系，才使归约成立。
Rice 定理把这种模式推广到偏可计算函数的非平凡外延性质。“外延”表示性质取决于计算出的函数：两个程序如果计算同一个函数，就必须共同具有或不具有该性质。“非平凡”表示有些这类函数具有该性质，另一些没有。定理不覆盖任意语法性质，例如源文件是否包含循环关键字。实际分析可以限制语言、接受不完备，或返回未知。
对角方法早于计算理论。对于声称列出所有无限比特序列的列表，可以构造一个序列，使其第 n 位不同于列表中第 n 个序列的第 n 位。它与每个已列序列至少有一处不同，因此列表不完整。停机论证增加了一项关键计算要求：必须能够从假设的判定器构造出导致矛盾的程序。Gödel 的算术编码则通过描述证明的公式，提供另一条自我指涉路径；不完备性定理与停机定理仍然具有不同的陈述和前提。
复杂性类与 P vs. NP 问题
P 包含可在多项式时间内求解的判定问题；NP 包含这样的判定问题：肯定实例具有长度为多项式、可以在多项式时间内核验的证书。满足赋值就是 SAT 的证书。一个问题要成为 NP 完全问题，必须属于 NP，而且每个 NP 问题都能通过指定的多项式时间归约转化为它。因此，任意 NP 完全问题的多项式时间算法，都能为 NP 中全部问题提供多项式时间算法：先应用归约，再运行该算法。这解释了为什么这样一个结果就能建立 P = NP。
方向至关重要：把已知 NP 完全问题归约到新问题，才是在建立新问题的困难性，而不是反过来。属于 NP 是另一项需要论证的要求；直觉上能描述“解”，并不自动满足它。优化与计数版本需要各自的形式化。
P 与 NP 问题仍未解决。NP 困难性没有证明指数时间下界。多项式时间是一种渐近类别，并不保证算法在我们关心的规模上很快。§3.3 会展开时间、空间、随机化、近似与平均情形困难程度之间的区别。
例如，路线优化的判定版本可以问：是否存在长度至多为 K 的巡回路线？检查候选路线时，可以核对访问的顶点，并求和其编码后的边权。寻找最短路线与计算路线数量是相关任务，但输出不同。输入大小还指编码长度：二进制整数需要大约为其对数的位数，因此循环该整数所表示的次数，并不一定是关于输入长度的多项式时间。
学习这个主题会改变什么
有用的习惯是诊断所要求的保证。分析器是否必须回答每个问题，还是可以说“未知”？输入语言是否不受限制，还是应用只使用有限片段？调度工具需要最优解，还是在截止时间前得到足够好的解？识别哪些要求可以调整，限制才会成为设计的帮助。
练习两类归约：把问题转成能够求解的问题，以及把已知不可解或困难的问题转成目标问题。写出输入映射，并证明答案对应的两个方向。仅仅看到指数大的搜索空间，既不能证明不可判定，也不能证明 NP 困难。
资源
书籍与文本
Sipser 的 Introduction to the Theory of Computation（第 3 版）依次展开自动机、可计算性和复杂性。掌握基本离散数学后，可以把它的证明与习题作为主要学习材料。尤其应亲自构造机器与归约：看懂完成的证明，通常比提供证明所需的构造容易。
Boaz Barak 的 Introduction to Theoretical Computer Science（introtcs.org 免费）是一本现代开放配套教材，强调计算现象、通用性、代码即数据、随机性、密码学和复杂性，并配有代码 notebook。它不能替代 Sipser 从自动机到可计算性的推进路线，但它提供了当代框架和计算例子，许多学习者会觉得它比传统大纲更鲜活。
对于基础和逻辑维度，Boolos、Burgess 和 Jeffrey 的 Computability and Logic（第 5 版，2007）是另一种入口。Sipser 更强调复杂性；Boolos-Burgess-Jeffrey 则强调可计算性及其与 Gödel 不完备性定理和模态逻辑的联系。想把 Gödel 结果理解为计算理论中的结果——而不只是数理逻辑中的结果——的读者，可以从这里开始。两本书是真正互补的：Sipser 用于复杂性，Boolos-Burgess-Jeffrey 用于基础深度。
Arora 与 Barak 的 Computational Complexity: A Modern Approach、Goldreich 的 Computational Complexity: A Conceptual Perspective 深入讨论 §3.3 引入的随机计算、交互式证明、电路复杂性和近似困难性。它们对 PCP 的处理包含简短概述容易省略的特殊证明编码与概率保证。熟悉基本归约后，可以按主题选择章节。
对于 可计算性的深入学习，Soare 的 Turing Computability: Theory and Applications（2016）是当前经典递归论的标准文本——图灵度、递归可枚举集、oracle 计算，以及不可判定性的精细结构。这些内容远远超出 Sipser 的覆盖，适合计划认真进入数理逻辑侧面的读者。
原始论文仍然是有价值的一手来源。Turing 1936 年的 “On Computable Numbers” 提供原始机器模型与不可判定性论证。Cook 1971 年的论文和 Karp 1972 年的论文是 NP 完全性理论的奠基文献，也都可以直接阅读。Davis 编的 The Undecidable 把奠基十年的主要论文收录在一卷中。
关于与逻辑的连接，Hopcroft、Motwani 和 Ullman 的 Introduction to Automata Theory, Languages, and Computation（第 3 版，2006）在自动机和文法方面比 Sipser 更深入——适合需要为了编译器工作或形式化方法而掌握形式语言理论的读者。
| 书籍 | 作用 | 类型 |
|---|---|---|
| Sipser，Introduction to the Theory of Computation（第 3 版） | 经典入口；清晰且完整 | 入门 |
| Barak，Introduction to Theoretical Computer Science（免费） | 带代码 notebook 的现代开放配套 | 辅助 |
| Boolos、Burgess & Jeffrey，Computability and Logic（第 5 版） | 偏基础的另一种入口 | 入门 |
| Soare，Turing Computability | 经典递归论深入处理 | 深入 |
| Hopcroft、Motwani & Ullman，Intro to Automata Theory（第 3 版） | 形式语言理论 | 参考 |
| Turing（1936）、Cook（1971）、Karp（1972）原始论文 | 奠基文献 | 参考 |
| 复杂性理论桥梁：Arora & Barak，Computational Complexity（免费草稿） | 通往 §3.3 复杂性理论的进阶桥梁 | 辅助 |
| 复杂性理论桥梁：Goldreich，Computational Complexity: A Conceptual Perspective | 通往 §3.3 的另一种高级桥梁 | 辅助 |
| Davis 编，The Undecidable | 原始论文合集 | 辅助 |
课程与讲座
MIT 6.045J / 18.404（Theory of Computation，MIT OCW）提供配合自动机到复杂性学习顺序的讲座与练习。可以先做题，再看解答，比较其中的构造和证明义务与自己的尝试。
Scott Aaronson 的课程材料，包括量子复杂性和复杂性理论课程材料（可在其个人网站获取），特别适合想进入研究前沿或量子维度的读者。Aaronson 的写作同时具有技术精确性和对材料的热情。
MIT 6.046（Design and Analysis of Algorithms，MIT OCW 免费）覆盖算法设计中复杂性理论开始变得相关的层级——NP 完全性归约、近似算法、随机算法。它补充 6.045，并且是希望把理论连接到算法设计的读者的自然下一门课。
| 课程 | 平台 | 类型 |
|---|---|---|
| MIT 6.045J / 18.404 Theory of Computation（免费） | MIT OCW / YouTube | 入门 |
| MIT 6.046 Design and Analysis of Algorithms（免费） | MIT OCW | 深入 |
| Aaronson 复杂性与量子复杂性材料（免费） | scottaaronson.com | 深入 |
实践、工具与当前来源
JFLAP 提供自动机、文法与图灵机的交互环境。可以从两状态奇偶自动机和使用栈的括号配对识别器开始，跟踪接受与拒绝输入，再解释两种存储模型为何不同。理解这些简单模型后，再尝试通用机构造。
Automata Tutor v3（在线免费）为自动机和形式语言添加了练习与反馈层，包括有限自动机、正则表达式、上下文无关文法、下推自动机、图灵机，以及模型之间的转换。它有价值，是因为自动反馈让这个主题能够进行大量练习；它应该补充手写证明，而不是替代手写证明。
实现一个小型图灵机模拟器，显示纸带、状态与步数。设置步数上限可以让实验结束，但到达上限只表示被模拟机器尚未停机。尝试判定终止却失败，并不是不可判定性的证明；一般结论需要本节的对角论证。
Scott Aaronson 的 “Who Can Name the Bigger Number?” 和 “Why Philosophers Should Care About Computational Complexity”（均可在其网站免费获取）是两篇短文，不需要技术准备，却能讨论可计算性和复杂性结果在哲学和数学上的意义。与 Sipser 一起阅读，可以提供这些技术结果为什么重要的语境。
Complexity Zoo（complexityzoo.net，免费）是复杂性类及其关系的综合参考。在学习过程中作为参考使用，它有用；但作为起点，它会令人不知所措。应在遇到具体复杂性类时用它查询。
| 资源 | 平台 | 类型 |
|---|---|---|
| JFLAP（免费） | jflap.org | 实践 |
| Automata Tutor v3（免费） | automata-tutor.model.in.tum.de | 实践 |
| 通过 Complexity Zoo 查询复杂性类（免费） | complexityzoo.net | 参考 |
| Aaronson 文章（免费） | scottaaronson.com | 深入 |
| 模拟图灵机实现 | 本地 | 实践 |
陷阱
| 陷阱 | 为什么会误导 | 更好的做法 |
|---|---|---|
| 把 Church–Turing 论题当成模拟定理 | 形式等价可以证明；把它认同为有效计算，是进一步的论题。 | 区分数学模型，以及连接模型与非形式过程的主张。 |
| 混淆识别与判定 | 模拟可以确认终止，却未必能判定不终止。 | 说明肯定与否定实例上都必须发生什么。 |
| 把无限内存当成物理硬件 | 模型允许任意大的有限实例。 | 区分无界的问题族与固定的有限装置。 |
| 颠倒归约方向 | 方向决定哪个问题继承解法或困难性。 | 明确画出输入转换与假想求解器。 |
| 把 Rice 定理用于语法 | 定理讨论所计算函数的非平凡性质。 | 检查等价计算是否必须具有相同性质。 |
| 把一般限制当成每个实例都失败 | 受限情形可能具有有效算法。 | 识别定义域、所需保证与可接受的不完备性。 |