当代中国逻辑学研究
三 可计算分析
|
来 源
：
|
当代中国逻辑学研究2009 \ - |
作 者
：
|
- |
浏览次数
：
|
9 | ||
|
摘 要
：
|
与递归可枚举度相关的研究在递归可枚举度的研究中, Sacks稠密性定理可以说是一个里程碑。张再跃扩展了Cooper关于极小对的一个定理，证明了：如果h是一个高的递归可枚举度，而b是一个不在h之上的递归可枚举度，则h之下存在两个不能被b计算的递归可枚举度构成极小对sup[391]。N-递归可枚举图灵度我们知道递归可枚举集合的一个等价定义是:X递归可枚举,当且仅当存在一个二元递归函数f满足以下条件：任意x, s， f（x， s）=0或1，且f（x， =0.具有n-递归可枚举代表元的图灵度就称为n-递归可枚举度，因此递归可枚举度就是1-递归可枚举度。 | ||||||
|
关键词
：
|
枚举 定理 实数 随机性 算法 图灵机 多项式 钻石 逻辑学 复杂性理论 数理逻辑 |
||||||
在线阅读
三 可计算分析
字体：大中小
可计算分析研究连续对象（实数、实函数、实数集以及更一般拓扑空间上的对象）的可计算性。A.Turing早在20世纪30年代，在他著名文章中就给出了可计算实数的定义。他注意到二进制和十进制表示不足以恰当的定义实数的可计算性。之后，人们尝试用不同的计算模型来研究分析中的能行性。而德国学者Weihrauch教授的二型能行理论（TTE）几乎可以包容所有的能行理论。
贵州大学李祥用程序来表示实数sup[285]。设a为一可计算实数，则所有计算a的程序的集合就表示了该实数。李祥研究了与这种表示相关的不可解问题。李祥还引进递归表示能行拓扑空间（recursively presented effective topological space），并研究这种空间中的“处处逐点”（everywhere pointwise）性质sup[284]。1983年，P.Hingston引进了能行Hausdorff空间的概念。李祥使用编码、对角化与优先方法来研究能行Hausdorff空间中开集的能行性质，主要结果是证明了在每个递归可枚举的图灵度中都有非r.e.开集但按点r.e.开集存在sup[49][50]。
黄文奇和Nerode合作利用两种编码系统把定义在[0，1]区间上的函数的不可计算度结构问题转换为纯递归论问题。从而利用可计算性理论中的工具获得了可构造分析中的若干结果sup[180]。
堵丁柱和葛可一合作研究[0，1]区间上的凸函数的积分和微分的计算复杂性，证明了如下结果（在P不等于NP的假设下）：（1）存在多项式时间可计算凸函数，它的积分不是多项式间可计算的；（2）存在多项式时间可计算凸函数，它在1/2处可微分，但此处的微分不是多项式时间可计算的sup[223]。
南京大学丁德成和吴永成研究了测度空间上的可计算性。首先他们引进了可计算测度空间，它是在测度空间上加上必要的可计算条件使得测度函数和集合的并与差在相应的表示下是可计算的。接着，他们研究如何表示可测集和可测函数以及基于这些表示的可计算性。他们证明了，可测集之间的某些关系（如：几乎处处相等、几乎处处包含、可测集的交集的可测性）是不可判定的sup[358]。他们发现，在无穷测度空间中，测度的可计算性与集合运算的可计算性总是矛盾的。也就是说，如果测度是全可计算的，那么集合的交与差运算都不完全可计算sup[359]。紧接着，丁德成和吴永成研究了可测数值函数的基本运算的可计算性。他们证明了，加法和除法总是可计算的，而乘法仅在个别特殊情况下是不可计算的sup[208][356]。经典的Daniell-Stone定理表明从一个抽象的Daniell积分可以得到一个测度使得在该测度下的积分正好等同于Daniell积分。吴永成和Weihrauch利用可计算性测度空间和可计算Stone向量格刻画了Daniell-Stone定理的可计算形式sup[360]。
中山大学赵希顺和Norbert Mueller合作，提出了用带Oracle的Turing机来表示实数空间紧集上的可计算算子，分析了一些重要算子的复杂性。证明了凸包算子、投影算子的复杂性与“P是否等于NP”问题之间的联系sup[362]。赵希顺和Mueller还研究Jordan域的Grid表示与边界表示之间的联系，证明了Grid表示的边界长度（如果有穷）是弱可计算的sup[318]。
南京大学陆宏和Weihrauch合作在二型能行理论的框架（TTE）内证明了C[0，1]的对偶空间上的Riesz表示定理的可计算形式sup[305]。紧接着，他们证明了局部紧Hausdorff空间上的Riesz表示定理的可计算形式sup[297]。
实数的许多表示诱导出的可计算性是等价的。然而，苏开乐、陈清亮等证明了这些等价的表示所诱导的原始递归性却未必等价sup[190]。
王国俊在紧Hausdorff测度空间上引进了黎曼型积分，证明了一个函数是黎曼可积的当且仅当它是几乎处处连续的。王国俊还引进了可计算性的概念，证明了在紧Hausdorff测度空间上，黎曼积分是可计算的当且仅当它可度量化sup[343]。
显示更多