论文部分内容阅读
算法信息论是一门新兴的理论计算机学科，它利用理论计算机的工具(图灵机)对复杂性的概念进行研究。Domination是算法信息论中的一个非常重要的概念，利用它可以给出图灵度新的刻画。
本文在domination的概念下研究图灵度的集合。首先介绍了递归论的基础知识：图灵度、Jump操作符以及domination的定义，重点研究了high、-L2、-GL2、α.n.r和hyperimmune等图灵度的集合。给出它们在domination下的新定义，并证明两种定义的等价性，然后很直观的得到它们的包含关系。最后利用domination定义新的图灵度ω-high，并证明它与≥T()’的等价性。