T007522　可计算性理论

---

张宏裕编著。

天津科学技术出版社1989年5月版。17．3万字。

用理想计算机作数学模型，系统地讲述可计算函数，介绍了原始递归函数类P₀、一般递归函数类G₀和部分递归归函数类D₀，证明了P₀G₀D₀，进一步证明了可计算函数与部分递归函数是等价的。

还讲述了不可判定问题，如停机问题不可解及希尔贝特(Hilbert)第十问题。

最后，作者对相对递归性和算术分层理论作了进一步的研究。书中系统地论述了克林尼的分层理论，其中关于归纳集合的研究，为施归于函数结构证明某种性质提供了理想的根据。