本網訊（通訊員申國桢）2021年10月19日15:00，南京大學數學系喻良教授在振華樓B214報告廳為我院師生帶來了一場題為“随機性與不可解性”的精彩報告。報告由beat365体育官网邏輯學教研室申國桢副研究員主持。武漢理工大學理學院數學系彭甯甯副教授、新加坡國立大學數學系博士後研究員肖鳴、以及beat365体育官网、數學與統計學院的10餘位同學參加了此次講座。

喻良教授從“問題”這一概念的數學化開始，“問題”被定義為一集自然數，并通過一些例子展示了這種定義的合理性。接下來，喻老師讨論了圖靈機和可判定性，并列舉了一些不可判定問題，如停機問題、一階數論、希爾伯特第十問題等，然後引入了圖靈歸約和圖靈度的概念，并借此引出講座的核心問題：“歸約到停機問題”是否是證明一個問題不可判定的唯一方法？喻老師詳細地介紹了曆史上對這個問題的兩個看似相反的回答：首先是Sacks等人證明的定理“幾乎所有的問題都不比停機問題更困難”，然後是Posner-Robinson定理“每個不可解問題都可以在某種意義上歸約到停機問題”。接下來，喻老師介紹了與此相關的著名的馬丁猜想，并證明了馬丁猜想在集合論公理系統ZFC中不成立。

講座的第二部分，喻老師詳細講解了随機性。他首先介紹了曆史上對于随機性的三種不同的定義，這三種定義被Schnorr證明是等價的，它們分别從不同的視角（不可壓縮性、無區别性、不可預知性）來刻畫随機性。然後介紹了Chaitin對于随機實數的典範構造，Miller和他對于1-随機性的等價刻畫，以及van Lambalgen對于随機對的等價刻畫。接下來，喻老師深入讨論了随機性的比較問題，引入了四種随機實數之間的大小關系，并介紹了Miller和他對于這些關系的研究，從而揭示了“越随機計算能力就越弱”這一深刻現象。講座的最後，喻老師介紹了高階随機性理論，重點介紹了集合論公理系統ZF+DC+AD中的馬丁猜想，以及他最近在這方面的研究工作。

講座結束後，彭甯甯副教授和肖鳴博士對講座中涉及的喻老師和Miller的技術性結果進行了交流和讨論，在場的幾位同學就自己感興趣的問題向喻老師請教。整個講座學術氛圍濃厚，同學們均表示此次報告内容充實、思路清晰、收獲頗豐。

（圖片：鄧莉萍   編輯：鄧莉萍   審稿：嚴璨、吳昕炜）