Computable Lipschitz 归约在随机性及可计算性理论中的应用

Computable Lipschitz(cl-) reducibility is a strengthening of weak truthtable reducibility, namely computations where the use on the oracle on argument n is n + c for some constant c, was suggested as a possible measure of relative.randomness by Downey，Hirschfieldt,Lafort[DHL01].. Having defined cl-reducibility we can consider the structure of the induced degrees.The cl-degrees are the equivalence classes under cl-reducibility..Notice that they either contain only random reals or only non-random reals. Since cl-reducibility is a strengthening of weak truth table reducibility, the structure of cl-degrees is interesting from the computation complexity. So the structure of cl-degrees of c.e. reals is interesting from randomness theory. Some concerned results are given in [BL06]，[BL07]etc.. Although cl-reducibility is a strengthening of weak truth table reducibility, the structure of cl-degrees of c.e. sets is different from the wtt-degrees and Turing degrees. For instance, the cl-degrees( or ibT-degrees) of c.e. sets are not dense. So the structure of cl-degrees is interesting from computation theory. .In our project, we will analyze the properties of the cl-reducibilty, to explore the structure of cl-degrees of c.e. reals (or sets).

Computable Lipschitz归约(简记为cl-归约)是强Turing归约，即给定变量,其用函数对应为增加某个常数[DHL01]。作为比较实数随机性的归约工具，cl-归约由新西兰的Downey，美国的Hirschfieldt,Lafort等专家提出，其对应的cl-度内实数具有相同的随机程度。所以，在cl-归约下，度的结构，尤其是c.e.实数对应的度的结构,及利用cl-归约下性质刻画随机实数对随机性理论具重要意义。国内外随机性理论研究方面诸多专家对以上的问题展开了丰富的研究，见文献[BL06]等。另一方面，c.e.集合在cl-归约（ibT归约-特殊的cl-归约）下对应的度的结构，其特殊性质，如非稠密等，促使可计算理论学者关注对cl-归约下c.e.集合度结构的研究。本课题拟从以上两方面来研究cl-归约的性质。

本项目旨在研究在cl-归约下可计算可枚举（c.e.）集合度的结构和分析可计算可枚举（c.e.）实数在cl-归约下的性质来描述实数的随机性。目前完成的主要结果如下：. 1. c.e.集合（实数）最大对是指在cl-归约下其无共同上界。通过与专家Ambos-spies,丁德成， Wolfgang 等的合作，我们建立c.e.集合最大对与行列可计算(array computable)类, 弱真值归约(wtt-)完备集, 图灵归约（T-)完备集等重要类的联系，并且进一步分析性质，如存在一个最大对，同时为最小对的c.e. 的cl-度，或存在一对非最大对且不具备最小的上界的c.e.的cl-度等等。. 2. ibT-归约是特殊的cl-归约，其用函数为恒等函数。通过与Ambos-spies, Bodewig 及Kräling 合作，我们得到c.e.集合的ibT-度和cl-度具有某个不同的度结构，从而从结构上区分ibT 和cl 两种归约。. 3. 我们引入一致非low_2类，通过cl-归约下c.e.实数的性质进一步理解此集合类: 如果某c.e. 图灵度是一致非low_2， 则对于任何不可计算的c.e.实数，此度中存在某c.e.实数使得两者构成一个c.e.实数的最大对。 以上证明的方法具有创新性，可用于证明Barmpalias, Downey 及Greenberg (2008)中对行列可计算类刻画的结论。 作为应用，我们证明了下列三个命题等价：(1)某c.e. 图灵度是行列不可计算；2）该度中存在一个c.e.实数，其不归约与任何wtt-完备的c.e.实数；（3）该度中存在一个c.e.实数，其不归约与任何复杂(complex)的c.e.实数。进一步，对于non-low_2类可通过cl-归约下c.e.实数类的性质刻画。. 4. Barmpalias，Day等证明了c.e.集合在ibT(cl)-归约下非稠密。在分析其证明方法之下，我们推广得到n-c.e集合在cl-归约下非稠密，c.e. 实数在ibT-归约下不稠密等结论。