470
个编辑
更改
跳到导航
跳到搜索
小第53行：
第53行： − − 柯式复杂度的主要缺点是因为停机问题而导致的不可计算性，针对K式复杂度的主要评论是它高度依赖编程语言的选择。虽然柯式复杂度有上述问题，但仍能揭示计算和模拟的本质。不同的计算模型形成了复杂度的分水岭，智能体沿着复杂度的沟壑通向2050。 − − − 定理：总能找到一个常量E，对于任意的字符串s，两种计算模型U1和U2的柯式复杂度满足： − − <math> − \lvert K_{U_1}(s) - K_{U_2}(s) \rvert < E − </math> − − 即，在误差条件E以内，有程序P能让计算模型U1模拟U2。 第83行：
第72行： + + + + + + + + + +
→柯式复杂度： 调整行文顺序，提高可读性
下标u是对应通用图灵机的代号，U是运行程序p的通用图灵机的实体。
下标u是对应通用图灵机的代号，U是运行程序p的通用图灵机的实体。
为提高通用性，忽略各图灵机之间的差异，将柯氏复杂度定义进一步定义为：
为提高通用性，忽略各图灵机之间的差异，将柯氏复杂度定义进一步定义为：
* 一维元胞自动机（CA）。以并行方式同时更新单个时间步上的所有元胞。
* 一维元胞自动机（CA）。以并行方式同时更新单个时间步上的所有元胞。
做了计算性能的比较，实验结果显示两者有着很强的相互关联，而且两者均可依靠输出字符串反转和计算对称性来进行分组。
做了计算性能的比较，实验结果显示两者有着很强的相互关联，而且两者均可依靠输出字符串反转和计算对称性来进行分组。
柯式复杂度的主要缺点是因为停机问题而导致的不可计算性，针对K式复杂度的主要评论是它高度依赖编程语言的选择。虽然柯式复杂度有上述问题，但仍能揭示计算和模拟的本质。不同的计算模型形成了复杂度的分水岭，智能体沿着复杂度的沟壑通向2050。
定理：总能找到一个常量E，对于任意的字符串s，两种计算模型U1和U2的柯式复杂度满足：
<math>
\lvert K_{U_1}(s) - K_{U_2}(s) \rvert < E
</math>
即，在误差条件E以内，有程序P能让计算模型U1模拟U2。
===统计复杂度===
===统计复杂度===