• 文献检索
  • 文档翻译
  • 深度研究
  • 学术资讯
  • Suppr Zotero 插件Zotero 插件
  • 邀请有礼
  • 套餐&价格
  • 历史记录
应用&插件
Suppr Zotero 插件Zotero 插件浏览器插件Mac 客户端Windows 客户端微信小程序
定价
高级版会员购买积分包购买API积分包
服务
文献检索文档翻译深度研究API 文档MCP 服务
关于我们
关于 Suppr公司介绍联系我们用户协议隐私条款
关注我们

Suppr 超能文献

核心技术专利：CN118964589B侵权必究
粤ICP备2023148730 号-1Suppr @ 2026

文献检索

告别复杂PubMed语法，用中文像聊天一样搜索，搜遍4000万医学文献。AI智能推荐，让科研检索更轻松。

立即免费搜索

文件翻译

保留排版，准确专业，支持PDF/Word/PPT等文件格式，支持 12+语言互译。

免费翻译文档

深度研究

AI帮你快速写综述，25分钟生成高质量综述，智能提取关键信息，辅助科研写作。

立即免费体验

一种用于逼近柯尔莫哥洛夫前缀复杂度的加法最优解释器。

An Additively Optimal Interpreter for Approximating Kolmogorov Prefix Complexity.

作者信息

Leyva-Acosta Zoe, Acuña Yeomans Eduardo, Hernandez-Quiroz Francisco

机构信息

Ciencia e Ingenieria de la Computacion, Universidad Nacional Autónoma de México, Ciudad Universitaria, Mexico City 04510, Mexico.

Facultad de Ciencias, Universidad Nacional Autónoma de México, Ciudad Universitaria, Mexico City 04510, Mexico.

出版信息

Entropy (Basel). 2024 Sep 20;26(9):802. doi: 10.3390/e26090802.

DOI:10.3390/e26090802
PMID:39330135
原文链接:https://pmc.ncbi.nlm.nih.gov/articles/PMC11431414/
Abstract

We study practical approximations of Kolmogorov prefix complexity () using IMP2, a high-level programming language. Our focus is on investigating the optimality of the interpreter for this language as the reference machine for the Coding Theorem Method (CTM). This method is designed to address applications of algorithmic complexity that differ from the popular traditional lossless compression approach based on the principles of algorithmic probability. The chosen model of computation is proven to be suitable for this task, and a comparison to other models and methods is conducted. Our findings show that CTM approximations using our model do not always correlate with the results from lower-level models of computation. This suggests that some models may require a larger program space to converge to Levin's universal distribution. Furthermore, we compare the CTM with an upper bound on Kolmogorov complexity and find a strong correlation, supporting the CTM's validity as an approximation method with finer-grade resolution of .

摘要

我们使用一种高级编程语言IMP2来研究柯尔莫哥洛夫前缀复杂度（）的实际近似值。我们的重点是研究该语言的解释器作为编码定理方法（CTM）的参考机器的最优性。这种方法旨在解决与基于算法概率原理的流行传统无损压缩方法不同的算法复杂度应用。所选的计算模型被证明适用于此任务，并与其他模型和方法进行了比较。我们的研究结果表明，使用我们的模型的CTM近似值并不总是与较低级计算模型的结果相关。这表明某些模型可能需要更大的程序空间才能收敛到莱文的通用分布。此外，我们将CTM与柯尔莫哥洛夫复杂度的上限进行了比较，发现有很强的相关性，支持CTM作为具有更精细分辨率的近似方法的有效性。

https://cdn.ncbi.nlm.nih.gov/pmc/blobs/855a/11431414/e7c2a130a276/entropy-26-00802-g006.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/855a/11431414/577e7fee08ed/entropy-26-00802-g001.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/855a/11431414/02d354dfd877/entropy-26-00802-g002.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/855a/11431414/450b2d129f25/entropy-26-00802-g003.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/855a/11431414/8ef0bd180272/entropy-26-00802-g004.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/855a/11431414/d2ad63e8cda8/entropy-26-00802-g005.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/855a/11431414/e7c2a130a276/entropy-26-00802-g006.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/855a/11431414/577e7fee08ed/entropy-26-00802-g001.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/855a/11431414/02d354dfd877/entropy-26-00802-g002.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/855a/11431414/450b2d129f25/entropy-26-00802-g003.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/855a/11431414/8ef0bd180272/entropy-26-00802-g004.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/855a/11431414/d2ad63e8cda8/entropy-26-00802-g005.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/855a/11431414/e7c2a130a276/entropy-26-00802-g006.jpg

相似文献

1
An Additively Optimal Interpreter for Approximating Kolmogorov Prefix Complexity.一种用于逼近柯尔莫哥洛夫前缀复杂度的加法最优解释器。
Entropy (Basel). 2024 Sep 20;26(9):802. doi: 10.3390/e26090802.
2
A Decomposition Method for Global Evaluation of Shannon Entropy and Local Estimations of Algorithmic Complexity.一种用于香农熵全局评估和算法复杂度局部估计的分解方法。
Entropy (Basel). 2018 Aug 15;20(8):605. doi: 10.3390/e20080605.
3
Symmetry and Correspondence of Algorithmic Complexity over Geometric, Spatial and Topological Representations.算法复杂性在几何、空间和拓扑表示上的对称性与对应性。
Entropy (Basel). 2018 Jul 18;20(7):534. doi: 10.3390/e20070534.
4
Discovering Neural Nets with Low Kolmogorov Complexity and High Generalization Capability.发现具有低柯尔莫哥洛夫复杂度和高泛化能力的神经网络。
Neural Netw. 1997 Jul;10(5):857-873. doi: 10.1016/s0893-6080(96)00127-x.
5
A Review of Methods for Estimating Algorithmic Complexity: Options, Challenges, and New Directions.算法复杂度估计方法综述：选项、挑战与新方向
Entropy (Basel). 2020 May 30;22(6):612. doi: 10.3390/e22060612.
6
Algorithmic Probability Method Versus Kolmogorov Complexity with No-Threshold Encoding Scheme for Short Time Series: An Analysis of Day-To-Day Hourly Solar Radiation Time Series over Tropical Western Indian Ocean.用于短时间序列的无阈值编码方案的算法概率方法与柯尔莫哥洛夫复杂性：对热带西印度洋逐日逐小时太阳辐射时间序列的分析
Entropy (Basel). 2019 May 31;21(6):552. doi: 10.3390/e21060552.
7
Calculating Kolmogorov complexity from the output frequency distributions of small Turing machines.从小型图灵机的输出频率分布计算柯尔莫哥洛夫复杂度。
PLoS One. 2014 May 8;9(5):e96223. doi: 10.1371/journal.pone.0096223. eCollection 2014.
8
Methods of information theory and algorithmic complexity for network biology.网络生物学的信息论与算法复杂性方法
Semin Cell Dev Biol. 2016 Mar;51:32-43. doi: 10.1016/j.semcdb.2016.01.011. Epub 2016 Jan 21.
9
Algorithmic complexity for short binary strings applied to psychology: a primer.短二进制字符串在心理学中的算法复杂度：简介。
Behav Res Methods. 2014 Sep;46(3):732-44. doi: 10.3758/s13428-013-0416-0.
10
Kolmogorov complexity metrics in assessing L2 proficiency: An information-theoretic approach.用于评估二语水平的柯尔莫哥洛夫复杂度指标：一种信息论方法。
Front Psychol. 2022 Oct 6;13:1024147. doi: 10.3389/fpsyg.2022.1024147. eCollection 2022.

本文引用的文献

1
A Review of Methods for Estimating Algorithmic Complexity: Options, Challenges, and New Directions.算法复杂度估计方法综述：选项、挑战与新方向
Entropy (Basel). 2020 May 30;22(6):612. doi: 10.3390/e22060612.
2
How Incomputable Is Kolmogorov Complexity?柯尔莫哥洛夫复杂性有多不可计算？
Entropy (Basel). 2020 Apr 3;22(4):408. doi: 10.3390/e22040408.
3
A Decomposition Method for Global Evaluation of Shannon Entropy and Local Estimations of Algorithmic Complexity.一种用于香农熵全局评估和算法复杂度局部估计的分解方法。
Entropy (Basel). 2018 Aug 15;20(8):605. doi: 10.3390/e20080605.
4
Calculating Kolmogorov complexity from the output frequency distributions of small Turing machines.从小型图灵机的输出频率分布计算柯尔莫哥洛夫复杂度。
PLoS One. 2014 May 8;9(5):e96223. doi: 10.1371/journal.pone.0096223. eCollection 2014.