计算理论导引

本科时候学的最痛苦的一门课没有之一。之前看过王垠对于计算理论用图灵机引入可计算性的吐槽文章深以为然……究竟为什么会有图灵机作规约的题目？？？图灵机真的适合作为引入可计算性的引子吗？？？横向比较了下，德语区（不知道欧陆其他国家如何，但德语区应该区别不大）的理论性普遍应该是最强的，Sipser的这本书也只能作为参考。计算机科班学生学过计算理论后，我觉得会对搞数学的那帮会有更深的敬畏吧……考试题每次最后一道证明NPC的问题总是做不出来，之前还有一道表面是描述图灵机实际是考察对角线证明的题目，很巧妙。期末考试24页，8道题目，3个半小时，60分满分24分及格，百分之40左右的通过率，纠结自己能不能通过考试，辗转不能眠，这是我人生目前为止经历过的最难忘也是最绝望的记忆之一……

理论计算机科学的入门好书

本书可以看做编译器原理的数学逻辑原理书。自动机 可计算性 复杂度。密码使问题变复杂，其他任务都是化简。自动机：有穷自动机（状态）和正则表达式在描述能力上等价（有限存储）；上下文化无关（下推自动机无限存储而且是栈机制）；有穷状态机类似于图灵机（无限存储任意访问数据）学习过数学基础（元数学）和离散数学这本书就基本上理解了。编译原理按照乔姆斯基文法结构的分类：词法：有穷自动机（ finite automata）和正则表达式（regular expression）乔姆斯基3型；程序设计乔姆斯基的2型— 与乔姆斯基分类结构（ Chomsky hierarchy）一样— 包括了文法的4个层次：0型、1型、2型和3型文法，且其中的每一个都是其前者的专门化计算理论对应着乔姆斯基的4个文法模型，0型文法的是图

清晰..

写的非常好，非常好。能让人学明白的书。

CS411书目

可判定，可识别，可计算，复杂性。真的很精彩。对于自动机的了解有了新的认识。对于还有不可计算的问题感到非常神奇。深深感到理论的魅力(就是我学习能力一般走不了学术路线了)

补标

看过前两张，状态机部分看的认真点，到上下文无关文法止，比较费脑