递归论（Recursion Theory）

研究生选修课，4学时，秋季开课

先修课程：一阶逻辑

课程目的：

掌握可计算性理论的基础知识，掌握哥德尔不完全性定理的证明，了解图灵机、复杂性的基本概念。

内容提要：

本课程为计算性理论与不完全性定理的基础知识，包括：

一、原始递归函数，初等函数；

二、图灵机，通用函数和通用机；

三、直观能行性的各种各样及其等价性；

四、形式系统的算术化、不完全性定理；

五、复杂性的基本概念。

教材：

R. Murawski: Recursive Functions and Metamathematics, Kluwer Academic Publishers, 1999.

参考书：

郭世铭：递归论导论，中国社会科学出版社，1998

M. 戴维斯：可计算性与不可解性，北京大学出版社，1984

N. Cutland，Computability：An Introduction to Recursive Function Theory，Cambridge University Press，New york，1980

成绩评定办法：

习题完成情况和成绩占40%，期末考试成绩占60%。

教学大纲：