《计算模型导引》书评

计算概念的形式化是20世纪的重大科学进展之一

此书为南京大学宋方敏老师《计算模型导引》的教材，前面@廿五 已经说得很详细了，这本书的组织结构是主要分为三个部分讲解：递归函数论、lambda演算、图灵机（其实还有算盘机）。确如宋公在书末结语写道的，计算概念的形式化是20世纪的重大科学进展之一。学习计算模型之后，对于什么是计算有了更清楚的认识。每个结论及其证明的确都是很美的，很漂亮的。以上是说这门课的意义，至于这本书。整本书主要是要点式堆积概念和定义，insight不多，并不适合自学。宋公在课上也曾说，“有的同学喜欢回去自学，我这本书不能自学的。来了一流大学，就应该来听教授讲课，不要自学。”（原话大意如此，偶有偏差）如果要学习这本书，建议在lambda演算一章可以参考Henk Barendregt 和Erik Barendsen的讲义Introduction to Lambda Calculus，符号系统和此书一样，但是examples更多，更加容易理解。图灵机一章的符号约定和国外通用的Michael Sipser的教材《Introduction to the Theory of Computation》不太一致，而且定义方式显得有点突兀。建议参考一下Sipser的书。