第一章 递归函数

引言

人类在 20 世纪为形式化“可计算”这个概念，提出了许多模型。本章将介绍递归函数类及其所刻画的直觉可计算函数类，这是一个重要的计算模型。

历史上，在 1936 年由 Gödel，Herbrand 和 Kleene 提出一般递归函数，这是由等式演算定义的。同年，由 Gödel 和 Kleene 提出 $\mu$-递归函数和部分递归函数。Kleene 证明一般递归函数集等同于 $\mu$-递归函数集。有时将一般递归简称为递归。

递归函数类在本书后继章节中将经常被引用。

本章小结

在本章我们介绍了函数集 $\mathcal{IF}$，$\mathcal{BF}$，$\mathcal{EF}$,$\mathcal{PRF}$，$\mathcal{ITF}$，$\mathcal{GRF}$ 和 $\mathcal{RF}$，它们之间有下述关系 $\mathcal{IF} \subset \mathcal{BF} \subset \mathcal{EF} \subset \mathcal{PRF} = \mathcal{ITF} \subset \mathcal{GRF} \subset \mathcal{RF}$ 在提出 $\mathcal{GRF}$ 和 $\mathcal{RF}$ 后，人们认为直觉可计算的全函数集等同于 $\mathcal{GRF}$，而直觉可计算的部分函数集等同于 $\mathcal{RF}$，这就是所谓的 Church-Turing 论题。在第五章将会对该论题作进一步论述。

作为一个计算模型，$\mathcal{GRF}$ 在以后各章将经常被利用。