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

5.1.3 希尔伯特纲领

希尔伯特认为应对数学基础危机就要证明数学一致性，即数学形式主义，目标是把各门数学形式化，建立相应的形式系统，证明一致性。他认为有三种数学理论：直观数学（算术、几何）、形式数学、元数学（证明论，研究一致性）。

在希尔伯特的学生伯内斯等人的帮助下提出希尔伯特纲领，主要主张：形式化、完全性、一致性、保守性、可判定性。

形式化指所有数学命题都能被严谨数学语言重述并按规则演算（有些概念如素数等，在原始的一阶语言中可能没有定义，但是要求能够定义，这样才可形式化）。

完全性指真数学命题都可被形式化证明。

一致性指可以形式证明且必须是有穷对象的有穷证明。

保守性指与真对象相关的命题证明可以借助理念对象，但要求消解掉，即可以不依赖理念对象证明命题（真实对象和理念对象：这里结合希尔伯特关于“无穷”的讨论进行说明。希尔伯特认为无穷分潜无穷和实无穷。希尔伯特说实无穷的论述运用的是一种虚拟语气。希尔伯特不假定实无穷，但是接受潜无穷，在他看来康托创造的无穷序数就是潜无穷，现实世界没有无穷，无穷是一种超乎经验之外的理念概念。作为无穷的一种，潜无穷虽然被接受，但是必须能够归约到有穷上来。有穷证明中“有穷”的涵义有三个：一是公式序列的长度必须是有穷的，二是公式序列中的公式必须是有穷命题，三是其中涉及的方法必须是有穷方法）。

可判定性指存在一种算法使得任给数学命题该算法都能判定它是不是可证的。

在希尔伯特看来，复杂系统的一致性，比如分析（Analysis），可以用更简单的系统证明，最终把所有数学的一致性归约到皮亚诺算术。哥德尔曾想按希尔伯特的指引，给出皮亚诺算术PA的一致性证明，并进一步给出分析的一致性证明，但得出了相悖的结果：哥德尔第一不完全性定理、哥德尔第二不完全性定理。

5.2 图灵可计算性

可计算性理论，又称递归论、算法理论、能行性理 。起初研究领域主要为可计算函数和图灵度，现在已经扩展至一般可计算性和可定义性，是数理逻辑、计科的独立分支。

5.2.1 三个基本概念：可计算性、算法概念、能行过程

计算来自原始人计数。后来对可计算性的等价的描述：(1) 哥德尔、埃尔布朗和克林尼根据方程演算定义的一般递归函数；(2) 丘奇通过 λ-演算定义的 λ-可定义函数；(3) 哥德尔和克林尼定义的部分递归函数；(4) 图灵基于图灵机的图灵可计算函数。(5) 波斯特基于典范演绎系统定义的函数；(6)马尔科夫基于基本字符集算法定义的可计算函数；(7) 谢佛德森和斯特吉斯基于无界存贮机（URM理想计算机）定义的可计算函数。这些理论促进了计 算工具的发展，电子计算机、DNA 计算机和量子计算机相继出现和应用。可计算性理论的基本概念、思想和方法已被广泛应用于计算机科学的各个领 域，如数据结构、计算机体系结构、算法设计与分析、编译方法与技术、程序设计语言 与语义分析等。

算法是术如《九章算术》，或者花剌子密algorithm表示算法。孙发特点：有输入输出、明确性、能行性、有穷性。明确性：关于算法的具体描述，每一步都必须清楚明白且没有歧义，从而保证算法能正确执行。 能行性：也称有效性或可行性。算法的每一步都必须能够通过有穷次的基本运算执行。有穷性：算法的执行过程必须在有穷步内终止，通常选择伪代码、流程图、控制表、程序设计语言等来描述算法。不满足有穷性的不叫算法而叫计算过程，例如计算机的操作系统就是一个计算过程，只有等待状态而不是停止状态。

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