科尔莫戈洛夫复杂度近似算法

Question

我正在寻找一种算法，可以计算给定输入字符串的Kolmogorov复杂性的近似值。因此，如果K是一个字符串S的Kolmogorov复杂性，t代表时间，那么该函数的行为应该类似于这样... 限制（t->inf）[K_approx（t，S）] = K。

- Tony

---

对于那些不熟悉该主题的人来说，字符串的 Kolmogorov 复杂度本质上是“生成该字符串的最短程序的长度”。例如，使用 J 编程语言（请参见此处）可以在 8 个字符（*/~1+i.9）内生成一个 9x9 的乘法表。由此可知，相对于 J 编程语言，一个 9x9 的乘法表的 Kolmogorov 复杂度为 8 或更低。 - Joey Adams

如果您正在尝试正式证明某些内容，那么您必须独立编写证明，完全忽略用于近似的方法。如果您只是想寻找乐趣，不妨尝试一下数据压缩算法？ - rwong

不，我不是在寻找证明。我正在寻找一个满足上述属性的算法。我一直没有找到，想知道是否有人已经做过了。我不知道任何数据压缩算法可以在原则上找到确切的Kolmogorov复杂性，只要给足够的时间。我想乍一看，由于你总是使用有限的字符串，所有可能的图灵机的枚举搜索可能会起作用...但问题可能是不可判定的。我正在寻找这样的算法，用于机器学习应用。 - Tony

现今的机器学习应用注重于压缩感知、模型简化算法等方面。KC过于理论化。 - rwong

似乎是作业...但 Joey Adams 是正确的。你已经得到了答案。 - PeterAllenWebb

@rwong，KC是理论上的，但像Ray Solomonoff这样的人推动了这些想法作为机器学习的基础。我认为从理论最优解到近似实际解决方案是一个逻辑上的步骤。 - Tony

Answer 1

理论上，随着运行时间趋近于无限，一个程序可以收敛于其输入字符串的科尔莫戈洛夫复杂度。 它可以通过并行运行每个长度等于或小于输入字符串的可能程序来实现。当找到给定长度的程序时，该长度被标识为当前已知的最小长度，并被打印出来，不再尝试其它长度大于等于该长度的程序。该算法（很可能）会永远运行下去，打印出越来越短的长度，并在无限时间内收敛于给定的科尔莫戈洛夫复杂度。

当然，运行指数级别的程序非常难以处理。一种更有效的算法是在 StackOverflow 上发布一个 代码高尔夫竞赛。 但是这种方法也存在一些缺点：

• 需要花费几天时间才能得到好的结果。
• 它消耗大量最宝贵的计算资源，造成数千美元的生产力损失。
• 随着资源被用于其他计算，产生的结果会随着时间的推移变得越来越少。
• 该算法对许多输入过早地 终止，即它在一般情况下不起作用。

- Joey Adams

---

@rwong：没错，这就是为什么要并行运行它们。对于那些似乎永远运行不完的程序，只有在找到更短的解决方案（如果有的话）之前才会允许它们继续运行。 - Joey Adams

蠕虫涌入我的脑海中...（对于那些不熟悉代码高尔夫的人：http://meta.stackexchange.com/questions/20736/what-is-code-golf-on-stack-overflow） - rwong

@Tony：是指空间限制还是程序长度限制？你只需要有限的时间来找到给定运行时间的最短程序（因为它们都会终止，显然）。更不容易想到的是，你只需要有限的时间来找到使用有限空间的最短程序。后者是正确的，因为对于在有限空间内运行的程序，停机问题是可判定的（好好想想）。因此，你可以将运行时间限制为->无穷大或将空间限制为->无穷大。你不需要两者都做。 - Joey Adams

@Joey，这将是检查图灵机的最大“大小”限制。如果我理解正确，您是说在给定一组有限的TM的集合最大“大小”的情况下，您总是可以确定程序是否会停止..因为执行终止分析的程序可以比所有相关的TM都要“大”，从而消除了将终止分析程序本身作为输入的可能性。我知道不可判定性的证明之一涉及将程序本身作为输入。 - Tony

为了防止程序无限运行，近似值可以限制在那些可证明终止的程序中。 - Anderson Green

Answer 2

我认为这可能有效？如果有人发现错误，请指出。

function KApprox(S:string,t:integer,TapeSizeMax:integer) : Turing Machine of size k
  begin

    // An abstract data type that represents a turing machine of size k
    var TM(k:integer) : Turing Machine of size k;
    var TMSmallest(k:integer) : Turing Machine of size k;  

    var j : integer;
    var i : integer;

    for (j = t to 0 step -1) // reduce the time counter by 1
      begin
       for (i = TMax to 1 step -1) // go to the next smaller size of TM
         begin
          foreach (TM(i)) // enumerate each TM of size i
             begin 
               if (TM(i).halt(TapeSizeMax) == true) and (TM(i).output() == S) then
                 begin
                   if (sizeof(TM(i)) < sizeof(TMSmallest(i))) then
                      TMSmallest(i): = TM(i);
                 end;
             end;
         end;
      end;      
    return TMSmallest;
 end;

- Tony

---

我认为致命的缺陷在于 TM[i].output() 可能永远不会返回。 - Gabe

我认为这将解决停止问题。 - Tony

现在的问题是没有halts()函数这样的东西。你可以编写一个适用于某些机器的函数，但并非所有机器都适用。 - Gabe

@好的，所以我指定了halts函数仅适用于大小为TMax的机器。因此.halts（TMax） - Tony

但是你无法为TMax>4编写一个“halts（）”函数。请参阅http://mathworld.wolfram.com/HaltingProblem.html。 - Gabe

好的，那么我们将不得不限制TM的磁带大小... 当TM.halts(TapeSizeMax) == true时。 - Tony

Answer 3

看起来 Ray Solomonoff 在这个领域做了很多工作。

Ray Solomonoff 的出版物

归纳推理理论——解决模式识别和人工智能问题的统一方法。

算法概率是否解决了归纳问题？

- Tony

Answer 4

我注意到的第一个问题是，“科尔莫戈洛夫复杂度”没有被很好地定义。这在某种程度上取决于如何表示程序的选择。因此，你需要做的第一件事就是修复一些编码程序的规范（例如，Joey Adams的规范要求程序用J语言编写）。

一旦你有了编码，你要寻找的算法就非常简单了。请参考Joey的答案。

但情况比运行指数级别的程序还要糟糕。每个程序都可能运行得像你能想象的那样长（技术上：运行时间作为函数输入大小可以增长得比任何递归函数都快）。更重要的是，一些最短的程序可能是运行时间最长的程序。因此，虽然并行方法会随着时间无限接近正确值，但它会以难以想象的缓慢速度进行。

你可以提前停止程序，认为此时的近似值已经足够好了。然而，你通常不知道这个近似值有多好。事实上，有定理表明你永远无法知道。

那么简短的答案是“很容易，只需使用Joey的算法”，但从任何实用性的角度来看，答案是“你没有机会”。正如rwong所建议的那样，最好使用重型压缩算法。

- Aubrey da Cunha

Answer 5

Kolmogorov复杂性的wikipedia page有一个名为“Kolmogorov复杂性的不可计算性”的子部分，位于“基本结果”部分下。这并不是一个旨在计算甚至近似计算的基本度量。

毫无疑问，有更好的方法来实现您想要的。如果您想要一种随机性度量，可以尝试二进制熵函数。使用标准算法之一进行压缩也可能符合要求。

- Rob Lachlan

---

维基百科文章中甚至没有提到“近似可生产性”这个词组。计算字符串的Kolmogorov复杂度的问题并未被提出。这是不可判定的，就此结束。我所寻找的只是一个函数，通过提供更多的时间和空间资源，可以得到越来越好的近似值。 - Tony

@Tony：您的算法未完全指定。我不确定您计划如何测试每个可能的图灵机和每个可能的输入字符串，但即使您以某种有意义的方式完成此操作，时间成本也将呈指数级增长。然而美好的理论看起来很好，但在实践中这不是适合您的东西。 - Rob Lachlan

@Rob，该函数只接受一个字符串作为输入"S:String"，并且仅测试大小为TMax的图灵机。因此，我们不会测试所有图灵机，因此无法获得输入字符串的精确KC值。 - Tony

@Tony - 我认为小型随机生成的图灵机不会成为大多数输入字符串的解决方案（即有效压缩器），这已经被广泛接受了。 - Stephen C

@Tony - 我认为可以默认小的图灵机不会成为大多数输入字符串的解决方案（即有效的压缩器）。任何计算近似KC的枚举图灵机的算法都将随着图灵机的大小呈指数级增长。简而言之，这样的算法是不切实际的。 - Stephen C