这次报告主要介绍了经典递归论里面的关于集合的复杂性的问题。首先从基本的概念开始展开，引入相对可计算性的概念。分别介绍了many-one可归约性、图灵可归约性、弱真值表可归约性和真值表可归约性，简单的讨论了这些可归约性的基本性质和它们相互之间的关系。并且在图灵可归约性的基础上引入绝对计算复杂性的概念，分别简要讨论了两个lowness和highness性质，说明不同集合作为oracle时计算能力的差别，并揭示了这两个性质之间的线性包含关系。之后又从另外一个角度讨论集合的复杂性，也就是集合的描述复杂性，以此划分了集合之间的算术层级结构。同时介绍了Limit Lemma，并将这种算术层级结构与计算复杂性联系起来，也由此引申出另外一个层级结构——差别层级结构。在介绍讨论了这一系列的复杂性关系和性质之后，最后简要的介绍了Post’s 问题。讨论了Post’s 问题的背景、解决经过和遗留问题，也就是人们所期待的关于Post’s问题的一个对数学家来说比较自然的解决方案。总体而言，此次报告的内容属于数理逻辑中比较艰深的理论，许多细节内容还需要大家通过后续的学习来补充。报告后，老师同学们主要就oracle这个概念进行了讨论，以及出于对Post’s问题的自然解的尚未找到而产生的对图灵可归约性这一个概念的合理性的质疑。