Study on convergence rate of weakly computable reals

弱可计算实数收敛速度研究

• 批准号: 22K03408
• 负责人: 宮部 賢志
• 金额: $ 2.33万
• 依托单位: Meiji University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2022
• 资助国家: 日本
• 起止时间: 2022-04-01 至 2027-03-31
• 项目状态: 未结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-22K03408/
• 关键词: 弱計算可能実数; Solovay還元; リプシッツ連続; 符号付き桁数表示; 計算可能解析; ランダムネス

本年度の研究では弱計算可能実数に対するSolovay還元の新しい特徴付けを得た．計算論において，実数の複雑さを何らかの還元により比較し，その構造を調べる研究がよく行われている．ランダムネスの理論で現れる弱計算可能実数の族は計算可能実数の族よりも広い実数の族で，Solovay還元は近似しやすさによる弱計算可能実数の半順序である．最近になって，左c.e.実数に対するSolovay還元とリプシッツ連続な計算可能性関数の関係が明らかになった．左c.e.実数の集合は弱計算可能実数の集合よりも小さい．そこで解析的なアプローチによる弱計算可能実数の近似可能性について理解を深めることを目的に研究を進めた．その結果，計算可能解析学でよく用いられる符号付き桁数表示でのuse関数の制限によりSolovay還元が特徴付けられるという結果を得た．use関数はTuring還元において神託にアクセスする場所の上限を表現する関数である．2進展開表示でのuse関数の制限による還元は計算可能リプシッツ還元(cL-reducibility)として知られており，Solovay還元と比較不可能であることも知られている．本研究での結果はこの事実のより自然な形での改良と見なすことができる．また，弱計算可能実数に対するSolovay還元のリプシッツ連続関数を用いた特徴付けも得た．その特徴付けは複雑だが，いくつかのより単純な変種とは異なることも示した．これらの結果に基づいて，多くの弱計算可能実数の族が実閉体となることを示した．

在今年的研究中，我们获得了弱可计算实数的 Solovay 约简的新表征。在计算理论中，经常进行研究通过某种简化来比较实数的复杂性并研究它们的结构。随机性理论中出现的弱可计算实数族是比可计算实数族更广泛的实数族，而索洛维约简由于易于近似而成为弱可计算实数族的偏序。最近，左 c.e. 实数的 Solovay 约简与 Lipschitz 连续可计算函数之间的关系已得到澄清。左 c.e. 实数集小于弱可计算实数集。因此，我们进行研究的目的是使用分析方法加深对弱可计算实数的逼近性的理解。由此，我们得到了Solovay约简的特点是符号数字表示中使用函数的限制，这在可计算分析中经常使用。 use函数是表达图灵约简中可以访问预言机的上限的函数。通过限制二元展开表示中的使用函数进行的约简被称为 cL-约简，并且也被认为是与 Solovay 约简无法相比的。这项研究的结果可以看作是对这一事实的更自然的改进。我们还使用 Lipschitz 连续函数获得了弱可计算实数的 Solovay 约简的表征。它的表征很复杂，但我们也表明它与一些更简单的变体不同。基于这些结果，我们表明许多弱可计算实数族是实闭域。

项目成果

Kenshi Miyabe

宫部贤士

Rational sequences converging to left-c.e. reals of positive effective Hausdorff dimension

有理数序列收敛于左 c.e.

• DOI: 10.1142/9789811259296_0005
• 发表时间: 2022
• 作者: Hiroyuki Imai; Masahiro Kumabe; Kenshi Miyabe; Yuki Mizusawa;Toshio Suzuki
• 通讯作者: Toshio Suzuki

Generality of computable measures

可计算测度的一般性

• 发表时间: 2022
• 作者: Kenshi Miyabe

実閉体を成す弱計算可能実数の部分族

形成实闭域的弱可计算实数子族

• 发表时间: 2022
• 作者: 宮部賢志

Subclasses of weakly computable reals

弱可计算实数的子类

• 发表时间: 2022
• 作者: Kenshi Miyabe