本文尚在草稿状态，很难在短期内完成写作。发布出来旨在为初学者提供一些指引：书籍、资料、简介、历史还有我在不同年代的吐槽。请原谅我把吐槽也作为指南的一部分，必不可少的部分。--作者
教材
Introduction to the Theory of Computation ( ITOC ),
作者: Michael Sipser
出版社: Course Technology
出版年: 2012-6-27
ISBN: 9781133187790
主要内容
ITOC主讲三大内容：
- 什么是计算；
- 什么可计算；
- 如何度量计算的效率。
大致上来说，首先我们需要一种准确的表达法来说明到底计算本质上是什么。不同的科学家抽象出不同的计算模型，于是我们必须考查这些模型的表达能力(第一部分：什么是计算)。其次，我们发现计算是有局限的，不是什么问题都能计算，那到底什么是可计算的问题呢？有什么问题是不可计算的呢（或称为“不存在算法”）？（第二部分：什么可计算）如果某些问题是可解的，存在某种算法可以解决这个问题，那么这种算法的效率如何度量呢？我们需要一种通用的标准度量，並建立相关理论（第三部分：复杂性理论）。
需要强调的是，ITOCv3是本科教材，用于高年级的本科教学。
第0章 引论
0.1 自动机、可计算性、复杂性
0.2 数学表示与术语
0.3 定义、定理与证明
0.4 证明的类型
第1章 正则语言
Language（语言），对计算问题的高度抽象表达。整本书的重点是“计算“，如果能体会出在描述计算理论时语言的定义所产生的巨大作用，则理解就上了一个台阶。只是，第一章并不能产生这么大的效用，需持续关注。
1.1 有限自动机
概念：FA、语言、正则语言、正则操作
定理：正则语言类在正则操作（并、交、串联）下封闭；
1.2 非确定性
重点：体会计算的非确定性
难点：DFA与NFA的等价
对非确定性的两种解读：
- 并行执行；
- 总是猜对执行路径。哪一种更好？
问题：为什么我们需要“不确定性“？
1.3 正则表达
1.4 非正则语言
要点：自动机的计算局限性
难点：Pumping Lemma及其应用
第2章 上下文无关语言
2.1 上下文无关文法
重点：歧义性
问题1：为什么把能以不同方式生成的字符串称为歧义？
问题2：为什么需要“最左派生“这个定义？
2.2 下推自动机
问题0：下推自动机（PDA）比有限自动机的能力更强，主要体现在哪里？为什么PDA能力会更强呢？
问题1：在Lemma 2.21的证明中，如何确保可被匹配的串w一定会被匹配？
回答：构造算法是非确定性算法。重点体会非确定性选择的含义。
问题2：在Lemma 2.27的证明中，如果p不可达q，那么的构造是否还合法（会出现不合法的情况）？
回答：暂无
2.3 非上下文无关语言
2.4 （忽略）
第3章 丘奇-图灵论题
本章的主要内容是介绍图灵机及其相关概念，旨在进一步刻画计算（算法）的本质。重点区分两个概念：图灵可判定与图灵可识别。从算法的角度看，前者要求计算在有限步之后结束，而后者没有。明白了这种区别，对计算机的有限计算将会有更深入的理解。
3.1图灵机
一种计算模型，定义繁琐，但并无理解难点。
3.2 图灵机的各种变种
3.3 算法的定义
第4章 判定性
4.1 可判定语言
4.2 停机问题
重点：对角线法、停机问题不可判定的证明
关于停机问题的一种充满诗意的证明
5 可归约性
这一章的重点是理解归约的本质、过程与应用。
5.1 语言理论中的不可判定问题
针对RL与CFL的若干语言形成的判定性问题进行证明。
5.2 一个简单的不可判定问题：PCP问题
只是一个证明！PCP问题的描述很简单，其不可判定性倒是颇令人感到意外。这里除了一个结论，一个冗长的证明外，内容不多。
5.3 不可判定问题的形式化定义：映射可归约性
重点：Mapping Reducibility的定义
第6章 计算理论的高级专题
6.1. 递归定理
递归定理展示“程序自我复制是可能的”这样一个简单而令人吃惊的结论。
The Quine Page，里面收集了大量不同语言写成的Quine程序：自己输出自己源代码的程序。
待续
参考书
- Introduction to Automata Theory, Languages, and Computation (IALC), John E. Hopcroft, Rajeev Motwani, Jeffrey D Ullman，Addison Wesley, 2006-7-15. (不能不说的另一本鼎鼎有名的ITOC book。)
- CS-581: Theory of Computation. (By Harry Porter -D)
- A free book of ITOC (another ITOC).
- MIT 18. 404J,Sipser 授课视频
选课建议
首先，这是一门为有志气有思想不怕困难的同学开设的课程。其次，这是一门比较困难的理论课程，需要大量的阅读与思考。第三，学这门课很难立即给你带来那种让同学们羡慕的实践技能、那些传说中大公司招人所需的技能，但是它能给你带来思想上的重大转变（如果你认真学的话）。第四，如果你对理论不感兴趣，请不要选，尽管我知道所谓“不喜欢理论”的人通常不知道什么是理论。最后，如果你选择了读研，我建议你选，因为你选择读研就隐含地意味你必须面对理论，也许你不同意我这个看法也没关系。
ITOC 在某学院的本科开课历史
- 2014年秋季，2012级网络工程专业首次授课；
- 2015年秋季，2013级网络工程专业第二次授课；
- 2016年秋季，2014级因故停开
- 2017年秋季，2015级因故停开
- 2018年秋季，2016级待定
...... - 2023年春季，2022级（大一新生）开课！！！
以下废话
我年轻的时候曾经吐槽说：
TOC是科普，无论是全职师奶还是IT民工都可以读之且获得乐趣，何况一众非常有可能是拥有211重点大学双一流学科本科学位的全职师奶或者IT民工。
阅读TOC不需要高IQ，不要总是拿自己的IQ忽悠自己和他人。
TOC是思维的训练，文化的熏陶，你们不缺少知识、不缺少信息，缺的是熏陶。
TOC是巨人出没的领域，你不走入巨人的领地，怎么能站到巨人的肩膀上呢？
2017年7月整理
2023年3月整理
