该文是《理论计算机科学电子札记》66卷第1期的一篇文章,探讨了实数的内在计算复杂性和内在随机性的关联。作者包括Rod G. Downey、Denis R. Hirschfeldt、Frank Nies和Frank Stephan。文章中提到了Solovay关于存在不可计算实数的证明,这些实数具有H-平凡性质,即其无前缀的柯尔莫哥洛夫复杂度H与信息熵的关系。作者提供了构建H-平凡实数的新方法,并分析了这类实数的可计算性理论特性,如它们无法解决停机问题。此外,文章还研究了H-平凡实数与其他类别的关系。 文章介绍了通过比较实数的相对初始段复杂度来评估它们的内在随机性,提出了基于复杂度的约简概念。这里的复杂度用K(经典柯尔莫哥洛夫复杂度)或H(无前缀的柯尔莫哥洛夫复杂度)来衡量。Chaitin的Omega数被用作随机实数的一个例子。文章中的核心问题是,如果一个实数α在某种复杂度度量下相对于另一个实数β是简单的,那么它们的随机性有何关系? 文章指出,所有实数都满足α≤Hα的性质,这是一个基本的不等式。接着,作者提出了一个自然的问题:当α≤Qβ时(Q代表H或K),对于不同类型的复杂度关系,实数的随机性如何变化?这涉及到对可约性的深入分析,以及如何通过这种分析来划分具有相似随机性的实数等价类。 在研究过程中,作者不仅建立了新的H-平凡实数构造,还讨论了它们的特殊性质,比如它们不能计算停机问题,这表明H-平凡实数集合是一种特殊的可计算可解集,且是无损伤的不完全c.e.集合。同时,文章还对比了H-平凡实数与其他类别的实数,如随机实数、可计算实数等,以揭示不同复杂性类别下的随机性行为。 这篇文章深入探讨了理论计算机科学中的一个重要主题,即计算复杂性与随机性的相互作用,特别是通过H-平凡实数这一概念,对这两个领域的边界进行了新的探索。这样的研究有助于深化我们对不可计算性和随机性的理解,对于理论计算机科学和可计算性理论的发展具有重要意义。
![](https://csdnimg.cn/release/download_crawler_static/88734674/bg4.jpg)
剩余16页未读,继续阅读
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://profile-avatar.csdnimg.cn/default.jpg!1)
- 粉丝: 5
- 资源: 2万+
我的内容管理 展开
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的C币 登录后查看C币余额
我的收藏
我的下载
下载帮助
![](https://csdnimg.cn/release/wenkucmsfe/public/img/voice.245cc511.png)
最新资源
- 计算机人脸表情动画技术发展综述
- 关系数据库的关键字搜索技术综述:模型、架构与未来趋势
- 迭代自适应逆滤波在语音情感识别中的应用
- 概念知识树在旅游领域智能分析中的应用
- 构建is-a层次与OWL本体集成:理论与算法
- 基于语义元的相似度计算方法研究:改进与有效性验证
- 网格梯度多密度聚类算法:去噪与高效聚类
- 网格服务工作流动态调度算法PGSWA研究
- 突发事件连锁反应网络模型与应急预警分析
- BA网络上的病毒营销与网站推广仿真研究
- 离散HSMM故障预测模型:有效提升系统状态预测
- 煤矿安全评价:信息融合与可拓理论的应用
- 多维度Petri网工作流模型MD_WFN:统一建模与应用研究
- 面向过程追踪的知识安全描述方法
- 基于收益的软件过程资源调度优化策略
- 多核环境下基于数据流Java的Web服务器优化实现提升性能
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035111.png)
![](https://csdnimg.cn/release/wenkucmsfe/public/img/green-success.6a4acb44.png)