程序检测

程序检测（program checking），计算机科学技术名词，检测一个程序是否计算函数 f 的局部算法。例如，如下协议就是一个程序检测：给定程序 P 和函数 f ，程序检测员 C 是一个多项式时间概率图灵机，它通过和 P 交互来确认 P 是否正确，要求对任给输入 χ ，①如果 P 是计算 f 的正确程序，那么Pr［接受 P ( x )］=1；且②如果 P ( x )≠ f(x) ，那么Pr［接受P(x)]<，这里是指检测员 C 和程序 P 的交互协议。