本网讯（通讯员杨新宇）10月25日下午，新加坡国立大学数学系杨跃教授在振华楼biwn必赢B214报告厅作了“论算法”的学术讲座。讲座由程勇教授主持，院内外300余名观众通过线上线下两种方式参加了此次讲座。

首先程勇教授向观众介绍了主讲人——杨跃教授是北京大学理学学士、康奈尔大学数学博士，在新加坡国立大学长期从事递归论、反推数学及数学哲学研究，多篇论文为国际顶刊收录。本次讲座从经典递归论对自然数集上的算法的研究开始，进而讨论如何在高阶对象上建立可计算性理论。

杨跃教授以欧几里得算法这一直观的例子引入主题，概括了算法的几大特征：有穷性、分步性、可机械执行性。而20世纪初期数学的发展要求对算法和可计算性给出一种严格的数学定义以证明某些函数的不可计算性。杨跃教授进而回顾了哥德尔为证明不完全性定理而引入的原始递归函数，并使用对角线方法论证解释了为何这一类函数不足以刻画所有直觉上可计算的函数。为了解决这一问题，哥德尔和厄布朗(Herbrand)引入了一般递归函数，这一函数类被证明与λ可定义函数、部分递归函数等价。基于这一事实，丘奇(Church)提出了著名的“丘奇论题”——所有直觉上可计算的函数恰好正是一般递归函数。而图灵机这一直观的计算模型的提出，最终使哥德尔相信了“丘奇论题”的正确性。

讲座的第二部分是介绍如何在比自然数更高阶的数学对象(如实数)上定义可计算函数，这也是杨跃教授本人近十年研究的一个问题。不同于经典递归论的情形，已有的几种定义，如TTE模型、BSS定义等所刻画的可计算函数类并不相同。而杨跃教授的想法是构造一种兼容TTE模型和BSS定义的函数类。他和其他合作者首先考虑在同构于实直线的Baire空间上定义可计算函数。他们采取了两种定义，分别是部分递归函数和图灵机的推广。前者是在部分递归函数中添加了TTE通用函数和判断一个自然数无穷序列是否处处为0的特征函数；后者是所谓的MS图灵机，有一个有穷状态的图灵机和若干通用神谕(universal oracle)图灵机组成。可以证明这两种定义刻画了同一个函数类。而对于更高阶的有穷类型(finite types)的对象,可以将这一想法进一步推广和抽象来定义其上的可计算函数。这也是杨跃教授最近正在研究的一个方向。

最后，杨跃教授从数学哲学和计算机科学的视角讨论了这一研究的意义。从数学哲学的视角，这一研究呼应了哥德尔1972年对有穷主义数学的讨论。正如哥德尔所指出的，有穷主义超出了希尔伯特纲领意义上数学对象的有穷性，其可以允许以构造性的方式引入更加抽象的数学对象。而从计算机科学的视角看，正如著名计算机科学家M.Vardi于2012年所指出的，如同光的波粒二象性，算法具有函数-机械二重性，这反映了计算机科学的一个基本原则。

在提问环节，我院申国桢老师和谢凯博老师分别就高阶对象上的可计算函数在形式系统的可表示性和加入0特征函数是否会引起函数类爆炸向杨教授进行了提问，杨跃教授回应道：如果能有自然的形式系统表示这一函数类，可以为其定义提供很好的哲学辩护；由于MS图灵机的其他限制,可以防止函数类爆炸的问题。程勇教授的问题则是：报告中的有限类型对象上的可计算理论与现有的其他不同研究路径间的关联，以及经典递归论的著名结果是否对MS图灵机可计算函数类也成立？杨跃教授指出，限制在自然数变量上的s-m-n定理和递归定理是成立的，他们目前正在考虑计算复杂性方面的结果是否成立。

讲座结束后，程勇教授对杨跃教授的精彩学术报告进行了评论和总结，他认为杨跃教授的讲座提纲挈领，深入浅出，拓宽了我院师生的学术视野和研究思路。

（编辑：邓莉萍 审稿：严璨）