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

摘要：

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

关键词：性质、有界、ibT、归约、函数、证明、集合、偏序

所属期刊栏目：5

分类号：O174(数学分析)

资助基金：This research was partially supported by the Sino-German binational grant Computability and Complexity in Analysis: Towards a Sound Foundation for Scientific Computations NSFC 10911130011 and DFG 446 CHV 113/266/0-1. Wei Wang was also partially supported by NSFC 11001281

在线出版日期：2013-01-27（万方平台首次上网日期，不代表论文的发表时间）

页数：共10页

页码：1-10