神谕图灵机（Oracle Machine）

神谕图灵机（Oracle Turing Machine）是一种理想化的抽象计算模型，它在标准图灵机的基础上配备了一个称为神谕（Oracle）的黑盒，能对某个固定集合的成员资格查询立即给出正确答案。

概述

神谕本身不受可计算性限制，甚至可以是不可判定的集合。机器运行时可写下一个查询串放入专用的神谕带，进入询问状态，一步之内便得知该串是否属于神谕集合，再据此继续计算。若神谕为集合A，则称该机为带神谕A的图灵机。

核心特点

• 相对计算：神谕机计算的是相对于A的可计算性，记作对A的图灵归约。
• 图灵归约：若带神谕B的机器能判定A，则称A图灵可归约到B，写作A≤ᴛB。
• 图灵度：图灵归约的等价类构成图灵度，用于度量不可解问题之间的相对难度。
• 相对化：给复杂度类附加神谕后得到相对化版本，如P^A、NP^A。

核心原理

神谕机的核心价值在于相对化技术。贝克、吉尔与索洛维在1975年证明：存在神谕A使P^A等于NP^A，也存在神谕B使P^B不等于NP^B。这说明任何仅靠相对化（对神谕保持成立）的证明方法都无法解决P对NP问题，为该难题划出了方法论障碍。在可计算性中，停机问题的神谕又能定义更高的不可解层级，形成图灵跳跃。

应用场景

神谕机用于定义与研究图灵归约、图灵度和算术层级，是可计算性理论的骨架工具。在复杂度理论中，它服务于多项式层级的定义、相对化障碍分析，以及对各复杂度类相互关系的探讨。

常见问题

问：神谕图灵机能解决停机问题吗？答：普通图灵机不能，但若神谕正好是停机问题集合，则带该神谕的机器可瞬间判定停机；不过它又面临更高一级、自身无法解决的停机问题。

问：相对化为什么对P对NP研究很重要？答：因为存在相互矛盾的神谕结果，任何在相对化下都成立的证明技巧都不足以判定P是否等于NP，提示需要非相对化的新方法。