测量位序列复杂度的方法

Question

我正在寻找一种简单的方法来估计一个固定大小（可能是最大长度为10）的位序列的复杂性。例如，我想0000000和111111根本不是很复杂，但101010和101101位于频谱的其他地方。

我知道Kolmogorov的复杂性是不可计算的，但它是否可以用二进制字母表对固定（和小）长度的序列进行简单编程？还是有另一种措施可能只是近似的措施，但更容易计算？

该措施非常简单，以便我可以向其他（尽管受过良好教育的）人解释这一点非常重要。

谢谢。

Answer 1

您需要有一个计算复杂度的程序，并且没有最佳程序。

例如，您可以运行代码字符串，并计算运行次数。

您可以通过LZW压缩器（如ZIP）运行字符串，并将压缩的大小报告给它。

您不必只选择一种方法。 你的方法可能是尝试五种不同的方法，并报告给你最小尺度的方法。

例如，您可以尝试初始颠倒其他位，然后尝试运行编码。 或尝试反转位2和3，然后反转位6和7，依此类推。

这些都是可能的方法来获得一个措施，但他们就是这样。

Kolmogorov复杂度是最小程序的大小，以位为单位，可以重现字符串，这取决于语言（无论是高级，装配，机器或图灵机，还是代码驱动特殊为此目的创建的程序）。

你知道它存在，因为你知道有上限和下限。任何可以重现字符串的程序都会给你一个上限。你知道空的程序不能，所以这给你一个零的下界。所以它介于两者之间，但这并不意味着你可以找到它。

请记住，谈论一个字符串的复杂性并没有意义，因为测量工具可以针对该字符串进行优化。 你真的需要谈论的字符串人口，只是为了保持工具诚实。