一个额外的最佳解释器,用于近似的科尔摩戈罗夫前复杂度
Zoe Leyva-Acosta1, Eduardo Acuña Yeomans1, Francisco Hernandez-Quiroz2
1Ciencia e Ingenieria de la Computacion, Universidad Nacional Autónoma de México, Ciudad Universitaria, Mexico City 04510, Mexico.
本研究探讨了使用IMP2编程语言和编码定理方法 (CTM) 对科尔摩戈罗夫前复杂度 (K) 的实际近似. 研究结果表明,依赖于模型的趋同与莱文的趋同.
科学领域:
- 理论计算机科学 理论计算机科学
- 算法信息理论 算法信息理论
- 计算复杂性 计算复杂性
背景情况:
- 科尔摩戈罗夫前复杂度 (K) 是算法信息的一个基本度量.
- 编码定理方法 (CTM) 为算法复杂性的应用提供了传统压缩的替代方案.
- 调查K的实际近似对于现实世界的应用至关重要.
研究的目的:
- 评估IMP2解释器作为CTM的参考机器的最佳性.
- 在不同的计算模型中比较CTM近似值.
- 评估CTM在接近科尔摩戈罗夫复杂性的有效性.
主要方法:
- 使用IMP2,一个高级编程语言,用于实际的K近似.
- 应用编码定理方法 (CTM) 使用IMP2作为参考机器.
- 将CTM结果与较低级别模型进行比较,并对科尔摩戈罗夫复杂性的上限进行比较.
主要成果:
- 使用IMP2的CTM近似并不总是与较低级别模型相关.
- 一些模型可能需要更大的程序空间来接近莱文的普遍分布.
- 在CTM和科尔摩戈罗夫复杂性的上限之间发现了强烈的相关性,验证了CTM.
结论:
- IMP2解释器是一个适合基于CTM的K近似模型.
- 模型选择影响CTM的融合和与较低级别复杂度指标的相关性.
- CTM提供了一种有效的方法,以高分辨率接近科尔摩戈罗夫复杂度.
更多相关视频
07:08Optimization of Synthetic Proteins: Identification of Interpositional Dependencies Indicating Structurally and/or Functionally Linked Residues
Published on: July 14, 2015
08:21A Simple Method for the Size Controlled Synthesis of Stable Oligomeric Clusters of Gold Nanoparticles under Ambient Conditions
Published on: February 5, 2016
相关概念视频
Accuracy, limits, and approximation
Accuracy is defined as the closeness of the measured value to the true or actual value. In engineering mechanics, repeated measurements are taken during theoretical or experimental analyses to ensure that the result is precise and accurate.
The accuracy of any solution is based on the...
Routh-Hurwitz Criterion I
To apply the Routh-Hurwitz criterion, a Routh table is constructed. The table's rows are labeled with powers of the complex frequency variable s, starting from the...
Routh-Hurwitz Criterion II
The first scenario occurs when a singular zero appears in the first column of the Routh table. This situation creates a division by zero issues. To resolve this, a small positive or negative number, denoted as epsilon (∈), is substituted for the zero. The stability analysis proceeds by assuming a sign for ∈. If ∈ is positive, any sign change in the first...
Linear Approximation in Time Domain
For a simple pendulum with a mass evenly distributed along its length and the center of mass located at half the pendulum's length,...
Theorems of Pappus and Guldinus: Problem Solving
Norton's Theorem
