3.17

图灵机

今天读了 Chapter 3,4 ， 建立起了从正则语言，到上下文无关语言，再到图灵可判定语言，最后到图灵可识别语言的完整链条。

学习了枚举器这个有用的概念，它可以用来证明许多命题，比如每个无穷图灵可识别语言都有无穷可判定的子集。

遇到了一个非常棘手的题目：3.13：证明把图灵机的左键扣掉，换成静止不动，会让它和 DFA 等价。我虽然想到了用 Myhill–Nerode theorem，但具体论证看了答案才明白，非常巧妙！

明天有两节课，不知道能否读完 Chapter 5, 6，如果按一天两章进行，需要周四才能读完，那么底线就是周五必须读完，周末继续 CS229