• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Journal of Symbolic Logic >RANDOMNESS VIA INFINITE COMPUTATION AND EFFECTIVE DESCRIPTIVE SET THEORY
【24h】

RANDOMNESS VIA INFINITE COMPUTATION AND EFFECTIVE DESCRIPTIVE SET THEORY

机译：无限计算随机性和有效的描述性集合理论

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

We study randomness beyond ${m{Pi }}_1^1$-randomness and its Martin-L?f type variant, which was introduced in [16] and further studied in [3]. Here we focus on a class strictly between ${m{Pi }}_1^1$ and ${m{Sigma }}_2^1$ that is given by the infinite time Turing machines (ITTMs) introduced by Hamkins and Kidder. The main results show that the randomness notions associated with this class have several desirable properties, which resemble those of classical random notions such as Martin-L?f randomness and randomness notions defined via effective descriptive set theory such as ${m{Pi }}_1^1$-randomness. For instance, mutual randoms do not share information and a version of van Lambalgen’s theorem holds.Towards these results, we prove the following analogue to a theorem of Sacks. If a real is infinite time Turing computable relative to all reals in some given set of reals with positive Lebesgue measure, then it is already infinite time Turing computable. As a technical tool towards this result, we prove facts of independent interest about random forcing over increasing unions of admissible sets, which allow efficient proofs of some classical results about hyperarithmetic sets.
机译：我们学习超过$ { rm { pi}} _1 ^ 1 $ -randomness及其Martin-l？f型变体的随机性，在[16]中介绍，并进一步研究[3]。在这里，我们严格关注{ rm { pi}} _1 ^ 1 $和$ { rm { sigma}} _ 2 ^ 1 $之间的阶段，由Hamkins引入的无限时间图测机器（ITTMS）给出和骗子。主要结果表明，与此类相关的随机性概念具有若干理想的属性，其类似于经典随机概念，例如通过有效描述集理论定义的Martin-L？F随机性和随机性概念，例如$ { rm { pi }} _ 1 ^ 1 $ -Randomness。例如，相互随机不会分享信息和van Lambalgen的定理版本的信息。我们证明了以下模拟到一个麻袋的定理。如果真实是无限时间，则相对于一些特定的真实的所有真实仪表，那么它已经是无限的时间计算可计算。作为这种结果的技术工具，我们证明了对随机强制上涨的独立兴趣的事实，增加了允许的集合的增加，这允许有效的一些经典结果关于超级算法集。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号