《递归论》求取 ⇩

绪论1

§01．违归论的对象1

§02．基本概念，组成规则4

§03．可计算性与可判定性14

§04．函数，直接定义的函数15

§05．迭置(叠置)18

§06．特征函数24

§07．配对函数27

§08．堆积函数与求项函数33

§09．叠置的化归35

第一章 算子41

§10．几个重要的算子41

§11．算子的一种分类52

§12．算子的相互表示与化归(上)54

§13．算子的相互表示与化归(下)67

§14．递归生成集与函数的组成过程70

§15．递归生成函数集的典型构成73

§16．控制函数与枚举函数75

§20．三大函数集81

第二章 初等函数集81

§21．初等函数集82

§22．初等函数集的分类85

§23．初等函数集的另一构成90

§24．初基函数集92

§25．基底函数集96

§26．多项式集97

§27．五则函数集106

§30．原始递归式及其简化111

第三章 原始递归函数111

§31．单重递归式116

§32．嵌套单重递归式119

§33．作用域变异的递归式122

§34．含有算子的递归式127

§35．多重递归式129

§36．非原始递归函数的一例134

§37．原始递归函数的分类138

§40．一般递归式及其简化141

第四章 递归函数集141

§41．一般递归函数集147

§42．一般递归式的加强150

§43．一般递归式与有序递归式153

§44．递归函数的典范表示156

§45．可在有限步骤内计算的函数159

§46．?可定义函数与组合子函数169

§47．可用机器计算的函数178

§48．可偏函数190

§49．可偏函数的递归性198

第五章 递归枚举性208

§50．归举集(递归枚举集)208

§51．可偏函数与归举集213

§52．归举谓词(归举关系)216

§53．存在化多项谓词(狄氏谓词)219

§54．归举集的分类229

§55．产生集与创造集233

§56．禁集与单纯集238

§60．个别问题与大量问题240

第六章 判定问题240

§61．基本的不可判定问题243

§62．枚举问题(编号问题)250

§63．数学上的不可判定问题251

§64．Church-Turing论点254

第七章 谱系(分层)及计算复杂性259

§70．算术谱系259

§71．算术谱系的基本性质262

§72．算术谱系的结构264

§73．相对算术谱系266

§74．解析谱系269

§75．计算复杂性274

第八章 化归与不可解度282

§80．化归与不可解度总论282

§81．多一化归与一一化归285

§82．T化归(相对化归)293

§83．化归论的进一步结果298

参考文献307