470
个编辑
更改
→柯式复杂度： 计算和模拟的本质
下标u是对应通用图灵机的代号，U是运行程序p的通用图灵机的实体。
下标u是对应通用图灵机的代号，U是运行程序p的通用图灵机的实体。
柯式复杂度的主要缺点是因为停机问题而导致的不可计算性，针对K式复杂度的主要评论是它高度依赖编程语言的选择。虽然柯式复杂度有上述问题，但仍能揭示计算和模拟的本质。不同的计算模型形成了复杂度的分水岭，智能体沿着复杂度的沟壑通向2050。
定理：总能找到一个常量E，对于任意的字符串s，两种计算模型的何式复杂度满足：
即，在误差条件E以内，有程序P能让计算模型U1模拟U2。
为提高通用性，忽略各图灵机之间的差异，将柯氏复杂度定义进一步定义为：
为提高通用性，忽略各图灵机之间的差异，将柯氏复杂度定义进一步定义为：