一些名词条目
- 形式系统
- 希尔伯特计划
- 数学悖论
- 公理集合论
- 古德斯坦定理
- 皮亚诺公理
- 数学基础
- Set Theory/集合论
- 判定问题
- 希尔伯特第十题与图灵机
- 邱奇与Lambda
- 康托尔与集合论
- 罗素悖论与元数学
- 奥卡姆剃刀原理
- 连续统假设（未解决）：不存在一个集合，其基数绝对大于可列集（可数），而绝对小于实数集（不可数）
- 一致性：一个形式系统中，任意由公理和规则推导出的定理（包含公理）都不会矛盾
- 完备性：一个形式系统中，任何公式都能通过有限的定理推导出
- 可判定性：存在一个通用算法可以用来判断任意公式的可证明性
- 形式系统：包括定义（在一阶谓词系统中指的是符号）、推演法则和公式（在一阶谓词系统中指的是一系列无意义符号的排列）
- 一阶谓词逻辑：定义的符号不带有其它任何属性
一些疑问
- 希尔伯特的23三个问题第二题，『算术公理系统的无矛盾性』是什么意思？
- 整个数学系统是完备的吗？
- 整个数学系统是一致的吗？
- 整个数学系统是可判定的吗？
一些结论
- 哥德尔证明第一条的多种表述
- 形式系统中，完备性和一致性不能同时达到（脱离算术系统而言）
- 给定任意有限多条皮亚诺算术的公理，都存在一些正确的命题，无法用所给公理来证明
- 一个形式体系如果一致，且它足够强到包含皮亚诺算术公理时，就能在里面构造出无法证明也无法证否的命题
- 哥德尔证明第二条的多种表述
- 一个形式体系如果一致，那么就不能用它本身证明它的一致性
- 一阶谓词逻辑是完备的、一致的
- 判定过程的存在与否和完备性无关
一些素材
希尔伯特发表演讲时的结尾语
Wir müssen wissen
Wir werden wissen
我们必须知道，我们必将知道
一阶谓词逻辑的可判定性
- 一阶谓词逻辑是完备的、一致的，所以我们可以列举所有的定理{p_1,p_2…p_n…}
- 为了判定一个公式是否可证明，我们可以将公式、[非公式]和定理集合中的元素进行比对，看公式是否是定理或者定理的否定，如果是，则说明可以判断公式的对错——即可证明的，否则就不是；或者换一种做法，将定理集合的幂集元素依次与公式进行“特殊操作”，这个“特殊操作”就是对每个幂集{p_i1~p_ik}，计算以下算式的真值： p_i1 合取 p_i2 合取 … p_ik 合取 非（公式） p_i1 合取 p_i2 合取 … p_ik 合取 （公式） 前面的公式恒为假则说明这个公式是定理，后一个式子恒为假则说明这个公式是定理的否定。后一种方法的好处就是能说明可用哪些公式来证明，而且更容易理解
- 用完上面两种方法，貌似找到了一阶谓词逻辑的判定通用方法（一阶谓词逻辑是傻瓜式的计算），但实际上错了，我们说过公式有可能是根本不知道结构的，在这种情况下根本不可能得到公式的在{p_i1~p_1k}各种真值组合下的真值，因此就无从判定起，也就是说，这两种方法必须依赖一点——知道公式结构或者公式恒为真/假（此时上面的判断式不受公式影响，不过实际情况是都知道公式恒为真/假了，显然是可证明的），于是我们只能说以上两种判定方法是半可判定的
可计算数
可以由图灵机计算的数称为可计算数
- 0.1：显然有限数肯定是可以计算的
- 1/3：这是个无限数，但1/3规律性很强，小数位每位都为3，显然也可以计算
- PI、e、sqrt(2)：这三个同样是无限数，而且展开小数部分会发现完全没有规律，但是它们依旧是可计算的，为什么呢？因为它们都可以通过一定的算法得到，对应的就是一个固定的图灵机
说了这么多，怎么不举个不可计算数的例子看看？如果读者这么问，那我只能遗憾的摇摇头：我们是没有办法构造不可计算数（不可计算数就等效于不可定义数？）的，其实这个也很好理解，首先，不可计算数肯定是无限数，而且是无规律数，同时它又不能通过公式去得到（如果可以通过公式构造，那我就根据公式构造图灵机，从而就可以计算这个数了），那么我们还有什么方式构造出这个无限数？貌似没有了，而且即使有新的方法我仍然可以通过图灵机模拟这种方法，这可能让人有点泄气，但幸运的是，这种数对我们来说一般是无用的，所以我们没必要在上面花时间。
不可判定问题就是不可解问题，也等同于不可计算问题（英文描述为Undecidable Problem）
注：不可计算数是不可定义数的超集合，即有的定义数也是不可计算的
可计算性
邱奇-图灵论题算是可计算性的最终定义，不过其本质和图灵、邱奇等人的独立研究没有差异，所以我们最终可以用一句简短的话来概括它：对问题存在一种有限指令、机械的方法使问题在有限步解决。有了定义，我们试着判断几个问题的可计算性
- 输出1/3的所有位数：不能在有限步解决，所以是不可计算的，而且本身这个问题就是存在缺陷的，因为它直接要求
- 证明哥德巴赫猜想：至今为止我们可能还没研究出一种证明方法，所以只能进行枚举，但这显然不能在有限步解决，所以也是不可计算的
复杂性理论
1969年，库克扩展图灵对于计算、不可计算理论，也就有了复杂性理论