• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Computability: the journal of the Association Ci >Asymptotic density,immunity and randomness
【24h】

Asymptotic density,immunity and randomness

机译：渐近密度，免疫力和随机性

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

摘要

In 2012, inspired by developments in group theory and complexity, Jockusch and Schupp introduced generic com- putability,capturing the idea that an algorithm might work correctly except for a vanishing fraction of cases. However, we observe that their definition of a negligible set is not computably invariant (and thus not well-defined on the 1 -degrees), resulting in some failures of intuition and a break with standard expectations in computability theory. To strengthen their approach, we introduce a new notion of intrinsic asymptotic density, with rich relations to both randomness and classical computability theory. We then apply these ideas to propose alternative foundations for further development in (intrinsic) generic computability. Toward these goals, we classify intrinsic density 0 as a new immunity property, specifying its position in the standard hierarchy from immune to cohesive for both general and ?_2~0 sets, and identify intrinsic density 1/2 as the stochasticity corresponding to permutation randomness. We also prove that Rice's Theorem extends to all intrinsic variations of generic computability, demonstrating in particular that no such notion considers 0' to be "computable".
机译：在2012年，受群体理论和复杂性发展的启发，Jockusch和Schupp引入了通用的可计算性，捕捉了一种算法，即在情况不复存在的情况下也可以正常工作的想法。但是，我们观察到它们对可忽略集合的定义不是可计算不变的（因此在1度上定义不明确），导致一些直觉失败和可计算性理论中的标准期望被破坏。为了加强他们的方法，我们引入了内在渐近密度的新概念，它与随机性和经典可计算性理论都有着密切的关系。然后，我们将这些思想应用于为（本征）通用可计算性进行进一步开发的替代基础。为了实现这些目标，我们将固有密度0归类为新的免疫属性，并指定其在标准组中从免疫到内聚的一般位置和？_2〜0集的位置，并将固有密度1/2确定为与置换随机性相对应的随机性。我们还证明了赖斯定理扩展到了通用可计算性的所有内在变化，尤其表明没有一个这样的概念认为0'是“可计算的”。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号