更改

</math>下，能够生成该序列的最小伯努利图灵机的程序长度。

</math>下，能够生成该序列的最小伯努利图灵机的程序长度。

这里，[[伯努利图灵机]]（Bernoulli-Turing machine，简称BTM）是一种[[概率性图灵机]]，是确定性图灵机的一种扩展。它通过引入随机数发生器，可以生成离散的随机序列。伯努利图灵机包含输入纸带、输出纸带、有限状态控制单元和工作纸带。在运行过程中，伯努利图灵机按照常规图灵机的方式读取纸带上的符号和自身的当前状态，并依据内置的规则表进行操作。与普通图灵机不同的是，其规则表中有一些与随机相关的规则时，它会根据随机数发生器的采样结果来决定具体的执行路径。例如，在某个状态下，图灵机可能有两种可选的操作，普通图灵机根据确定的规则选择其中一种，而伯努利图灵机则通过随机源（即随机数发生器）以一定的概率来决定执行哪一种操作。

这里，[[伯努利图灵机]]（Bernoulli-Turing machine，简称BTM）是一种[[概率性图灵机]]，是确定性图灵机的一种扩展。它通过引入随机数发生器，可以生成离散的随机序列。伯努利图灵机包含输入纸带、输出纸带、有限状态控制单元和工作纸带。在运行过程中，伯努利图灵机按照常规图灵机的方式读取纸带上的符号和自身的当前状态，并依据内置的规则表进行操作。与普通图灵机不同的是，其规则表中有一些可随机执行的规则，它会根据随机数发生器的采样结果来决定具体的执行路径。例如，在某个状态下，图灵机可能有两种可选的操作，普通图灵机根据确定的规则选择其中一种，而伯努利图灵机则通过随机源（即随机数发生器）以一定的概率来执行其中的某一种操作。

<math>M_{\min }(x \mid \mathrm{BTM})</math>代表在能够捕捉数据[math]x[/math]条件下的所有伯努利图灵机中的最小的模型<ref>C. H. Bennett. Dissipation, information, computational complexity, and the definition of organization. In D. Pines, editor, ''Emerging Syntheses in the Sciences''. Addison-Wesley, Redwood City, 1988.</ref>。这个模型是能够有效预测<math>x</math>的最简单形式，且在该模型中尽量减少其复杂性。<math>\left\|⋅\right\|</math>这个符号表示对模型复杂度的量化，例如图灵机的指令表长度。

<math>M_{\min }(x \mid \mathrm{BTM})</math>代表在能够捕捉数据[math]x[/math]条件下的所有伯努利图灵机中的最小的模型<ref>C. H. Bennett. Dissipation, information, computational complexity, and the definition of organization. In D. Pines, editor, ''Emerging Syntheses in the Sciences''. Addison-Wesley, Redwood City, 1988.</ref>。这个模型是能够有效预测<math>x</math>的最简单形式，且在该模型中尽量减少其复杂性。<math>\left\|⋅\right\|</math>这个符号表示对模型复杂度的量化，例如图灵机的指令表长度。

统计复杂度的一个特征是，对于完全随机对象，有[math]\displaystyle{ C_μ(x)=0 }[/math]，如抛硬币产生的序列。同时对于简单的周期性过程，如[math]\displaystyle{ x=00000000…0 }[/math]时，也有[math]\displaystyle{ C_μ(x)=0 }[/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{ C_μ(x) }[/math]剔除了通用图灵机在模拟随机比特时所花费的计算努力。

下图展示了柯式复杂度和统计复杂度随着序列从简单周期性变为完全随机的过程中二者的差异。如图(a)所示，柯式复杂度会随着序列随机性的增加而单调递增。相反，统计复杂度在周期和随机两个极端点上均为零，并在中间达到最大值（见图(b)）。这反映出如下的观点：随机性在统计上是简单的，一个完全随机的过程具有零统计复杂度；周期性在统计上也是简单的，一个完全周期性过程具有较低的统计复杂度。复杂过程在这两个极端之间产生，并且是可预测机制和随机机制的混合，有中等程度随机性的数据具有最大的统计复杂度。

下图展示了柯式复杂度和统计复杂度随着序列从简单周期性变为完全随机的过程中二者的差异。如图(a)所示，柯式复杂度会随着序列随机性的增加而单调递增。相反，统计复杂度在周期和随机两个极端点上均为零，并在中间达到最大值（见图(b)）。这反映出如下的观点：随机性在统计上是简单的，一个完全随机的过程具有零统计复杂度；周期性在统计上也是简单的，一个完全周期性过程具有较低的统计复杂度。复杂过程在这两个极端之间产生，并且是可预测机制和随机机制的混合，有中等程度随机性的数据具有最大的统计复杂度。