为什么革命机叫预言机?

预言机 2024-01-25 33
在计算复杂度理论与可计算性理论中,预言机(英语:oracle machine),又称革命机,是一种抽象电脑,用来研究决定型问题。预言机可以被视为一个具有额外黑盒子(即预言者)的图灵机,该黑盒子能够在单一运算中解答特定问题。

预言者可以解答的问题范围非常广泛,可以涵盖任何复杂度类内的问题,甚至可以处理不可判定问题,如停机问题。预言机的引入使得理论计算模型更加丰富和灵活,有助于深入研究决定性问题的本质和复杂性。这对于推动计算机科学和数学领域的进步具有重要意义。

相关推荐