In this paper we show that the approximating the Kolmogorov complexity of a set of numbers is equivalent to having common information with the halting sequence. The more precise the approximations are, and the greater the number of approximations, the more information is shared with the halting sequence. An encoding of the 2^N unique numbers and their Kolmogorov complexities contains at least >N mutual information with the halting sequence. We also provide a generalization of the "Sets have Simple Members" theorem to conditional complexity.


翻译:在本文中,我们显示,对一组数字的科尔莫戈罗夫复杂程度的接近程度相当于拥有与停止序列相同的信息。近似越精确,近似数量越多,与停止序列共享的信息就越多。2 ⁇ N的独特数字及其科尔莫戈罗夫复杂程度的编码至少包含有停止序列的 >N 的相互信息。我们还提供了“Sets有简单成员”理论的概括性,以有条件的复杂程度为条件。

0
下载
关闭预览

相关内容

《计算机信息》杂志发表高质量的论文,扩大了运筹学和计算的范围,寻求有关理论、方法、实验、系统和应用方面的原创研究论文、新颖的调查和教程论文,以及描述新的和有用的软件工具的论文。官网链接:https://pubsonline.informs.org/journal/ijoc
专知会员服务
50+阅读 · 2020年12月14日
知识图谱推理,50页ppt,Salesforce首席科学家Richard Socher
专知会员服务
106+阅读 · 2020年6月10日
深度强化学习策略梯度教程,53页ppt
专知会员服务
178+阅读 · 2020年2月1日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
103+阅读 · 2019年10月9日
【论文笔记】通俗理解少样本文本分类 (Few-Shot Text Classification) (1)
深度学习自然语言处理
7+阅读 · 2020年4月8日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
SLAM的动态地图和语义问题
计算机视觉life
24+阅读 · 2019年4月27日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Arxiv
0+阅读 · 2021年3月28日
Arxiv
0+阅读 · 2021年3月28日
Arxiv
0+阅读 · 2021年3月26日
VIP会员
相关资讯
【论文笔记】通俗理解少样本文本分类 (Few-Shot Text Classification) (1)
深度学习自然语言处理
7+阅读 · 2020年4月8日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
SLAM的动态地图和语义问题
计算机视觉life
24+阅读 · 2019年4月27日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Top
微信扫码咨询专知VIP会员