可计算性理论及其应用

我们继续研究可计算性的纯粹理论及其应用方面。对于可计算性理论方面我们致力于研究不可解度的可定义性，例如REA性质，Martin猜想，集合论公理系统对于不可解度的结构影响等；应用方面我们关注于可计算性理论在算法信息论和分析方面的应用，着重于刻画随机性以及低性性质，研究算法信息论中引入的新的归约度的结构，高等随机性理论以及概率测度和随机变量的可计算性理论等等。

我们研究了高等随机性以及图灵度的结构问题。分离了low for $\Pi^1_1$-randomness 和low for $\Delta^1_1$-randomness，回答了Nies,Simpson以及Friedman打几个古老的公开问题。还研究了shif度，证明了$0'$的自然可定义性。研究了hif集合的图灵跃迁，回答了Downey, Cai以及Shore等人打一系列公开问题。提出了用Martin-Lof随机性研究随机性概念的方法并且给出了一些应用。