计算、枚举和能行逼近研究

We investigated the structure of the computably enumerable Turing degrees, discoverd some new hierarchies of the structure (Li, Wu and Zhang, Illinois Journal of Mathematics, 2002, Wang and Li, to appear). In the study of the splitting and nonsplitting phenomina, we proved a generalised low splitting theorem, extending the Robinson low splitting theorem (Arslanov, Cooper and Li, 2000, Mathematical Logic Quarterly), and a nonsplitting theorem (Cooper, Li, JSL, to appear), and we proved a splitting theorem of the difference hierarchy (Cooper and Li, Journal of the London Math Soc, 2002). .A major piece of work during the project is the affirmative solution to the Major Subdegree Problem posed by Lachlan in 1967 (Cooper and Li, to appear). We sovled the density problem of the N-C.E. enumeration degrees (Cooper, Li, Sorbi and Yang, Israel Journal of Mathematics, to appear). In the topic of definable ideals of the computably enumerable degrees, we proved a remarkable join theorem (Jockusch, Li and Yang, to appear). The main publications during the project by the end of 2002, include 6 papers in international journals, and 2 papers in Chinese journals.

图灵归约提供了精美的模型以分析不可计算对象的结构。在这些对象中，最重要的类型是可计算枚举、n-可计算枚举集和能行逼近函数，我们研究这些对象的图灵结构，重点研究可计算枚举度中的分解与非分解现象，n-可计算枚举度中的非稠密、局部稠密和局部分解现象及基本理论的不可判定性。这是可计算性理论前沿课题的研究，是计算机科学的基础理论。.