递归论 哥德尔，形式逻辑

总算找到了一个像样的逻辑论坛。呵呵！
说点递归论把。递归论也叫可计算性理论，感觉是为了和计算机搭上关系，呵呵。
递归论现在标准读物就是
Soare Recursively Enumerable Sets and Degrees.
已经读了大半了，感觉不太困难。只是后面练习狂多，而且老板要求尽量全部完成，这个挺痛苦的 。呵呵！
之前最好看一些 数理逻辑的入门教材。 还有 Davis "Computability and Unsolvability" 之前最好看看。 或者 Cutland 的 "computability" 也可以。否则一进来那个 Turing 论题 Church论题可能就会觉得特玄乎。
现在递归论发展有点到瓶颈了，纯递归论（Core computability）好像是说现在越来越难走了，简单的东西都做完了，剩下的都是硬骨头。所以现在很多做这方面的人都在试图将递归论应用到其他领域。有应用到代数（computable algebra），组合数学，Peano arithmetic，分析和拓扑(computable topology and computable analysis)，模型论（effective model theory），能行数学（effective mathematics），解决很多经典数学中的问题是否可以effective，不过到底有什么意义就不大清楚了，呵呵。还有的它应用到计算复杂性中去，这算比较多的，现在搞复杂性的一些专家就是从递归论出身的。现在还有应用的比较成功的，也是比较热门的的是和随机性的结合,即算法信息论，也叫描述复杂性。 Chicago 的 Soare主页上有 Downey的一本写这个的书，可以下载的。据说有人利用递归论成功地解决了Riemann几何中的问题，最终结果看不出任何递归论的痕迹，很牛吧！

 

哥德尔不完备性定理

百科名片

哥德尔不完备性定理的提出和证明就是为了解决 怀特海上述猜想，它指出：使用层层外延法扩张 形式逻辑体系并不能清除其总和的矛盾！ 哥德尔最妙的想法就是把一切逻辑运算视作一种 二进制代码(CODE)，就例如，“与”可对应为1， “或”可对应为10，“非”可对应为11。但这些 二进制数却被他再转换成小数，如0.1，0.01， 0.11，组合逻辑运算不过是这三种码的组合，也 就是更复杂的小数。

目录

递归

小数代表逻辑运算

二进制与十进制

有理数和无理数

结论

 

 

递归

　　递归：逻辑运算里有一种调用自身的运算，称为

　　“递归”。递归术语今天是编程算法里最基本的

　　运算方法之一。递归有两种结局：1.终止于有

　　限次数的操作；2.无限递归下去，在编程上被

　　称为死循环。

小数代表逻辑运算

　　当逻辑体系按照怀特海的办法延拓到一个新的，

　　更大的逻辑体系时，旧的逻辑体系中的操作如果

　　被新的体系调用，就会出现递归，递归有时是无

　　限次数的(这是允许的，不象计算机运算不允许)，

　　在此情况下，由二进制代码所代表的逻辑运算将

　　出现无限循环的小数。

　　这样，哥德尔就用递归把每一次形式逻辑体系的

　　外延后的操作，用有限小数和无限循环小数代

　　表出来，而且他还证明了，这种代表是唯一对应

　　的，也就是说，每一二进制有限小数或无限循

　　环小数皆唯一对应于怀特海意义下的无限扩张逻

　　辑体系下的某一逻辑操作。

二进制与十进制

　　二进制数与十进制数之间能建 立起唯一对应关

　　系，因之，实轴上0-1的一端(剃除掉两个端点，

　　0、1)的所有小数都可以由二进 制小数表出，

　　而且，两种进位制里的有限小数和无限循环

　　小数都对应。

有理数和无理数

　　任何有限小数和无限不循环小数都属于0-1之间

　　的有理数。0-1数段的实数除了全部含于其中的

　　有理数以外，还存在着无理数,例如2分之2的平

　　方根。如果我们表0-1数段的所有有理数集合为

　　Ro，表剩下的所有无理数集合为Io，则可证明：

　　Ro 对等于 R;

　　Io 对等于 I

　　这里的R、I见(一)中例的定义。因此，我们遂有

　　Ro有可数势，而Io有不可数势。

　　哥德尔证明了：怀特海意义下的无限延拓形式逻

　　辑体系的所有逻辑操作所组成的集合与Ro之间能

　　够建立起1-1的对应关系，也就是说，这两个集

　　合对等，因此，它们有相同的势。即都具有可数

　　势。

　　但是，如果我们把0-1间任意一个无理数对应成

　　一个逻辑操作，因为它无限不循环，这个操作是

　　我们不能确定的，但却能有限截断后知道的，我

　　们就可以理解成不能用确定的逻辑操作去解决的，

　　或者换个口吻，说成是矛盾。

结论

　　于是，哥德尔就得出了结论，形式逻辑分析不能

　　用来解决认识中的所有出现的矛盾，更有甚者，

　　我们由Io的不可数势的性质看到，这样的矛盾远

　　多于形式逻辑分析所能解决的数量！

　　哥德尔定理证明的独到之处，在于用数学反过来

　　证明逻辑分析问题，前面我们已经看到，数学上

　　已经确定了的推理本来是可被拆成基本逻辑操作

　　来推理的。罗素曾有个想法，认为所有数学的推

　　理都可拆开成基本的逻辑运算去实现，好像是数

　　学可以变成逻辑学似的，今天的哲学界数学界摈

　　弃了罗素这个想法，认为这是不可能的。