470
个编辑
更改
跳到导航
跳到搜索
第57行：
第57行： − + 第63行：
第63行： − + − 这里的w等于前式的p，即输出x的程序源代码字符串。+
→柯式复杂度： 复杂度公式的进一步标准化
<math>
<math>
K(s) := C_m(x) = min\{ \lvert \lang M,w \rang \rvert: 通用计算机M在输入w时停机并输出x \}
K(x) := C_m(x) = min\{ \lvert \lang M,w \rang \rvert: 通用计算机M在输入w时停机并输出x \}
</math>
</math>
<math>
<math>
K(s) := C_m(x) = min\{ \lvert \lang M,w \rang \rvert: M(w) = x \}
K(x) := C_m(x) = min\{ \lvert \lang M,w \rang \rvert: M(w) = x \}
</math>
</math>
这里的w等于前式的p，即输出x的程序源代码字符串。x等于前式的s，即待输出的字符串。
在文献<ref name=":5">Jean-Paul Delahaye, Hector Zenil. Towards a stable definition of Kolmogorov-Chaitin complexity. Fundamenta Informaticae XXI 1–15. 2008</ref>中确定柯式复杂度的定义时，使用了两种不同的计算模型：
在文献<ref name=":5">Jean-Paul Delahaye, Hector Zenil. Towards a stable definition of Kolmogorov-Chaitin complexity. Fundamenta Informaticae XXI 1–15. 2008</ref>中确定柯式复杂度的定义时，使用了两种不同的计算模型：