基于Ershov分层的图灵度结构研究

This project will study the Turing degree structure in which relative computability is a core topic. Wherein, Turing reduction is a basic concept and Turing degree induced by which is a spectra of computabilities of all mathamatical objects. So far, the Turing degree structure is not completely unveiled after several decades' study. Bases upon our last investigations on Ershov hierarchies, the key point of this project is in 2-c.e. Turing degrees, we use the priority tree method introduced by Lachlan to study the structural properties of Turing degrees below 0', which consists of three aspects: (1) the study of some algebraic properties of Turing degrees in Ershov hierarchy, (2) the study of infima of some Turing degrees in different hierarchies, and (3) the study of the distribution of Lachlan sets, i.e., study the Turing degree structure below the complete Turing degree by using the distribution of Lachlan sets. The project will hopefully enrich the study on the algebraic aspect of Turing degree structure and add the information about the structural properties of Turing degrees.

本项目拟研究可计算性理论中的图灵度结构性质。相对可计算性是可计算性理论的一个核心研究课题，图灵归约是其中一个基本而又重要的概念，由此得到的图灵度是对数学结构计算能力的一个基本谱分。虽然这方面的研究已经有了几十年的历史，但是对图灵度结构的认识仍然不足。基于我们前期对Ershov分层结构的研究，本项目以二阶递归可枚举图灵度作为突破口，使用Lachlan的树构造方法，结合Ershov分层研究0 '以下的图灵度局部结构性质，研究内容主要包括：（1）研究Ershov分层中的图灵度的一些代数性质，（2）研究Ershov分层中的某些图灵度在不同分层中的下确界，（3）研究Lachlan集合的分布情况，即利用Lachlan 集合去研究完备的图灵度下的一些结构。本项目可丰富对图灵度代数结构的研究，增加对图灵度结构性质的认识。

可计算性理论是计算科学的理论基础。而在研究可计算性理论的过程中，图灵归约是一个非常重要的概念，由图灵归约得出的图灵度是对数学结构计算能力的一个基本谱分。虽然这方面的研究已经有了几十年的历史，但是对图灵度结构的认识仍然不足。本项目以二阶可计算枚举图灵度作为突破口，使用Lachlan的树构造方法，结合Ershov分层研究0 '以下的图灵度局部结构性质，主要研究了以下几个重要内容并得出相关结果：.（1）我们得到了一个关于几乎泛可杯的二阶可计算枚举度的结论：给定一个非0的可盖的可计算枚举度c，我们利用0'''-优先树方法构造了一个几乎泛可杯的二阶可计算枚举度d和一个可图灵归约到d的可计算枚举度b，使得c与d的上确界为0'，c与b的下确界为0，任意图灵归约到d的可计算枚举度都图灵归约到b。.（2）我们采用了0'''-优先树方法构造出三个二阶可计算枚举集B，A1和A2，一个3阶可计算枚举集C，使得它们满足四种类型的要求。从而得到相应的三个二阶可计算枚举度度b，a1和a2，一个3阶可计算枚举集c，使得a1和a2在二阶可计算枚举度结构中有下确界b，在3阶可计算枚举度结构中有下确界c，且b<c。.（3）我们证明了对任意真二阶可计算枚举度d，L[d]中任意两个元素都不可能构成极小对。结合Ishmukhametov存在一个真二阶可计算枚举度d使得L[d]中没有极小度的结论，我们可以得出结论：存在一个真二阶可计算枚举度d使得L[d]中没有最小度。.本项目所研究的内容具有以下意义：.（1）本项目得出的结论可以推出很多优秀递归论专家得出的一些在可计算性理论里很有意义的结论， 比如 Arslanov 的 cupping 定理，Downey的 Diamond 定理Angsheng Li 和 Xiaoding Yi 的 cupping 定理； Downey，Angsheng Li 和 Guohua Wu 的互补定理。.（2）从对 Lachlan 集合的分布认识，达到对二阶可计算枚举度的新的认识。