本网讯（通讯员申国桢）2021年10月19日15:00，南京大学数学系喻良教授在振华楼B214报告厅为公司师生带来了一场题为“随机性与不可解性”的精彩报告。报告由yl23455永利官网逻辑学教研室申国桢副研究员主持。武汉理工大学理学院数学系彭宁宁副教授、新加坡国立大学数学系博士后研究员肖鸣、以及yl23455永利官网、数学与统计学院的10余位同学参加了此次讲座。

喻良教授从“问题”这一概念的数学化开始，“问题”被定义为一集自然数，并通过一些例子展示了这种定义的合理性。接下来，喻老师讨论了图灵机和可判定性，并列举了一些不可判定问题，如停机问题、一阶数论、希尔伯特第十问题等，然后引入了图灵归约和图灵度的概念，并借此引出讲座的核心问题：“归约到停机问题”是否是证明一个问题不可判定的唯一方法？喻老师详细地介绍了历史上对这个问题的两个看似相反的回答：首先是Sacks等人证明的定理“几乎所有的问题都不比停机问题更困难”，然后是Posner-Robinson定理“每个不可解问题都可以在某种意义上归约到停机问题”。接下来，喻老师介绍了与此相关的著名的马丁猜想，并证明了马丁猜想在集合论公理系统ZFC中不成立。

讲座的第二部分，喻老师详细讲解了随机性。他首先介绍了历史上对于随机性的三种不同的定义，这三种定义被Schnorr证明是等价的，它们分别从不同的视角（不可压缩性、无区别性、不可预知性）来刻画随机性。然后介绍了Chaitin对于随机实数的典范构造，Miller和他对于1-随机性的等价刻画，以及van Lambalgen对于随机对的等价刻画。接下来，喻老师深入讨论了随机性的比较问题，引入了四种随机实数之间的大小关系，并介绍了Miller和他对于这些关系的研究，从而揭示了“越随机计算能力就越弱”这一深刻现象。讲座的最后，喻老师介绍了高阶随机性理论，重点介绍了集合论公理系统ZF+DC+AD中的马丁猜想，以及他最近在这方面的研究工作。

讲座结束后，彭宁宁副教授和肖鸣博士对讲座中涉及的喻老师和Miller的技术性结果进行了交流和讨论，在场的几位同学就自己感兴趣的问题向喻老师请教。整个讲座学术氛围浓厚，同学们均表示此次报告内容充实、思路清晰、收获颇丰。

（图片：邓莉萍   编辑：邓莉萍   审稿：严璨、吴昕炜）