Turing著名的停机定理说明无法用有限时长的算法判定任意的计算机程序是否停机产生确定输出，这意味着你无法将某些永不停机的程序和其实会在等待时间后才停机的区分开来，人们或可主张这结果意义不大——毕竟运行时间太长的程序和不停机实践上也没啥区别。然而，Rice定理来指出“事情没那么简单”：停机定理中的“停机”可以被替换成任何只跟功能有关的性质，结果一样是不可判定的。
例如：一段程序是否是破坏系统文件的计算机病毒就是不可判定的，跟停机问题是同样意义上的不可判定。使用停机定理来证明计算机“比人类无能”的反AI论者运行杀毒软件时身体可是很诚实——如果你觉得不可判定类问题人比机器更擅长的话，你为什么不自己扒代码而是让另一个计算机程序（杀毒软件）来尝试识别病毒呢？根据Rice定理，对方完全可以具有你的杀毒软件识别不了的破坏功能。
判定病毒为何与判定停机等价？这就要从Rice定理的具体证明说起，我们首先定义何为只跟功能有关的性质：两个程序作用于同一数据若总是产生相同的运行结果（都不停机或都停机在相同输出），则称两者功能相同。一个程序的性质F如果满足以下两点：
（1）程序P具有F当且仅当所有功能相同的程序都具有F。
（2）具有/不具有F的程序各至少存在一个（这排除了所有程序无论功能如何都具有/不具有F的平凡情况）。
则称性质F只跟程序功能有关，或称F是功能性的。显然，“会破坏系统文件”“病毒性”就是功能性的。
Rice定理是这样处理的，假定可以判定任意程序是否具备F，那么对任意程序A都可以通过判定下列构造的A1和A2来求解A是否停机：
A1：每个循环中仿真运行A常数步，在循环末尾检验A是否已进入（仿真的）停机态，否则继续循环，是则清零并执行G1.
A2：每个循环中仿真运行A常数步，在循环末尾检验A是否已进入（仿真的）停机态，否则继续循环，是则清零并执行G2.
G1：任一已知具有F的程序。G2：任一已知不具有F的程序。功能性的定义（2）自然要求了G1和G2都存在，所以上述构造是可行的。
若A停机，则A1与A2功能分别等同于G1与G2，故判定结果应各是具有/不具有F，结果不同。
若A不停机，则A1与A2都会被卡在仿真运行A的无限循环上，因为仿真的停机态永不会被访问。功能相同，故结果相同。
网友评论