总算找到了一个像样的逻辑论坛。呵呵!
说点递归论把。递归论也叫可计算性理论,感觉是为了和计算机搭上关系,呵呵。
递归论现在标准读物就是
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的不可数势的性质看到,这样的矛盾远
多于形式逻辑分析所能解决的数量!
哥德尔定理证明的独到之处,在于用数学反过来
证明逻辑分析问题,前面我们已经看到,数学上
已经确定了的推理本来是可被拆成基本逻辑操作
来推理的。罗素曾有个想法,认为所有数学的推
理都可拆开成基本的逻辑运算去实现,好像是数
学可以变成逻辑学似的,今天的哲学界数学界摈
弃了罗素这个想法,认为这是不可能的。