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

批准号:
11201065
项目类别:
青年科学基金项目
资助金额:
22.0 万元
负责人:
范赟
依托单位:
学科分类:
A0101.数学史、数理逻辑与公理集合论
结题年份:
2015
批准年份:
2012
项目状态:
已结题
项目参与者:
查日军
国基评审专家1V1指导 中标率高出同行96.8%
结合最新热点,提供专业选题建议
深度指导申报书撰写,确保创新可行
指导项目中标800+,快速提高中标率
微信扫码咨询
中文摘要
Computable Lipschitz归约(简记为cl-归约)是强Turing归约,即给定变量,其用函数对应为增加某个常数[DHL01]。作为比较实数随机性的归约工具,cl-归约由新西兰的Downey,美国的Hirschfieldt,Lafort等专家提出,其对应的cl-度内实数具有相同的随机程度。所以,在cl-归约下,度的结构,尤其是c.e.实数对应的度的结构,及利用cl-归约下性质刻画随机实数对随机性理论具重要意义。国内外随机性理论研究方面诸多专家对以上的问题展开了丰富的研究,见文献[BL06]等。另一方面,c.e.集合在cl-归约(ibT归约-特殊的cl-归约)下对应的度的结构,其特殊性质,如非稠密等,促使可计算理论学者关注对cl-归约下c.e.集合度结构的研究。本课题拟从以上两方面来研究cl-归约的性质。
英文摘要
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).
本项目旨在研究在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-归约下不稠密等结论。
期刊论文列表
专著列表
科研奖励列表
会议论文列表
专利列表
The partial orderings of the computably enumerable ibT-degrees and cl-degrees are not elementarily equivalent
可计算可枚举 ibT 度和 cl 度的偏序本质上并不等价
DOI:10.1016/j.apal.2012.11.002
发表时间:2013-05
期刊:ANNALS OF PURE AND APPLIED LOGIC
影响因子:0.8
作者:Ambos-Spies, Klaus;Bodewig, Philipp;Fan, Yun;Kraeling, Thorsten
通讯作者:Kraeling, Thorsten
DOI:10.1007/s00224-012-9424-1
发表时间:2012
期刊:Theory of Computing Systems
影响因子:0.5
作者:K. Ambos-Spies;Decheng Ding;Yun Fan;W. Merkle
通讯作者:K. Ambos-Spies;Decheng Ding;Yun Fan;W. Merkle
Computable Lipschitz 归约下c.e.实数的性质
- 批准号:11126055
- 项目类别:数学天元基金项目
- 资助金额:3.0万元
- 批准年份:2011
- 负责人:范赟
- 依托单位:
国内基金
海外基金
