我正在寻找一种算法，可以计算给定输入字符串的Kolmogorov复杂度的近似值。因此，如果K是字符串S的Kolmogorov复杂度，并且t表示时间，那么函数将表现得像这样...... limit（t-> inf）[K_approx（t，S）] = K.
我正在寻找一种算法，可以计算给定输入字符串的Kolmogorov复杂度的近似值。因此，如果K是字符串S的Kolmogorov复杂度，并且t表示时间，那么函数将表现得像这样...... limit（t-> inf）[K_approx（t，S）] = K.
理论上，当运行时间接近无穷大时，程序可以收敛其输入字符串的Kolmogorov复杂性。它可以通过并行运行每个可能的程序来工作，即输入字符串的长度或更短。当找到给定长度的程序时，该长度被识别为现在已知的最小长度，被打印，并且不再有程序> =该长度被尝试。该算法（很可能）将永远运行，打印更短和更短的长度，在无限时间内收敛于精确的Kolmogorov复杂度。
当然，运行指数数量的程序是非常难以控制的。一个更有效的算法是发布一个 在StackOverflow上编码高尔夫。一些缺点：
该 维基百科页面 对于Kolmogorov，复杂性在“基本结果”部分下有一个标题为“Kolmogorov复杂性的不可复制性”的小节。这不是一个可以计算甚至有效近似的基本衡量标准。
毫无疑问，有更好的方法可以达到你想要的效果。如果你想要一个随机度量，你可以尝试二进制熵函数。其中一种标准算法的可压缩性也可能符合要求。
我觉得这可能有用吗？如果有人看到错误，请指出。
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;
我注意到的第一个问题是“Kolmogorov复杂性”没有明确定义。它在某种程度上取决于如何表示程序的选择。因此，您需要做的第一件事就是修复一些程序编码（例如，Joey Adams的规范，程序用J编写）。
一旦进行了编码，您正在寻找的算法非常简单。看到乔伊的答案。
但情况甚至比必须运行指数多的程序还要糟糕。每个程序都可以运行，只要你可以想象（技术上：运行时作为函数输入大小可以比任何递归函数增长更快）。更重要的是，可能是一些最短的程序是运行时间最长的程序。因此，当时间变为无穷大时，并行方法将接近正确的值，但它将以难以想象的速度缓慢地进行。
您可以提前停止程序，确定该点的近似值足够好。但是，你一般不知道这种近似有多好。事实上，有些定理表明你永远不会知道。
所以简短的回答是“简单，只需使用Joey的算法”，但无论如何，实际上，答案是“你没有机会”。正如rwong所推荐的那样，你最好只使用重型压缩算法。