...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Journal of complexity >Randomness and universal machines
【24h】

Randomness and universal machines

机译：随机和通用机器

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

摘要

The present work investigates several questions from a recent survey of Miller and Nies related to Chaitin's Ω numbers and their dependence on the underlying universal machine. Furthermore, the notion Ω_U [X] = Σ_(p:U(p)↓∈X)2~(-|p|) is studied for various sets X and universal machines U. A universal machine U is constructed such that for all x,Ω_U [{x}] = 2~(1-H(x)). For such a universal machine there exists a co-r.e. set X such that Ω_U [X] is neither left-r.e. nor Martin-Loef random. Furthermore, one of the open problems of Miller and Nies is answered completely by showing that there is a sequence U_n of universal machines such that the truth-table degrees of the Ω_(U_n) form an antichain. Finally, it is shown that the members of hyperimmune-free Turing degree of a given Π_1~0-class are not low for Ω unless this class contains a recursive set.
机译：本研究调查了最近对Miller和Nies进行的调查中与查伊廷Ω数及其对基础通用机器的依赖性有关的几个问题。此外，概念Ω_U[X] =Σ_（p：U（p）↓∈X）2〜（-| p |）研究各种集合X和通用机器U。 x，Ω_U[{x}] = 2〜（1-H（x））。对于这样的通用机器，存在协同作用。设置X，使得Ω_U[X]都不为左。也不是Martin-Loef随机的。此外，通过显示存在通用机器序列U_n使得Ω_（U_n）的真值表度形成反链，可以完全解决Miller和Nies的一个开放问题。最后，表明给定的Π_1〜0类的无超免疫图灵度的成员对于Ω不低，除非该类包含递归集。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号