1 背景与动机
1.1 经典可计算性理论的局限
经典可计算性理论——由图灵、丘奇、哥德尔等人在20世纪30年代奠定——确立了“可计算函数”的严格数学定义。图灵机模型为“算法”提供了精确的形式化描述，而丘奇-图灵论题则认为，任何直观上可有效计算的函数都能由图灵机计算。然而，经典理论存在一个根本局限：它只研究绝对意义上可计算的问题，即完全不依赖外部信息就能被图灵机解决的那些问题。但在数学和实践中，许多问题天然地需要借助额外信息（例如另一个问题的解）才能求解。例如，判断一个数是否为某个已知非递归集合的元素，显然需要访问该集合的信息。经典框架无法系统刻画这种“借助外部资源”的计算过程，从而限制了我们对问题难度相对比较的理解。
1.2 相对化思想的历史渊源
1.2.1 图灵1939年论文中的预言机概念
相对化思想最早可追溯到图灵1939年的博士论文《基于序数的逻辑系统》。在那篇开创性论文中，图灵引入了“预言机”（oracle machine）的概念：一台图灵机能够从某个外部“预言”中即时获取关于特定集合成员关系的信息。预言被想象为一个黑箱，图灵机可以在计算过程中向它提问（例如“数n属于集合A吗？”），并立即收到答案。这种机制允许图灵机“借用”本不可计算的信息，从而定义出一类新的可计算函数，即相对于给定预言可计算的函数。图灵明确指出，预言机不是具体的物理设备，而是一种数学抽象，用于研究逻辑系统与可证明性之间的关系。这一构想为后续的相对化理论奠定了基石。
1.2.2 波斯特问题与归约的提出
20世纪40年代，埃米尔·波斯特深入思考了递归不可解度的结构问题。他提出了著名的“波斯特问题”：是否存在一个非递归的递归可枚举集合，其图灵度严格介于递归度和完备递归可枚举度之间？要解决这一问题，首先需要一种比较不同集合计算难度的方法。波斯特与图灵几乎同时独立地提出了“归约”概念：如果给定集合B作为预言，集合A可以被计算出来，则称A可归约到B（记为A ≤_T B）。这种归约关系（后来被称为图灵归约）可以将所有集合划分为等价类，每个等价类称为一个图灵度。波斯特问题直接推动了图灵度结构的研究，并促使相对化思想成为递归论的核心工具。虽然波斯特原问题后来通过优先方法得到肯定解决（由穆奇尼克和弗里德伯格独立完成），但相对化框架本身早已超越了原始问题的范畴。
2 基本定义
2.1 预言机图灵机
预言机图灵机是一种扩展的图灵机模型。除了标准的有限状态控制器、纸带和读写头之外，它还配备了一个“预言带”和一个“预言询问状态”。预言带用于存储向预言提出的问题（通常是一个自然数的编码），而预言则在机器进入询问状态后，在“回答带”上返回一个比特（0表示“否”，1表示“是”），指示该数是否属于预言的集合。预言机的工作流程如下：机器正常运行，直到它进入询问状态；此时，机器将预言带上当前的内容视为一个数字n，查询外部预言集合A；如果n∈A，则在回答带上写入1，否则写入0；然后机器从指定状态继续执行。回答的获取被视为一个原子操作，不消耗额外的步数（从抽象角度而言）。预言机可以无限次询问，但每次询问必须等待回答后才能继续。预言机的行为完全由初始状态、转移函数以及预言的特性决定。需要注意的是，预言本身不必是递归的，甚至不必是集合论意义上的“函数”——它只是作为一个被动的信息源存在。
2.2 相对化可计算函数与集合
2.2.1 计算于预言机A的函数
令A为任意自然数子集。一个函数f: ℕ → ℕ被称为相对于A可计算的（记为f ≤_T A或f是A-可计算的），如果存在一台预言机图灵机M，使得当M以预言集合A运行时，对于任何输入x，M经过有限步后停机，并在输出带上留下f(x)。类似地，一个集合S ⊆ ℕ被称为相对于A可计算的，如果其特征函数是A-可计算的。当A本身是递归集时，相对于A的可计算性等同于经典可计算性，因为预言信息可以简单地被算法模拟。但对于非递归的A，相对化可计算函数集合严格包含经典可计算函数集合。例如，取A为停机问题集合K，那么相对于K，我们就能判定原停机问题的解——但依旧存在相对于K仍然不可判定的问题（如K的跳跃）。
2.2.2 枚举相对化与局部可计算性
相对化概念还可以拓展到枚举情形。一个集合S被称为相对于A递归可枚举（记为S是RE.A的），如果存在一台预言机M（以A为预言），使得M可以枚举S的所有元素。更精确地说，存在一个A-可计算函数f，使得S是f的值域。枚举相对化允许我们研究那些不能直接判定成员关系，但能“列出”其中元素的问题。与经典递归可枚举性类似，RE.A集合恰好是A-可计算函数的半可判定类。此外，局部可计算性（local computability）强调相对化只作用于计算过程的特定部分；例如，在有限序数层次上的相对化往往只涉及有限次的预言查询，从而形成严格的分层结构。
2.3 图灵归约与图灵等价
2.3.1 归约的传递性
图灵归约A ≤_T B（读作“A图灵可归约于B”）定义如上：存在一台以B为预言的图灵机，能计算A的特征函数。这一关系具有传递性：如果A ≤_T B且B ≤_T C，那么A ≤_T C。证明思路是通过组合预言机：将计算A的机器中每次对B的询问，替换为计算B的机器（以C为预言）的模拟。传递性使得图灵归约构成一个预序，进而可以定义等价类。注意，经典递归可归约（如m-归约）也满足传递性，但图灵归约更灵活——因为它允许多次询问，且询问可以依赖于之前的结果。
2.3.2 图灵度（Turing Degree）的概念
基于图灵归约的等价关系定义为：A ≡_T B 当且仅当 A ≤_T B 且 B ≤_T A。每个等价类称为一个图灵度（Turing degree）。全体图灵度构成的集合记为𝒟。图灵度之间由偏序关系：deg(A) ≤ deg(B) 如果A ≤_T B。最小的图灵度是递归度（即所有递归集合的度，记为0）。图灵度结构具有丰富的代数性质：任意两个度有上确界（即联合度），但并非每对度都有下确界；它构成一个上半格（upper semilattice）。图灵度的研究是整个递归论的核心领域之一，它揭示了可计算性问题在连续谱上的分层。典型的图灵度包括递归度0、完备递归可枚举度0'（停机问题的度）、跳跃算子定义的更高层次（0'', 0'''...）以及介于它们之间的众多中间度。
3 核心结构
3.1 图灵度的基本性质
3.1.1 最小度与递归度
在所有图灵度中，递归度（记为0）是唯一的最小元。它由所有递归集（即经典可计算集）构成。对任何图灵度d，都有0 ≤ d，因为任何递归集（包括空集）都可以在不使用预言的情况下被计算。有趣的是，存在无限多条链从0向上延伸，且每个非递归度之上仍有更高度的集合。图灵度结构没有最大元：对于任意集合A，总存在比它更难的集合（例如A的跳跃A'）。因此，图灵度构成一个无最大元的偏序上半格。
3.1.2 上界、下界与格结构
对于两个图灵度a和b，它们的最小上界（即联合度）a ∪ b总是存在：取集合A（度a）和B（度b）的某种配对，例如{A与B的编码对}，其图灵度就是a ∪ b。具体构造为A⊕B = {2n : n∈A} ∪ {2n+1 : n∈B}。然而，并非每对图灵度都有下确界（最大下界）。事实上，存在很多“无下界对”（即没有共同下界），也有存在下界的对。图灵度结构的这种不完全性（即不是格，只是上半格）是一个重要特征。此外，图灵度还呈现稠密性：任何两个可比较的度之间总存在无限多个中间度（这由斯佩克特定理和后续结果建立）。这些性质使得对图灵度序结构的研究成为递归论中最富有挑战性的分支之一。
3.2 跳跃算子
3.2.1 跳跃的定义（A'）
跳跃算子（jump operator）是图灵度结构中的关键操作。对于任意集合A，定义其跳跃A'为“相对于A的停机问题”：即所有带有预言A的图灵机在输入某个编码时是否停机的集合。形式上，令W_e^A表示第e个A-预言机枚举的集合（即其停止集），则A' = {e : 第e个A-预言机在输入e时停机}。跳跃算子将图灵度严格提升：A <_T A'且A'的图灵度严格大于A的图灵度。例如，空集的跳跃∅'就是经典的停机问题K。跳跃算子可以理解为一种“不可判定性生成器”，它对任何集合都产生一个更难的问题。
3.2.2 跳跃的迭代与算术层次
3.2.2.1 有限跳跃与ω-跳跃
跳跃算子可以反复迭代：A^(n)表示对A应用n次跳跃。例如，A'' = (A')'，依此类推。经典的算术层次可以用跳跃来刻画：对于n≥1，空集∅的n次跳跃∅^(n)恰好是Σ_n完备（或Π_n完备）的集合。因此，跳跃迭代自然地将图灵度与算术层级对应起来：∅对应算术层次中最简单的（递归）问题，∅'对应停机问题（Π_1完备），∅''对应二次停机问题（Σ_2完备），等等。更一般地，对于极限序数λ，可以定义λ-跳跃（如ω-跳跃）为所有有限次跳跃的某种极限。这导致了超算术层次（hyperarithmetical hierarchy）的出现，其中递归序数（countable ordinals）用于索引跳跃的迭代，从而构建出一个跨越所有算术及其之上层次的可计算性谱系。
3.2.2.2 跳跃定理与不动点
跳跃定理（jump inversion theorem）是递归论中的重要结果：对任何度a ≥ 0'，都存在一个度d使得d' = a。换言之，任何高于停机问题的图灵度，都可以是某个集合的跳跃。这展示了跳跃算子的“满射”性，但仅对足够高的度有效。此外，还存在不动点现象：可以构造集合A使得A' ≡_T A，但这样的A必然具有递归度（因为如果A' ≤_T A，则A为递归，由弗里德伯格定理）。更一般的跳跃不动点研究涉及超算术层次中的固定点；例如，存在一个非递归的集合A使得A' ≡_T A''，但这种情况仅限于特定层次。跳跃算子还与其他概念（如低度、高度、广义高阶递归）紧密交织，形成了丰富的递归论分支。
3.3 相对化递归可枚举性
3.3.1 递归可枚举于A（RE.A）
集合S被称为递归可枚举于A（记为S是RE.A的），如果存在一个以A为预言的图灵机，当输入一个自然数时，机器可判定是否停机（或等价地，可以枚举S中的所有元素）。RE.A集合恰好是那些可以由A-可计算函数值域描述的集合。经典递归可枚举集合（RE）就是RE.∅。RE.A类具有类似于经典RE的性质：它是封闭于并、交、笛卡尔积的；存在A-通用RE.A集合（即相对于A的停机问题A'，它本身是RE.A的且A-完备）；存在RE.A的不可判定性定理（如赖斯定理的相对化版本）。此外，RE.A与RE.B的比较可反映图灵度的关系：如果A ≤_T B，那么RE.A ⊆ RE.B；反之则不一定成立。
3.3.2 波斯特定理的相对化版本
波斯特定理（Post's theorem）将算术层次与跳跃联系起来，其相对化版本表述为：对于任意集合A和任意n≥1，一个集合B是Σ_n^A（即相对于A的Σ_n公式可定义）当且仅当B是RE.A^(n-1)（即递归可枚举于A的n-1次跳跃）。这里A^(n-1)表示对A应用n-1次跳跃。特别是，Σ_1^A就是RE.A（由定义）。相对化波斯特定理为我们提供了一种用图灵度刻画算术复杂度的工具：每个算术层次的相对化版本恰好对应于某个特定跳跃的RE类。例如，某个集合是Σ_2^A当且仅当它是RE.A'。这一结果的重要性在于，它将模型论中的可定义性层次与递归论中的可计算性层次统一起来，为在集合论和模型理论中应用相对化方法铺平了道路。
4 高级主题与应用
4.1 相对化与算术层级
4.1.1 相对化Σ_n与Π_n公式
相对化算术层级将经典算术层级（Σ_n, Π_n）扩展为相对于给定集合A的版本。一个公式称为Σ_n^A，如果它在A的参数中允许使用A作为谓词，并且公式的量化前缀是n次交替存在/全称量词，起始于存在量词。类似地定义Π_n^A（起始于全称量词）。例如，一个性质是Σ_2^A，如果它可以表达为“存在x使得对所有y，某个关于A的可判定条件成立”。相对化层级与图灵度紧密联系：Σ_1^A公式定义的关系恰好是RE.A（即A-可枚举类），而Π_1^A公式定义的关系是co-RE.A。相对化算术层次中的完备性概念（如Σ_n^A-完备集）可以通过跳跃来刻画：Σ_n^A-完备集恰好是A^(n)本身（或与A^(n)图灵等价）。这一理论在描述集合论和较高阶算术中有着重要应用。
4.1.2 超算术层次与递归序数
超算术层次（hyperarithmetical hierarchy）是对算术层次的进一步扩展，它允许沿着可数序数（递归序数）迭代跳跃。一个集合是超算术的，如果它可由某个递归序数索引的跳跃层次中的任意一层定义。更精确地，对于递归序数α，定义H(α)为从空集开始经α次跳跃（包括极限步骤）得到的集合。超算术集合恰好是那些可归约到某个H(α)的集合。相对化版本的超算术层次涉及相对于给定集合A的类似构造。这一理论提供了将可计算性概念推广到可数序数级的手段，并在证明理论（例如算术超限递归）和描述集合论（如解析集的分类）中发挥核心作用。值得注意的是，超算术归约（或称超算术可归约性）比图灵归约更强，它能捕捉到递归序数意义上的信息提取。
4.2 相对化在集合论中的体现
4.2.1 可构成集合L中的相对化
在集合论中，可构成集合（Gödel的L模型）通过可定义性分层构建。相对化在L模型中表现为：给定一个集合A，可构造L[A]（带谓词A的可构成宇宙）。L[A]是所有可以通过使用A作为参数，在可定义性操作中迭代得到的集合构成的模型。这一相对化过程不仅保留了ZFC公理，还使得A变得可定义（或至少是某种程度的可构造）。在L[A]中，相对化可计算性概念与经典递归论类似，但此时预言机所对应的集合可能是任意集合（不仅是自然数子集）。例如，定义“相对于A可计算的”在L[A]语境中就是指在L[A]内部可以被某个带有A的图灵机模拟的过程。这一框架用于研究大基数公理和公理的相对一致性，特别是用于证明某些独立性结果（如选择公理相对于ZF的独立性）。
4.2.2 强制法与相对化独立性结果
强制法（forcing）是科恩创立的用于证明独立性结果的技术。在强制法中，相对化扮演了关键角色：给定一个模型M（通常可数是ZF的模型）和一个偏序集P（“条件”），构造一个M的扩张M[G]（其中G是M上的P-生成滤），使得M[G]中满足某些额外公理。在这一过程中，相对化可计算性用于分析M中的哪些对象在扩张中具有某种可定义性程度。例如，科恩利用强制法证明了连续统假设（CH）独立于ZFC，其中通过添加足够多的实数产生一个模型，使得新实数的图灵度呈现非常复杂的结构。相对化可计算性在此处提供了区分不同实数“难度”的精细工具。近年来，递归论强制法（recursion-theoretic forcing）进一步发展，直接使用图灵度条件构造具有特定度性质的集合（如最小度、高度等），而这些方法建立在相对化可计算性基础之上。
4.3 计算复杂性中的相对化
4.3.1 随机预言机与分离结果
在计算复杂性理论中，相对化思想被用来研究复杂性类之间的关系。随机预言机是指一个以均匀概率随机选择的预言集合。贝克尔-吉尔定理（BGS定理）开创性地证明了：存在一个随机预言机使得P=NP成立，同时也存在另一个随机预言机使得P≠NP成立。这种相对化分离表明，经典的P与NP问题不能通过纯相对化的方法解决，因为预言机的存在会改变复杂性类的包含关系。更一般地，随机预言机结果揭示出复杂性类之间的某些性质（如多项式层级是否塌缩）依赖于预言机的信息，从而提出了对绝对证明方法的需求（如非相对化证明）。相对化方法在分离复杂性类（如PSPACE和PTIME）中也常常被使用，例如利用对角化构造预言机使得某些类分离。
4.3.2 P与NP的相对化争论
P与NP问题的相对化版本（即是否存在预言机使得P^A = NP^A或P^A ≠ NP^A）是复杂性理论中一个经典议题。如前所述，存在预言机分别使等式成立或不等成立，这意味着任何证明P=NP或P≠NP的论证都必须使用非相对化的技术（不能仅通过对角化或模拟）。这一认识在20世纪70年代引发了关于“相对化障碍”的深入讨论。相对化悖论也出现在其他类上：例如，Baker、Gill和Solovay证明了存在预言机使得P=NP，但NL不等于P等其他情况。这些结果推动了“非相对化证明”方法的发展，如算术化证明（arithmetization）和交互式证明系统（IP=PSPACE等）。尽管如此，相对化在复杂性理论中仍是一个重要工具，用于探索类之间隐藏的结构并揭示分离的障碍。
5 相关概念与拓展
5.1 多项子集归约（m-归约、1-归约）的相对化
除了图灵归约，还有很多其他归约概念，它们可以在相对化框架中定义。m-归约（多一归约）要求将问题A的实例映射为问题B的实例，且答案一致；其相对化版本为A ≤_m^C B（即存在一个C-可计算函数f，使得对所有n，n∈A ⇔ f(n)∈B）。1-归约（同单一归约）更为严格，要求f是单射。相对化m-归约与图灵归约相比更“弱”（即更严格），因为它们限制了信息获取的方式。在相对化语境下，这些归约对应的度结构（如m-度）也具有类似上半格的性质，但其结构比图灵度更精细。例如，存在m-度不等的集合可能具有相等的图灵度。这些概念在枚举归约（enumeration reducibility）中也有对应的相对化版本。
5.2 超算术归约与半度结构
超算术归约（hyperarithmetical reducibility）是图灵归约的加强版，它允许通过超算术层次中的可数步递归获得信息。一个集合A超算术可归约到B（记为A ≤_h B），如果存在某个递归序数α使得A是B^(α)可计算的（即相对于B的α次跳跃）。超算术归约产生的等价类称为超算术度，它们构成一个比图灵度更细致的结构。半度结构（semi-degree）是递归可枚举度（即RE度）的一种特殊情形：它包含所有递归可枚举集合（相对于某个基集）的图灵度。半度结构在递归论中具有丰富的代数性质，例如存在最小递归可枚举度（即0'本身），以及存在多种中间度等。超算术归约与半度结构相结合，用于研究递归序数层次上的可定义性与计算性。
5.3 相对化可计算性与连续性
相对化可计算性与拓扑学中的连续性概念有着微妙关联。在Baire空间（ω^ω）中，一个算子F: ω^ω → ω^ω是连续的当且仅当它在每个输入上的值只依赖于输入的有限前缀。这种局部性类似于预言机计算的“有限查询”性质：对于任何图灵归约，给定预言A，一台预言机只需要在计算过程中查询A的有限多个点就能决定输出的任何有限段。因此，图灵可计算性可以被视为一种特殊的连续性，其中查询模式由算法决定。更一般地，相对化可计算性与有效拓扑（effective topology）有紧密关系，形成了有效描述集合论的基础。例如，“相对化可计算函数”恰好对应着Baire空间中的“有效连续函数”。这一视角使得递归论与拓扑学、分析学之间架起桥梁，并在可计算分析（computable analysis）中得到了广泛应用。