更改

=== 柯氏复杂度 ===

=== 柯氏复杂度 ===

[[柯式复杂度]][math]\displaystyle{ K(x) }[/math]是指在通用确定性[[图灵机]]（Universal Turing Machine，简称UTM）上运行时输出的最小程序所需的比特数。不同的程序语言描述同一程序的[math]\displaystyle{ K(x) }[/math]是可以比较的，但也无法确定哪种程序语言有最小的[math]\displaystyle{ K(x) }[/math]，同一种程序语言在描述不同程序时[math]\displaystyle{ K(x) }[/math]也并不相同，所以柯式复杂度通常是不可计算的。如果待测对象是由信息源（例如[[马尔可夫链]]）生成的离散符号序列[math]\displaystyle{ s^L }[/math] ，[math]\displaystyle{ L }[/math]为序列的长度，柯式复杂度与香农熵率[math]\displaystyle{ h_μ }[/math]的关系为：

在已有的众多复杂度量化指标中，柯氏复杂度是最符合我们要求的一个指标，[[柯式复杂度]][math]\displaystyle{ K(x) }[/math]是指在通用确定性[[图灵机]]（Universal Turing Machine，简称UTM）上运行时生成字符串[math]\displaystyle{ x }[/math]的最小程序长度。UTM的能力在于可以模拟任何图灵机，因此可以执行任何可计算的过程。柯氏复杂度则依赖于这种通用性，通过UTM，可以理解任何字符串或数据的最短生成程序。但因为图灵停机问题的存在，我们无法构造一个通用算法来决定任意程序是否会在给定输入上停机。这意味着我们不能有效地判断哪些程序是最短的，因为没有方法可以保证找到最短程序的存在与否。由于没有通用的方法来验证或找到生成字符串[math]\displaystyle{ x }[/math]的最短程序，我们就无法计算柯氏复杂度。即使我们能够找到一个生成字符串[math]\displaystyle{ x }[/math]的程序，我们也无法保证它是最短的。为了确定程序是否为最短程序，我们需要检查所有可能的程序，而这一过程在计算上是不可行的。如果待测对象是由信息源（例如[[马尔可夫链]]）生成的离散符号序列[math]\displaystyle{ s^L }[/math] ，[math]\displaystyle{ L }[/math]为序列的长度，柯式复杂度与香农熵率[math]\displaystyle{ h_μ }[/math]的关系为：

<math>

<math>