该函数何时将字符串映射到其无前缀的Kolmogorov复杂性停止？

Question

在 算法随机性和复杂性 从Downey和Hirschfeldt，在第129页上说

美元

其中$ k（ sigma） downarrow $表示$ k $ halts on $ sigma $，$ sigma $是二进制字符串。 $ k $表示没有前缀的Kolmogorov复杂性。

$ k $什么时候停止？我认为这仅在有限数量的输入上停止，因为关于Kolmogorov复杂性的不合同性的经典证明使$ k $的域上的上限为上限。但是，可以选择任意选择$ k $停止的有限输入集（只需要存储源代码中的有限数量的复杂性）即可。

那么这个总和明确吗？换句话说，$ k $的域是否定义好？

Answer 1

我想你是对的; $ k $是无法计算的特定功能。作者可能意味着使用 一些 （任意）近似实施；所以不，如果您是ped的，这似乎不是明确的。您也可以称其为滥用符号。

而是考虑这个：

$ qquad displaystyle forall {m in mathcal {m} _k}。

带有$ MATHCAL {M} _K = {M {所有计算$ k $的亚功能的图灵机。

从本质上讲，这意味着：无论您的实现哪种字符串都可以计算kolmogorov的复杂性，但界限均可保持。

---

正如卡尔在评论中指出的那样，符号与停止或计算无关，因为$ k $是不可计算的。阅读$ sum_ {k（ sigma）！ downarrow} $作为$ k $的域上的sum范围。