数理逻辑-余俊伟（三） (4-2)

能行过程：在数理逻辑和计算机科学中，算法也是一个能行过程或能行方法，即能解决某问题。能行过 程的特点与算法基本是一样的，区别在于：前者稍显粗略，因为它允许用自然语言描述， 不过可读性却比较强；后者十分严格，是用选择伪代码、流程图、控制表、程序设计语 言等进行描述的，不允许使用自然语言描述，不过可读性不是很强。因此，算法一定是 能行过程，而能行过程不一定是算法，但能行过程却一定可以通过语言的转换变成算法。

5.2.2 图灵可计算性

此节先说了图灵机如何运算，然后用图灵机描述可计算性。涉及部分函数的概念。

不同书不同图灵机，但等价。

5.2.3 部分递归函数

除了图灵机，可计算性有另一种精确描述：哥德尔–克林尼式的数学描述。它 可以从最简单的、直观的可计算函数逐步地生成（全部的）直观的可计算函数利于人们把握具体的直观可计算函数。最终，我们还会说明所有的部分递归函数都是图灵可计算的。

原始递归函数：给出0也就是零值函数，给出后继函数，给出投影函数，然后复合函数。再原始递归。原始递归函数类是包含初始函数并对复合和原始递归封闭的最小函数类。称函数 f 是原始递归的，如果它属于原始递归函数类。引入极小算子（minimalisation operator）和正则（regular）极小算子。定义递归函数和部分递归函数。递归函数类是包含初始函数并对复合、原始递归和正则极小算子封闭的最小函数类；称函数f是递归的，如果它属于递归函数类。 部分递归函数类是包含初始函数并对复合、原始递归和极小算子封闭的最小函数类； 称函数f 是部分递归的，如果它属于部分递归函数类。 递归函数类不等于图灵可计算函数类，它只是图灵可计算函数的真 类，因为下文会证明图灵可计算函数类就是部分递归函数类。

5.2.4 丘奇图灵论题

丘奇给出 λ-可定义函数这种可计算性描述的同时，还提出了丘奇论题：直观上可计算的函数类就是 λ-可定义函数类。图灵 1936 年给出图灵可计算函数这 种可计算性描述后，1937 年又证明了图灵可计算性和 λ-可定义性的等价。用图灵可计算函数对丘奇论题进行了重新表述，得到丘奇–图灵论题：直观上可计算的函数类就是图灵可计算函数类。

5.2.5 可计算枚举集

可计算集和可计算枚举集又可叫递归集和递归可枚举集。

5.3 第一不完全性

设 T 是可计算公理化的、一致的 L1-理论。作为目标，希望 T 是完全的， 即 T 等于 Th(M)。不妨进一步假设，能够用语言 L1 谈论自身基本语法和自 公理到定理的证明。一般说来，只要 L1 可以谈论自然数的性质，那么 L1 就 能通过编码的方式谈论自身语法。

罗宾森算术比皮亚诺算术要弱很多，一来定理表述可以更一般， 二来标准算术模型的真语句集与罗宾森算术的差异比其与皮亚诺算术的差异更大。

本节哥德尔第一不完全性定理的证明思路是：首先证明所有的可计算关系都是可表 示的，然后证明算术化的语法概念是可计算的，而后在此基础上证明不动点引理，从而 基于可表示的证明概念由不动点引理推出哥德尔第一不完全性定理。

5.3.1 罗宾森算术

数学联邦政治世界观提示您：看后求收藏（同人小说网http://tongren.me），接着再看更方便。