柯尔莫哥洛夫复杂度近似算法

Question

我正在寻找一种算法，可以计算给定输入字符串的柯尔莫哥洛夫复杂度的近似值。因此，如果 K 是字符串 S 的柯尔莫哥洛夫复杂度，并且 t 代表时间，那么该函数的行为将类似于以下所示： limit(t->inf)[K_approx(t,S)] = K。

Answer 1

理论上，当运行时间接近无穷大时，程序可以收敛于其输入字符串的柯尔莫哥洛夫复杂度。它可以通过并行运行每个可能的程序（输入字符串的长度或更短）来工作。当找到给定长度的节目时，该长度被识别为目前已知的最小长度，被打印，并且不再尝试>=该长度的节目。该算法（很可能）将永远运行，打印越来越短的长度，在给定无限时间的情况下收敛于精确的柯尔莫哥洛夫复杂度。

当然，运行指数数量的程序是非常困难的。更有效的算法是在 StackOverflow 上发布代码高尔夫 。一些缺点：

• 可能需要几天时间才能找到好的结果。
• 它使用了大量我们最宝贵的计算资源，造成了数千美元的生产力损失。
• 随着时间的推移，由于资源被转移到其他 计算。
• 该算法提前终止，这意味着它不会工作一般。

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;

Answer 3

看来雷·所罗门诺夫在这个领域做了很多工作。

雷·所罗门诺夫的出版物

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

算法概率能解决归纳问题吗？

Answer 4

柯尔莫哥洛夫复杂度的维基百科页面有一个标题为“柯尔莫哥洛夫复杂度的不可计算性”的小节，位于“基本结果”部分。这并不是一个可以有效计算甚至近似的基本度量。

毫无疑问，有更好的方法可以实现您想要的目标。如果您想要衡量随机性，您可以尝试二元熵函数。标准算法之一的可压缩性也可能符合要求。

Answer 5

我注意到的第一个问题是“柯尔莫哥洛夫复杂性”没有明确定义。这在某种程度上取决于如何表示程序的选择。因此，您需要做的第一件事是修复程序的某些编码（例如，Joey Adams 的程序用 J 编写的规范）。

一旦你有了编码，你正在寻找的算法就非常简单了。请参阅乔伊的回答。

但情况比必须运行指数级数量的程序还要糟糕。这些程序中的每一个都可以像您想象的那样运行（从技术上讲：作为函数输入大小的运行时间可能比任何递归函数增长得更快）。更重要的是，有些最短的程序可能运行时间最长。因此，虽然并行方法会随着时间趋向无穷大而接近正确值，但其速度会慢得难以想象。

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

所以简短的答案是“简单，只需使用乔伊的算法”，但无论从实用性的角度来看，答案是“你没有机会”。正如 rwong 所建议的，您最好只使用重型压缩算法。