首页 | 本学科首页   官方微博 | 高级检索  
     

每一个非零的可计算可枚举强有界图灵度都具有反成杯性质
引用本文:克劳斯·安博司比斯,王玮. 每一个非零的可计算可枚举强有界图灵度都具有反成杯性质[J]. 逻辑学研究, 2012, 0(3): 1-10
作者姓名:克劳斯·安博司比斯  王玮
作者单位:德国海德堡大学数学与计算机科学系;中山大学逻辑与认知研究所、哲学系
基金项目: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);partially supported by NSFC 11001281
摘    要:可计算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  归约  函数  证明  集合  偏序

Every Nonzero c.e.Strongly Bounded Turing Degree has the Anti-cupping Property
Klaus Ambos-Spies. Every Nonzero c.e.Strongly Bounded Turing Degree has the Anti-cupping Property[J]. Studies in Logic, 2012, 0(3): 1-10
Authors:Klaus Ambos-Spies
Affiliation:Institute of Logic and Cognition,Department of Philosophy,Sun Yat-sen University
Abstract: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.
Keywords:
本文献已被 CNKI 维普 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号