Computable Lipschitz 归约下c.e.实数的性质

Computable Lipschitz归约(简记为cl-归约) [DHL01]作为比较实数随机性的归约工具由新西兰的Downey，美国的Hirschfieldt,Lafort等专家提出。Cl-归约是一种极强的Turing归约，即给定变量,其用函数对应为增加某个常数。作为新工具，cl-归约的引入引起了国内外随机性理论研究方面诸多专家的注意。特别的，cl-归约下computable enumberable(c.e.)实数又表现与以往经典Turing-归约等不同的度结构。这些结论也引起可计算理论专家对cl-归约下度结构的关注。本课题旨在研究对cl-归约下c.e.实数(包括c.e.集合)的性质。此工作在可计算性理论和随机性理论两方面都具有价值。

本项目旨在研究在computable Lipschitz 归约下c.e.实数的性质。(我们简称computable Lipschitz归约下所对应的度为cl-度)。作为特殊的c.e.实数类，c.e.集合对应的cl-度结构是我们本项目中研究重点。首先，对于cl-归约下特殊结构-最大对，我们分析了其与array不可计算的c.e.度的关系，以及最大对和Turing完备，Wtt-完备之间关系，并且得到相应的一些有意义的结论；另外，通过对cl-度的cup性质的分析，得到了cl-度与特殊的cl-度(ibT-度）之间的区分，此前这样的区分尚未找到。本项目的研究补充了c.e.集合对应的cl-度理论，体现了cl-归约在可计算理论中的应用。