杨跃教授《递归论》讲座

 

2007年10月11日下午3:00-5:00，由北京大学哲学系、北京书生公司、清华大学人文社会科学学院哲学系共同举办会议，邀请来自荷兰阿姆斯特丹大学人文学院哲学系的语言哲学教授Martin Stokhof做了题为“Hand or Hammer? On Formal and Natural Languages in Semantics”（“手还是锤子？论语义学中的形式语言和自然语言”）的演讲。北京大学哲学系的周北海教授主持。清华大学哲学系王路教授，北京大学哲学系叶峰教授、邢滔滔教授，中国人民大学刘晓力教授，以及来自清华大学、北京大学、中国人民大学、北京师范大学等院校的研究生参加了会议。Martin Stokhof教授所谈论的问题主要是自然语言和形式语言的关系的问题，他揭示了潜在于语法形式和逻辑形式的区分之中的两个基本假定，并且表明这些假定如何有助于形成一种特殊的方法论，这些假定与语义学作为一门学科的地位的关系。讲座后各位老师和研究生与教授进行了深入的讨论，既涉及如何理解语义学的基本假定的问题，又涉及一些具体的自然语言语义学研究的例子。

2007年12月20日下午，新加坡国立大学的杨跃教授来到北大，在逻辑、语言与认知研究中心作了题为“关于叶尔绍夫层谱初等等价问题的一个新结果”的报告。

杨跃教授先从递归论的概况讲起。递归论也称可计算性理论，是数理逻辑的四个主要分支之一，主要研究可计算性或可定义性。

随后，杨跃教授讲述了递归论的两个特征。数学中经常有这样的问题：我们采用的方法对于我们想要达到的目标来讲是充分的吗？在这种情况下就需要对采用的方法进行分析，而这经常涉及到递归论。哥德尔的不完全性定理是说，存在在算术的标准模型下为真的命题，其在皮亚诺算术系统下不可证。除了哥德尔句之外，这里还有一个更数学化的命题，其为真但在皮亚诺算术系统下不可证。通过一种简单的构造，可以定义出一个自然数的无穷序列。这个序列在开始时增长速度极快，且似乎会永远增长下去。采用超穷归纳（到e0），利用序数的良序性，可以证明：这个序列在有穷步之内会下降到0。这个定理在皮亚诺算术下是不可证的。直观上其原因在于，皮亚诺算术系统在构造“增长速度”方面存有极限，在其之内无法构造出增长速度如此快的序列。递归论的特征之一就是其可以对我们采用的工具进行分析。递归论的第二个特征是：经常需要使用它来分析复杂性。算术分层理论就是这样一个例子。这个特征还体现在如下一些研究方向当中：复杂性方面的各种归约关系很自然地产生等价关系，研究归约关系和相应等价类的结构的理论称为度论；对递归可枚举集e和e*形成的格的研究；应用递归论，比如递归模型论，算法随机性研究等。

杨跃教授提到，也许把递归论称为定义理论更合适。一个自然数的子集是S1当且仅当存在一个S01公式可以选出这个集合。能够得到，自然数的递归子集的集合恰好就是S0的集合；自然数的递归可枚举子集的集合恰好就是S1的集合；等等。这部分说明了递归论是对可定义性的研究。

随后，杨跃教授把报告转向了自己的研究领域。

递归论除了研究“绝对”的可计算性之外，还研究“相对”的可计算性。自然数的子集并不都是可计算的。对于两个集合A和B来说，假设A是可计算的，那么B也是可计算的，在这种情况下，我们说A相对于B是可计算的。依据这种相对可计算性产生的等价关系，可以定义出图灵度，即某种由自然数子集组成的等价类。杨跃教授讲到，对于由所有图灵度和相对可计算关系组成的结构D的研究是当代递归论研究领域的核心。

一个自然数的子集是可计算的当且仅当存在一个程序P，这个程序总是可以停止，且对任一自然数来说，若它在这个集合当中，则这个程序输出1，若不在，这个程序输出0。程序总是有限长，因此可以把所有的程序列出来，P0, P1…。显然，存在一些程序，在某种输入情况下也许永远不会停止。定义集合K如下K = {Pi：Pi在输入时停止}。显然K不是递归的，而是递归可枚举的。令集合K的图灵度是0?。根据n-递归可枚举这个概念，可以把0?切割成很多片，这就是叶尔绍夫层谱。在算术分层理论的基础之上，从模型的角度对片与片之间的等价关系进行研究，是递归论的一个重要研究领域。最后，杨跃教授介绍了最近自己和南京大学喻良教授合作在这方面取得的一个新结果。

 

（琚凤魁)