470
个编辑
更改
跳到导航
跳到搜索
第80行：
第80行： − + 第103行：
第103行： + + + + +
→柯式复杂度： 补充计算模型内容。
===柯式复杂度===
===柯式复杂度===
[[柯式复杂度]]是大家公认的复杂度度量方法，在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>
这里的w等于前式的p，即输出x的程序源代码字符串。
这里的w等于前式的p，即输出x的程序源代码字符串。
在文献<ref name=":5">Jean-Paul Delahaye, Hector Zenil. Towards a stable definition of Kolmogorov-Chaitin complexity. Fundamenta Informaticae XXI 1–15. 2008</ref>中确定柯式复杂度的定义时，使用了两种不同的计算模型：
* 确定性图灵机（deterministic Turing machines (TM)）
* 一维元胞自动机（CA）
做了计算性能的比较，实验结果显示两者有着很强的相互关联，而且两者均依靠输出字符串反转和计算对称性来进行分组。
===统计复杂度===
===统计复杂度===