A Computable Measure of Algorithmic Probability by Finite Approximations with an Application to Integer Sequences
A Computable Measure of Algorithmic Probability by Finite Approximations with an Application to Integer Sequences
复制标题
DOI：
10.1155/2017/7208216
复制
发表时间：
2017-01-01
期刊：
影响因子：
2.3
通讯作者：
Zenil, Hector
中科院分区：
文献类型：
--
作者：
Soler-Toscano, Fernando;Zenil, Hector
鉴于广泛使用的无损压缩算法近似算法（Kolmogorov-Chaitin）的复杂性，通常，通用无损压缩算法在表征特征以外的统计特征与熵评估没有什么不同，在这里，我们探索一种替代和补充的方法。我们研究的形式性质的莱文启发措施。根据小型图灵机的输出分布计算。我们介绍和证明有限approximationsm（k），已被用于在sometapplications作为一种替代无损压缩算法的近似算法（Kolmogorov-Chaitin）的复杂性。我们证明了m和m（k）的相关性质，并将它们与Levin的普适分布进行了比较。最后，我们提出了一个应用程序的整数序列从在线百科全书的序列，这表明我们的AP为基础的措施可能会表征非统计模式，我们报告有趣的相关性与文字，功能，和程序描述长度的序列。
Given the widespread use of lossless compression algorithms to approximate algorithmic (Kolmogorov-Chaitin) complexity and that, usually, generic lossless compression algorithms fall short at characterizing features other than statistical ones not different from entropy evaluations, here we explore an alternative and complementary approach. We study formal properties of a Levin-inspired measure.. calculated from the output distribution of small Turing machines. We introduce and justify finite approximationsm(k) that have been used in someapplications as an alternative to lossless compression algorithms for approximating algorithmic (Kolmogorov-Chaitin) complexity. We provide proofs of the relevant properties of both m and m(k) and compare them to Levin's UniversalDistribution. We provide error estimations of m(k) with respect to m Finally, we present an application to integer sequences from the On-Line Encyclopedia of Integer Sequences, which suggests that our AP-based measures may characterize nonstatistical patterns, and we report interesting correlations with textual, function, and program description lengths of the said sequences.