Kolmogorov复杂度

对象或算法的Kolmogorov复杂度是其最优规格的长度。在某种意义上，它可以被认为是一种算法熵，在这个意义上，它是包含在对象中的信息量。

这是游戏的截图.kkrieger．

考虑到图像，游戏必须至少有几百兆字节，对吗?它只有96千字节。

考虑字符串11111111111111111111111111111111而且4 c1j5b2p0cv4w1x8rx2y39umgw5q85s7．

描述第一个字符串最明显的方法是说它包含32个1。

1

取32＄周期“1”

描述包含的字符比字符串本身更少。

另一方面，在haskell中描述另一个字符串的最好方法是(可能)直接定位它。

这就是为什么第二个弦实际上更复杂。

用像英语这样丰富的语言来描述事物的复杂性，对于任何知道贝瑞悖论的人来说都不是不知道的。

贝里悖论声称复杂性英语中所有整数的最小值为11。如果不是，那么就会有第一个不是的整数。但是，它也可以被描述为最小的正整数，不能在十一个字以内定义。

这可以看作是一个直观的原因uncomputablityKolmogorov复杂度。

如果你对代码高尔夫、过程生成或压缩理论感兴趣，你的领域一定与Kolmogorov复杂性有关。

Kolmogorov复杂度 $K$相对于图灵机 $f$一串串的 $x,$是

$K_f(x) = \min \{|p|: f(p) =x \}。$

看来复杂性取决于 $f$还有 $x$．在某种程度上，这是不可避免的，因为描述确实依赖于描述语言。

然而，如果图灵机是通用的，那么在这样的图灵机中，字符串的复杂性之间的差异将以常数的形式变化。

这就是所谓的不变性定理．证明来自于对图灵机进行编码，然后在图灵机中编写程序的想法。第一部分(即编码的图灵机)不依赖于字符串，因此是一个常数。

$x$是不可压缩的当且仅当

$K(x) \geq x。$

不可压缩字符串也可以被调用随机算法．

对所有 $n$，则存在长度大于或等于的不可压缩字符串 $n。$

证明只是鸽子洞原理的一个简单应用。

有 $2 ^ n$字符串的 $n$有些，但确实有 $2^n - 1$尺寸小于的描述 $n。$这是因为

$\sum_{i=0}^{n-1} {2^i} = 2^n -1。\ _ \广场$

不难看出，大多数字符串是不可压缩的。然而，由于Kolmogorov复杂度的不可计算性，我们很快就会看到不可压缩性是不可判定的。

此时，您应该能够了解为什么您的压缩软件可以很好地压缩某些内容，而其他内容则不能很好地压缩。你应该理解为什么编写一个好的压缩算法是如此的困难和有趣。

我们需要从定义开始:

形式语言的复杂性是指列出该语言中所有字符串的程序的复杂性。

$K (\ cdot)$是无法计算的。

没有复杂的正式系统 $n$能证明一个物体有吗 $K(x) > n。$

假设。在这种情况下，形式系统将能够证明对象具有复杂性 $n '$．然后它会对物体的描述进行编码 $n$位。自 $N ' > N$，这是一个矛盾。

由于任何程序的复杂性都是有限的，因此必然存在一串比它无法决定其复杂性的程序的复杂度更高的字符串。 $_ \广场$

如果这个证明不能说服你，看看下面的非正式证明:

假设有一个函数柯尔莫哥洛夫(x)它的定义是 $n$位。

现在，我们可以定义一个有长度的程序 $米$像这样的片段:

1 2 3 4

对于长度为I的字符串x, I = 1到无穷，如果kolmogorov(x) > m+n打印x

从结构上看，这个程序应该输出所有复杂度大于 $m + n$．因为这个程序的复杂程度 $m + n$，我们有一个矛盾，因为这实际上意味着这些字符串的复杂性不超过 $m + n$因为有一种不那么复杂的输出方式。

1

-［------->+<］>-．［--->++++<］>+．-［++>-----<］>．．+++++++++．-［---->+<］>++．+［->++<］>．-［--->+<］>--．+++++++++．++．------------．----．---．+［--->+<］>+++．-［---->+<］>+++．

如果你一直跟着看，你应该会发现这是贝瑞悖论的一个版本。

人类是否可以决定不可压缩性或停止问题的哲学问题仍然存在。如果是的话，那就意味着大脑是一个无限复杂的物体。

此部分需要扩展。

这是一种通用的证明技术，它依赖于存在任意长度的不可压缩字符串这一事实。这是用来表明一个类中的特定属性成立，通过表明相反的情况将暗示不存在任意长度的随机字符串。

证明有无穷多个质数。

---