可计算性理论及其在算法信息论中的应用

我们研究可计算性理论（又称递归论）及其在算法信息论中的应用。尤其是关于随机性的刻画问题。这是可计算性理论（甚至整个数学）的一个热门领域。2006年国际数学家大会有多人因研究随机性获奖。最近著名可计算理论学家Downey因此获得国际数学家大会45分钟报告的邀请（这在数理逻辑中几乎是最高荣誉）。.我们主要从可计算性理论观点出发，刻画随机性。研究随机性与可计算性的关系并且运用可计算性理论的方法研究随机数的Kolmogorov复杂性。我们将着重于研究lowness性质以及分离2-randomness,strongly Chaitin randomness 和 3-randomness. .我们还着重于图灵度的整体结构的研究。这是可计算性理论的一个古老课题。现在遗留的公开问题都是极为困难的。近来我们发现算法信息论中的一些方法可以成功地运用到这一领域。