前言

一、 物理建模：Malament-Hogarth MH-时空

1. 基础定义

• 计算者（Computer, C）：沿着世界线 $\gamma_C$ 运动。
• 观察者（Observer, O）：沿着世界线 $\gamma_O$ 运动。

2. MH 时空的数学性质

• $d\tau_C = \sqrt{-g_{ab} dx^a dx^b}$ 是计算者的固有时。
• $I^-(p)$ 表示点 $p$ 的过去因果集（Chronological Past）。
• 物理意义：计算者拥有无限的时间去运行程序（$\tau_C \to \infty$），但整条无限长的世界线都位于观察者到达点 $p$ 之前的“过去”。

3. CTC 与 MH 的区别与联系

• MH机器（MH Machine）：利用无限红移面（如Reissner-Nordström黑洞内部或AdS时空），不一定需要时间循环，只需要时间流逝速率的极端差异。
• CTC计算机：利用闭合类时曲线回到过去，让未来的输出成为现在的输入。
• 结合：在某些高级MH模型中，奇异点附近可能自然形成CTC。

二、 计算模型：超图灵机

1. 算法流程

// 观察者 Observer (O)
Procedure Observer_Protocol():
    Launch(Computer, Program_P);
    Timer t = 0;
    While (t < LIMIT): // LIMIT 是物理上的汇合点 p 对应的时间
        if (Receive_Signal("HALT")):
            Return "HALT";
        t += dt;
    // 如果到达点 p 仍未收到信号
    Return "NOT HALT";

// 计算者 Computer (C)
Procedure Computer_Protocol(Program_P):
    Result = Run(Program_P); // 在无限时间内运行
    if (Result == HALTS):
        Send_Signal_To_Observer("HALT"); // 发送光子信号
        Self_Destruct(); // 或者保持在此状态

2. 算术层级

• 对于 $x \in \mathbb{N}$，判定 $x \in H$（停机集）： $H(x) = \begin{cases} 1 & \text{if } \text{Observer receives signal} \\ 0 & \text{if } \text{Observer reaches point } p \end{cases}$

三、 计算能力与复杂度类

1. 时间复杂度的坍缩

• 观察者视角：所有计算，无论标准复杂度是 $O(n^2)$、$O(2^n)$ 还是 $O(\infty)$，其物理消耗时间均为 $O(1)$（即在固有时 $\tau_O$ 界限内）。
• 这导致了什么？ 所有的 递归可枚举问题 (R.E.) 都在 $O(1)$ 时间内可解。

2. CTC 计算机的复杂度类：$P_{CTC}$

• NP 完全问题 (如 3-SAT)：可以在多项式时间内解决。
  • 原理：计算机猜测一个解 $x$，将 $x$ 传送到过去。在过去，验证 $x$ 是否正确。如果正确，不做改变；如果不正确，将 $x$ 修正为 $x'$ 并传送。根据物理的一致性原则（Nature hates paradoxes），系统必然收敛到一个不动点（Fixed Point），即正确的解。
• 算法思路 (Time Travel Sort)： 对于一个求解问题 $f(x)=y$。 $y_{past} = \text{ReadFromFuture}()$ $y_{new} = \text{Compute}(y_{past})$ $\text{SendToPast}(y_{new})$ 物理系统为了避免因果悖论，会强制 $y_{past} = y_{new}$，从而直接给出解。

3. NOI 题目对应的能力跃迁

四、 总结