1判定器、识别器与余识别器
闭卷重建判定器、识别器与余识别器的对象、状态、事件、不变量与一个失败反例。
理论计算：自动机、可计算性与复杂性 · 小纸条
选一章打印。双面打印（按长边翻页）后沿虚线剪开，每张卡片正面题目、背面答案。
第 1 页 · 正面（题目）
2自动机问题的可判定性
闭卷重建自动机问题的可判定性的对象、状态、事件、不变量与一个失败反例。
3CFG接受与空性
闭卷重建CFG接受与空性的对象、状态、事件、不变量与一个失败反例。
4对角化的逻辑骨架
闭卷重建对角化的逻辑骨架的对象、状态、事件、不变量与一个失败反例。
5接受问题与停机问题
闭卷重建接受问题与停机问题的对象、状态、事件、不变量与一个失败反例。
6实验：有限自动机性质判定
闭卷重建实验：有限自动机性质判定的对象、状态、事件、不变量与一个失败反例。
7证明：Rice定理使用边界
闭卷重建证明：Rice定理使用边界的对象、状态、事件、不变量与一个失败反例。
第 1 页 · 背面（答案）
核心机制：DFA接受、空语言、等价等问题可通过运行或有限图可达性判定；实验入口：把DFA空语言化为初态到任一终态的可达性，给出终止和正确性证明；边界：具体输入串不被接受不能推出语言为空；搜索图时要覆盖所有可达状态。
核心机制：判定器对所有输入停机；识别器只保证成员最终接受；语言可判定当且仅当它和补语言都可识别；实验入口：用交错模拟两个识别器构造判定器，并说明至少一方必停的理由；边界：顺序先跑一个识别器可能永远等不到另一个，不能替代交错。
核心机制：假设存在覆盖所有对象的编号，再构造在第i项第i输入上反向行为的新对象，得到无法处于清单中的矛盾；实验入口：先在二进制无限矩阵上演练对角翻转，再迁移到机器语言；边界：构造对象必须仍属于讨论全集；不能用有限表格冒充无限对角论证。
核心机制：CFG成员可用CYK等算法判定，空性可求可生成且从开始符可达的符号；实验入口：分别写两算法的有限状态空间和终止度量；边界：CFG等价与二义性并不因成员可判定而自动可判定。
核心机制：实现DFA语言空性与有限性判定：可达终态与可达且可通终态的环决定结果；实验入口：测试空、有限非空、无限和含无关环四类自动机；边界：这是有限图算法，不能直接推广到任意图灵机状态空间。
核心机制：通过自指或归约证明A_TM和HALT_TM不可判定，同时区分它们的可识别性；实验入口：写出假想判定器接口、包装机器和矛盾输入，逐步标调用与输出；边界：不可判定不等于每个实例都难，也不等于问题不可识别。
核心机制：任何非平凡的图灵可识别语言语义性质不可判定，句法性质不在结论内；实验入口：为语言是否为空构造归约草图，再解释状态数是否为偶数为何不适用；边界：必须验证性质只依赖识别语言且非平凡；程序运行时间不是纯语言语义性质。