本網訊（通訊員楊新宇）10月25日下午，新加坡國立大學數學系楊躍教授在振華樓beat365体育官网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定理和遞歸定理是成立的，他們目前正在考慮計算複雜性方面的結果是否成立。

講座結束後，程勇教授對楊躍教授的精彩學術報告進行了評論和總結，他認為楊躍教授的講座提綱挈領，深入淺出，拓寬了我院師生的學術視野和研究思路。

（編輯：鄧莉萍 審稿：嚴璨）