Kolmogorov复杂性：扩展和应用程序

免责声明：此文本在我的数字货架上铺设了太长，仍未收到它应该受到的注意力和严谨。我仍然希望好奇的读者了解新的东西。

这个文本的墙壁致力于我最喜欢的CS概念（到目前为止）：Kolmogorov复杂性。它在那里用图形，树木和递归。它的美丽源于其简单的定义和强大的联系，以及许多我花哨的研究领域。它定义如下：产生给定序列的最小程序的长度。

这可能听起来对未纠正的读者来说，但坚持不懈，在这个简单的概念之后，这是一个深层影响和应用的整个世界。

了解序列的Kolmogorov复杂性意味着了解可以知道的所有内容。它是删除数据中存在的所有可计算冗余的过程，到达最短的算法，从而使用计算（空间，时间和能量）引起这些模式。

k（“ababababab”）＆lt; K（“AASDJKLPZ”）K（“3.141”）＆lt; K（“10011110100111010”）

计算N比特长度的序列X的Kolmogorov复杂度是一个非常坚韧的螺母，以裂缝，因为产生任何长度序列N的可能程序的搜索空间相对于输入尺寸N呈指数级增长。甚至更糟糕的是它需要它臭名昭着的暂停问题，这是不可计算的。 K（x）最明显的上限显然是x本身的长度n。

我们仍然可以实现一个程序，该程序生成2 ^ N个不同的程序，并过滤掉所选择的编程语言的所有无效程序。我们留下了一个巨大的有效节目清单，长度低于n。

可悲的是，我们不能仅执行这至少有限量的程序，过滤它们的输出给定序列，并通过按长度对有效的剩余程序进行排序来完成。一些程序将需要年龄终止，有些甚至可能永远不会 - 我们不能分开，因为艾伦在臭名昭着的暂停问题证明了。

单独的Kolmogorov复杂性很简单而美丽，但我们了解到这是不实际的计算。因此，让我们尝试通过计算机程序的一些实际属性将其扩展，如它们的总执行时间和最大分配空间（例如RAM）。这产生了密切相关的复杂性措施，应该更容易近似，因此对实际应用更具相关性，因为我们最终可以计算它们。

K（x）是正常的Kolmogorov复杂性功能。 kt（x）是重量程序执行到度量的扩展。 KTS（X）还考虑该计划的空间要求。

好的，现在是什么？让我们做电脑科学家喜欢做和欺骗我们的方式使用足够好的启发式/近似的力量。处理运行过长甚至无限的程序的一种简单方法是在42秒之后丢弃它们。

这个看似肮脏的技巧实际上非常有用，它过滤了运行太长的程序。通过这样做，我们丢失了找到真正的Kolmogorov复杂性的保证，因为一个非常短的程序可能很长，直到它最终输出x（输入序列）。 Sidenote：有一篇论文，它还具有直观的感觉，即计划的源长度与其执行时间相关的源长度有助于我们。因此，我们丢失了找到真正的K（x）的保证，但仍然留下短暂（不一定是最短的！）在我们所需的最长时间执行的程序。

另一个不错的事实是，懒洋洋地搜索最短的节目仍然是最佳的（在我们的近似范围内），因为我们在找到在我们的时间限制内产生输入序列x的第一个（因此最短）程序时完成的，除非我们想要继续搜索对于一个潜在的程序（尽管在它们的大小增长时，它可能不太可能找到更快的执行程序）。

所以我刚刚描述了k（x）的可计算版本？没有，但实际的近似。我们搜索在预定义的时间/计算资源限制内产生x的最短程序k（x，t = <42）。从最短的程序开始，并迭代地复制所有可能程序的树。不停止或简单执行的程序只是丢弃了，因为无论如何我们想要高效的程序，这很好。

像Zip这样的常见无损数据压缩工具仅是其输入的真正Kolmogorov复杂性的近似值。 压缩数据的长度加上解压缩数据的程序的长度是真正的Kolmogorov复杂度的上限。 “Kolmogorov复杂性是可计算的：没有算法，当输入任意数据序列时，输出产生数据的最短程序。” - 维基百科 压缩距离（CD）将两个对象A，B（例如文本文件）作为参数，并通过使用Kolmogorov复杂度或Praxis在A，B和B上的近似（例如压缩算法）C（x）上定义相似度分数。 B. 然后定义CD为：LEN（C（A + B））/（LEN（C（a））+ len（c（b））） 如果是一个＆amp; b非常相似C（A + B）不会大于C（a）或c（b），反之亦然，如果a＆amp; B是不同的C（A + B）将远远大于C（a）或c（b）。