470
个编辑
更改
小第46行：
第46行： − + 第52行：
第52行： − 下标u是对应图灵机的代号。+
→柯式复杂度： 对通用图灵机代号u和实体U进行说明
===柯式复杂度===
===柯式复杂度===
[[柯式复杂度]]是大家普遍公认的复杂度度量方法，在Jean-Paul Delahaye和Hector Zenil对复杂系统量化方法研究的工作中<ref name=":5">Jean-Paul Delahaye, Hector Zenil. Towards a stable definition of Kolmogorov-Chaitin complexity. Fundamenta Informaticae XXI 1–15. 2008</ref>，认为最天然的计算设备的模型需要有一定的表达能力，并定义是一个字符串s对于通用图灵机U的'''柯尔莫哥洛夫-蔡汀(Kolmogorov-Chaitin)复杂度'''<math>K_{u}(s)</math>为输出该字符串s的最短程序p的二进制长度。
[[柯式复杂度]]是大家普遍公认的复杂度度量方法，在Jean-Paul Delahaye和Hector Zenil对复杂系统量化方法研究的工作中<ref name=":5">Jean-Paul Delahaye, Hector Zenil. Towards a stable definition of Kolmogorov-Chaitin complexity. Fundamenta Informaticae XXI 1–15. 2008</ref>，认为最天然的计算设备的模型需要有一定的表达能力，并定义一个字符串s对于通用图灵机U的'''柯尔莫哥洛夫-蔡汀(Kolmogorov-Chaitin)复杂度'''<math>K_{u}(s)</math>为输出该字符串s的最短程序p的二进制长度。
<math>
<math>
</math>
</math>
下标u是对应通用图灵机的代号，U是运行程序p的通用图灵机的实体。
柯式复杂度的主要缺点是因为停机问题而导致的不可计算性，针对K式复杂度的主要评论是它高度依赖编程语言的选择。
柯式复杂度的主要缺点是因为停机问题而导致的不可计算性，针对K式复杂度的主要评论是它高度依赖编程语言的选择。