《计算模型导引》

研究生理论计算机科学入门课程《计算理论导引》的教材《计算模型导引》的非官方习题解析，主讲教师：宋方敏（教授），习题由助教讲授。南京大学计算机科学与技术系版权所有。

书本前言节选

计算(Computation)概念的形式化是20世纪的重大科学成果之一。

很久以来，人们一直在问“什么是计算”、“计算的范围有多大”等问题。在20世纪30年代，Church， Turing，Gödel和Kleene等人各自提出模型来描述计算概念，形成所谓的可计算理论(computablility theory)。该理论旨在精确描述直接概念——可计算函数。从此，标准的计算模型出现。今日之计算机可看作此模型的实现。从计算机科学的角度来看，该理论解决以下问题：计算机可以做什么？计算机的能力有极限吗？

本书主要介绍递归函数算盘机、$\lambda$-演算、组合逻辑和Turing机等计算模型。这些模型对计算机科学、哲学和数学基础产生了巨大而深远的影响。

作者的话

实在是听不懂宋公的课，习题也不会做，只能做些微小的事情。存在疏漏和不足之处，希望读者批评指正。

English Introduction

This is an unofficial solution manual to the book of "Introduction to Models of Computation" by Prof. Fangmin Song. The solutions are given in class by TAs.

I hope this can help my graduate partners taking this class in Nanjing University.

Enjoy it.