Kolmogorov-Complexity定义的等效性

Question

有很多方法可以定义 kolmogorov-complexity, 而且，通常，所有这些定义都等效到添加剂常数。那就是$ k_1 $和$ k_2 $是kolmogorov复杂性函数（通过不同的语言或模型定义），则存在一个常数$ c $，因此对于每个字符串$ x $，$ | k_1（x） - k_2（x）（x） ） <c $。我相信这是因为每个kolmogorov复杂性函数$ k $，并且对于$ k（x） le | x |的每一个$ x $ +c $，对于某些常数$ c $。

我对基于图灵机器的$ k $的以下定义感兴趣

1. 状态数: ：将$ k_1（x）$定义为最小数字$ q $，以使带有$ q $状态的TM在空字符串上输出$ x $。
2. 程序长度: ：将$ k_2（x）$定义为输出$ x $的最短“程序”。即，修复一种将TMS编码为二进制字符串的方法；对于机器$ m $，表示其（二进制）编码为$ langle m rangle $。 $ k_2（x）= min | langle m rangle | $，其中最低限度为所有$ m $'，在空输入上输出$ x $。

$ k_1 $和$ k_2 $等效吗？它们之间的关系是什么？如果它们不等效的话，哪个人的关系更好。

特别是我的问题是$ k_2 $随$ x $增加而增加，这似乎不是超级线性（或至少与常数$ c> 1 $线性，因此$ k_2 <c | x | $，而不是$ | x |+c $）。考虑输出$ x $的最简单的TM - 刚刚编码$ x $作为其状态和过渡功能的一部分。立即看到$ k_1（x） le | x |+1 $。但是，同一台计算机的编码要大得多，而我得到的微不足道的界限是$ k_2（x） le | x | log | x | $。

Answer 1

我提前道歉，因为我给出了太多的细节，但是我要与人矛盾。

大约$ k（x）≤k'（x）+c $

$ k_1（x）≤k_2（x）+c $通常来自一个事实 口译员 描述语言＃2的描述语言＃1和 不是 从从＃2的程序转换为＃1程序的翻译。

例如，$ k_ mathtt {c}（x）≤k_ mathtt {python}（x）+c_ mathtt {py2c} $，您会像这样简单地得到这种不等式：

void py_run(char * s) {
    // code of your Python interpreter
}

int main(void) {
    py_run("Put here your Python program of size Kpython(x)");
}

那么您的常数$ c_ mathtt {py2c} $将是$ 528+490240688 $，其中$ 528 $是此代码的位数，而$ 490240688 $ bits是$ 490240688 $ bits是大小，是官方的二元式翻译，当然只需要C.要解释python的描述语言中的可能性，以便您可以比69 MB做得更好:-)

重要的是您可以编写Python程序 线性 在您的C代码中。例如，您需要在每个字符之间放置“香蕉”的语言不是一个很好的描述程序，属性是错误的。 （但是，如果说明语言授权您在单独的文件或块中写入数据，则此问题消失了）

为什么您的$ k_1（x）= q $有缺陷

您对$ k_1 $的定义的问题在于，您可能需要超过$ q $位来描述带有$ q $状态的图灵机，因为您需要编码过渡。

因此，没有$ k_1 $和$ k_2 $可能不是等效的，但这主要是$ k_1 $的错误。我认为我们可以证明所有$ a> 0 $都有$ c_a $，因此$ k_1（x）≤a| x |+c_a $。当然，任何$ a <1 $都足以证明$ k_1 $不是有效功能的事实，因为这意味着我们可以编码更多的所有$ 2^n $可能的长度$ n $的字符串，以$ n $ $位。

但是，在建造图灵机时，尺寸是一个非常紧密的束缚。这个想法是，在$ b $状态的一个块中，有$ b^{2b} $可以找到每个州的过渡方式，这比通常的$ 2^b $方法更好。然后，您可以存储每个块中的$ log_2 b $信息。 （不是$ 2 log_2 b $

是的...有了$ 2^{1/a} $的块，您可能可以证明$ k_1（x）≤a| x |+c_a $。但是我已经写了太多关于为什么状态的数量不是有效的Kolmogorov复杂性功能的方法。如果您要我详细说明，我会的。

现在大约$ k_2 $

幼稚的描述性语言大致对应于$ k_2（x）= q cdot 2 cdot（ log_2 q + 2）$（对于每个下一个状态，即$ log_2q $ and log_2q $，以及有关写入和终止的详细信息）。

看起来您似乎，我坚信，更好/骗子的方法是授权将“数据”编码到图灵机器中，也许是通过在描述语言中添加二进制标签，该标签表明状态是否是否是状态 数据状态 （那只是写一点并转到下一个状态）或者如果它做其他事情。这样，您可以将$ x $的一点点存储在描述性语言的一点点中。

但是，如果保留相同的$ k_2 $，则可以使用我在上一部分中使用的相同技术来节省一些位，但是我似乎被困在$ k_2（x）≤a| x | x | log | x |+ c $（对于任何$ a> 0 $）..也许小于$ log | x | $，但获得$ o（| x |）$似乎很难。 （我希望它应该是$ | x | $，甚至不是$ o（| x |）$。