275
个编辑
更改
跳到导航
跳到搜索
第56行：
第56行： − 粗略地说，柯式复杂度[math]\displaystyle{ K(x) }[/math]需要考虑对象中的所有比特，包括随机状态。其主要后果是[math]\displaystyle{ K(x) }[/math]中数值[math]\displaystyle{ x }[/math]被随机性的生成所主导，因此掩盖了对象以及其生成过程中的重要结构。相比之下，统计复杂度[math]\displaystyle{ C_μ(x) }[/math]剔除了通用图灵机在模拟随机比特时所花费的计算努力。统计复杂度的一个特征是，对于完全随机对象，有[math]\displaystyle{ C_μ(x)=0 }[/math]，如抛硬币产生的序列。同时对于简单的周期性过程，如[math]\displaystyle{ x=00000000…0 }[/math]时，也有[math]\displaystyle{ C_μ(x)=0 }[/math]。因此，统计复杂度的值对于（简单的）周期性过程和完全随机过程都很小。如果[math]\displaystyle{ s^L }[/math]表示[math]\displaystyle{ x }[/math]的前[math]\displaystyle{ L }[/math]个符号，那么复杂性之间的关系简单地为：+ + + + + + + + + + + + + + + + + + + + + + +
→统计复杂度
=== '''统计复杂度''' ===
=== '''统计复杂度''' ===
因为柯式复杂度[math]\displaystyle{ K(x) }[/math]需要考虑对象中的所有比特，包括随机状态生成的比特。其主要后果是[math]\displaystyle{ K(x) }[/math]中数值大小[math]\displaystyle{ x }[/math]可能会被随机状态生成的比特所主导，这样会导致对象的特征和重要结构被掩盖。为了避免这个问题，计算力学提出了统计复杂度[math]\displaystyle{ C_μ(x) }[/math]的概念，用来量化对象的复杂性，它反映了对象的结构和动态特性，以及有效建模所需的计算资源。它的公式为
<math>
C_{\mu}(x)=\left\|M_{\min }(x \mid \mathrm{BTM})\right\|
</math>
<math>
C_{\mu}(x)
</math>是统计复杂度，表示时间序列<math>
x
</math>的复杂性度量。它反映了在给定精度<math>
\mu
</math>下，最小模型的复杂度。<math>
M_{\min }(x \mid \mathrm{BTM})
</math>这是在给定伯努利图灵机（Bernoulli-Turing machine，简称BTM）背景下的最小化模型，用于捕捉序列<math>
x
</math>的模式。这个模型是能够有效预测<math>
x
</math>的最简单形式，且在该模型中尽量减少其复杂性。<math>
\left\|⋅\right\|
</math>这个符号表示对模型复杂度的量化，它可以是基于模型状态的数量、参数数量或计算资源的度量。
相比之下，统计复杂度[math]\displaystyle{ C_μ(x) }[/math]剔除了通用图灵机在模拟随机比特时所花费的计算努力。统计复杂度的一个特征是，对于完全随机对象，有[math]\displaystyle{ C_μ(x)=0 }[/math]，如抛硬币产生的序列。同时对于简单的周期性过程，如[math]\displaystyle{ x=00000000…0 }[/math]时，也有[math]\displaystyle{ C_μ(x)=0 }[/math]。因此，统计复杂度的值对于（简单的）周期性过程和完全随机过程都很小。如果[math]\displaystyle{ s^L }[/math]表示[math]\displaystyle{ x }[/math]的前[math]\displaystyle{ L }[/math]个符号，那么复杂性之间的关系简单地为：
[math]\displaystyle{ K(s^L )≈C_μ (s^L )+h_μ L }[/math]
[math]\displaystyle{ K(s^L )≈C_μ (s^L )+h_μ L }[/math]