每一个非零的可计算可枚举强有界图灵度都具有反成杯性质(英文)

Every Nonzero c.e.Strongly Bounded Turing Degree has the Anti-cupping Property

可计算Lipschitz图灵归约(cl-归约)是指用函数被x→x+c约束的图灵归约,其中c是常数;而ibT归约则通过限制用函数为恒等函数得到。我们通称cl-,ibT-归约为强有界图灵归约。我们证明:对于r=cl,ibT,在可计算可枚举r-度构成的偏序结构(R_r,≤)中,每一个非零的a都具有反成杯性质。为此,我们证明一个新结论:对于每一个不可计算的可计算可枚举集合A,都存在一个不可计算的可计算可枚举B,使得对所有满足A≤_(wtt) C的可计算可枚举集合C都有B≤_(ibT) C。结合关于可计算偏移的已知性质,我们便可得到上述主要定理。

The strongly bounded Turing reducibilities r = el （computable Lipschitz reducibility） and r = ibT （identity bounded Turing reducibility） are defined in terms of Turing reductions where the use function is bounded by the identity function up to an additive constant and the identity function, respectively. We show that, for r = ibT, el, every computably enumerable （c.e.） r-degree a 〉 0 has the anti-cupping property in the partial ordering （Rr, 〈） of the c.e. r-degrees, The proof is based on （1） the （new） result, that, for any noncomputable c.e. set A there is a noncomputable c.e. set B such that B ≤ibT C for all c.e. sets C with A 〈wtt C and （2） some （old） observations on computable shifts.