为什么 AI、数学、物理的底层理论，总是诞生在欧美？原因出现在这！

可计算性，是现代 AI、数学、物理最重要却最容易被忽略的思想。从 λ 演算、图灵机、Rule30 到 Claude/GPT，你会发现：真正存在的东西，本质上都是一段能够运行的程序。

"如果一个东西不能被计算，那它在物理宇宙里就不会真正发生。" —— 丘奇–图灵论题的宇宙学版本

"简单的规则也能产生不可约的复杂。你无法抄近路，只能让它跑。" —— Stephen Wolfram，《一种新科学》(2002)

Chapter 0.9 停在了丘奇 1936 年的 λ 演算：一切可计算的东西都是函数。这一章把那句话推到它的宇宙学极限：一切真实发生的东西都是计算。一旦戴上"可计算性"这副眼镜，很多原本要死记硬背的数学约定会突然变得明朗 —— 为什么函数可以随便复合？为什么神经网络输出层非要套一个 softmax？为什么有些问题"原理上"就是算不出来？答案都指向同一件事：数学不是漂浮在空中的符号游戏，而是宇宙这台计算机能真正跑起来的那部分。

这一章和 Chapter 0、0.5、0.7、0.8、0.9、0.95 一起，是本项目"如何学"的元章节群。前面几章教你换视角、读公式、追物理、看高阶函数；这一章给你最后一副眼镜：把每一个数学对象都看成"一段能在某台机器上跑完的程序"，看不能跑完的就画出它的边界。

0.96.1 三个 1936：可计算性被同时发现了三次

物理学里最深刻的时刻，往往是三个人从三个完全不同的方向，走到同一个答案。1936 年就是这样一年 —— 三个人各自定义了"什么叫可计算"，事后发现三套定义计算能力完全相等：

三条路殊途同归，凝成一句 丘奇–图灵论题：

凡"可被任何机械过程计算"的函数，恰好就是这三套模型能计算的函数。

这不是一个能证明的定理（"机械过程"没有形式定义），而是一个关于物理世界的经验断言 —— 八十多年过去，没有任何物理可实现的计算模型超出过这个类。量子计算机也没有：它可能更快，但能算的函数集合一模一样。

这件事的教学意义极大："可计算"不是某种编程语言的偶然特性，而是一个绝对的、语言无关的自然类。就像"能量"跨越力学/电磁/热学是同一个守恒量，"可计算"跨越 λ / 图灵机 / 递归函数是同一个集合。你在 Chapter 0.9 用 Clojure 玩的 lambda，和 CPU 里跑的机器码，是同一个数学对象的两张脸。

# 同一个函数（阶乘），三种 1936 定义各写一遍，输出必然逐位相等
# —— 这就是"丘奇-图灵论题"在你屏幕上的实证
def fact_recursive(n):                    # 哥德尔/克莱尼：原始递归
    return 1 if n == 0 else n * fact_recursive(n - 1)

fact_lambda = (lambda f: (lambda x: x(x))(lambda x: f(lambda *a: x(x)(*a))))(  # 丘奇：Y 组合子
    lambda self: lambda n: 1 if n == 0 else n * self(n - 1))

def fact_turing(n):                       # 图灵：只用读写"纸带"和状态转移（while + 状态）
    tape, acc = n, 1
    while tape > 0:                       # 状态转移，直到停机
        acc, tape = acc * tape, tape - 1
    return acc

assert fact_recursive(6) == fact_lambda(6) == fact_turing(6) == 720

0.96.2 万物皆可计算：从楚泽的"计算空间"到 Wolfram 的计算宇宙

丘奇–图灵论题说的是"函数"。但 20 世纪下半叶有一群人把它推得更狠：如果连宇宙本身的演化都是一种计算呢？

• 1969，康拉德·楚泽（Konrad Zuse，造出世界第一台可编程计算机 Z3 的人）写下《Rechnender Raum》（Calculating Space，计算空间）：宇宙是一台巨大的元胞自动机，物理定律就是它的更新规则，空间的每一格在每一"时钟滴答"按同一条局部规则刷新。这是"数字物理学"的开山之作。
• 1980s–2002，斯蒂芬·沃尔夫勒姆（Stephen Wolfram）用二十年做了一件事：系统地跑遍最简单的程序，看它们能长出什么。结论震撼 —— 一条只看"左邻、自己、右邻"三格、只有 8 行真值表的一维规则（Rule 30），能生成在统计上无法与真随机区分的花纹。简单规则 → 不可约的复杂。他把这写成《A New Kind of Science》(2002)。
• 2020，Wolfram 物理项目：进一步猜测时空、引力、量子力学都从一个"超图不断重写"的计算过程里涌现。

这套世界观的硬核是沃尔夫勒姆的 计算等价原理（Principle of Computational Equivalence）：

几乎所有"看起来不太简单"的过程，在计算能力上都是等价的、图灵完备的。天气、流体、大脑、Rule 30、你的 Python 解释器 —— 复杂度一旦越过一个很低的门槛，就都到顶了，没有谁比谁"更能算"。

由此得到一个反直觉但极其有用的推论 —— 计算不可约性（Computational Irreducibility）：对这类系统，没有比"老老实实一步步跑完"更快的预测捷径。这正好解释了 Chapter 0.8 那个口号"求解留给下一个"为什么是普遍现象：大多数微分方程没有解析解，不是因为我们不够聪明，而是因为宇宙这段程序本身就不可约 —— 你只能积分（reduce），不能跳步。

# Rule 30：一维元胞自动机，8 位规则号 = 00011110 = 30
# 一条"左中右三格 → 中心新值"的查找表，就能从单个 1 长出乱花
def rule30_step(row, rule=30):
    out = []
    for i in range(len(row)):
        left, mid, right = row[i-1], row[i], row[(i+1) % len(row)]
        idx = (left << 2) | (mid << 1) | right     # 3 位邻域 → 0..7
        out.append((rule >> idx) & 1)              # 查规则号的第 idx 位
    return out

row = [0]*40 + [1] + [0]*40                        # 一颗种子
for _ in range(40):
    row = rule30_step(row)                         # 计算不可约：只能一步步跑
# 中心那一列的比特流可以直接当伪随机数发生器 —— Mathematica 真的这么用过

一句话："万物皆可计算"不是玄学，是一个可以在 20 行代码里亲手复现的实验事实。 你不需要相信"宇宙是模拟"，只需要接受一个更弱也更有用的版本：凡是物理上能发生的过程，都落在丘奇–图灵那个圈里 —— 所以用程序去建模它们，原则上永远不会"力所不及"。

0.96.3 为什么函数组合是合理的？—— 因为计算就是组合

中学生第一次见到 \((f\circ g)(x)=f(g(x))\) 时会有个隐隐的疑问：凭什么两个函数拼一起还是个"正当"的函数？ 可计算性给出的答案干净利落：

可计算函数在"复合"下是封闭的 —— 把两段能跑完的程序首尾接起来，结果还是一段能跑完的程序。

这不是约定，是计算的定义本身。图灵机的一步是一次状态转移；一个程序就是转移的顺序复合。哥德尔的递归函数把"复合"直接列为构造可计算函数的五条原语之一。所以 Chapter 0.9 里 Clojure 的 comp、数学里的 \(\circ\)、CPU 里的"下一条指令"，是同一件事：计算 = 把小的可计算步骤组合成大的。函数组合"合理"，是因为它就是计算这个动作的原子。

# 可计算函数在 comp 下封闭：拼起来还能跑完 —— 这就是"函数组合合理"的全部理由
def compose(*fns):                        # comp：数学的 ∘，也是"程序 = 步骤的顺序拼接"
    def composed(x):
        for f in reversed(fns):
            x = f(x)                       # 每一步都停机 ⇒ 整条链停机 ⇒ 结果仍可计算
        return x
    return composed

# 一个神经网络前向传播 = 一串 lambda 的 comp（呼应 Chapter 0.9.4）
layer1 = lambda x: [max(0, v) for v in x]          # ReLU 层
layer2 = lambda x: sum(x)                           # 汇聚层
net = compose(layer2, layer1)                       # net = layer2 ∘ layer1

这也解释了 Chapter 0.9.4 的"神经网络 = lambda 的塔"为什么是合法的：堆 100 层不会跳出可计算的圈，因为复合是可计算类的封闭运算。深度学习之所以能"想堆多深就堆多深"，底层许可证就是这条封闭性。

0.96.4 为什么输出层要套 softmax？—— 让"决策"变成可被梯度计算的东西

这是全章最实用的一节，也是可计算性视角最漂亮的一次兑现。

神经网络最终要做的往往是一个离散决策：这张图是猫还是狗？下一个词是哪一个？最诚实的写法是 argmax —— 挑分数最高的那个类。但 argmax 有一个致命问题：

# argmax 是一个阶梯函数：分数微微变化，输出要么纹丝不动，要么突然跳变
# 它的导数几乎处处为 0，跳变点不可导 —— 梯度无处可流
import numpy as np
def argmax_onehot(scores):
    out = np.zeros_like(scores)
    out[np.argmax(scores)] = 1.0
    return out                            # 台阶：∂out/∂scores = 0 (a.e.)

回忆本项目的主线（Chapter 0.9.4）：训练 = 在权重空间里找 \(\nabla L=0\) 的不动点。而找不动点靠的是梯度下降 —— 一个沿着导数一步步走的计算过程。如果损失对参数的导数处处是 0，这个计算根本跑不起来：没有信号告诉你往哪挪。

于是问题的本质是一句可计算性的话："离散的 argmax 决策，对梯度这台机器来说是不可计算的。" 解决办法不是换机器，而是把决策改写成一个连续、可微、因而可被梯度计算的版本 —— 这就是 softmax：

def softmax(z, tau=1.0):                  # argmax 的"连续松弛"：可微 ⇒ 梯度可计算
    z = np.asarray(z) / tau
    e = np.exp(z - z.max())               # 减最大值只为数值稳定
    return e / e.sum()

# 关键：温度 τ → 0 时，softmax 连续地退化回 argmax（那个不可导的台阶）
z = np.array([2.0, 1.0, 0.1])
for tau in [3.0, 1.0, 0.3, 0.05]:
    print(tau, np.round(softmax(z, tau), 3))
# τ 越小越"尖"，越像 one-hot；τ→0 就是 argmax。softmax = argmax 的可微家族

看穿了这一层，很多"输出层的玄学"就都明朗了，它们全是同一句话的变体 —— 把一个离散/不连续的东西，换成它的可微松弛，好让梯度这台计算机能继续跑：

一句话：连续性和可微性，不是数学家的洁癖，而是"让梯度下降这台计算机能跑起来"的工程前提。 每一处 softmax / sigmoid / softplus，都是在离散决策外面裹一层可微外衣 —— 本质是把一个"梯度算不了"的函数，翻译成一个"梯度算得了"的近亲。这正是可计算性视角对深度学习最实用的一次照亮。

这也回扣了 Chapter 0.5.3 的 \(\log\) 和 \(e^x\)：softmax 里的 \(e^{z}\) 保证了处处可导且恒正，配上归一化就成了概率 —— "可微"和"可当概率"在指数函数这里合二为一，绝非巧合。

0.96.5 计算的边界：有些东西，宇宙自己也算不出来

可计算性视角最深的礼物，是它同时画出了地图的边缘 —— 明确告诉你哪些问题"原理上"无解。这让数学从"我不够聪明"的焦虑，变成"这里是自然律禁区"的清醒。

• 停机问题（图灵 1936）：不存在一个程序，能对任意程序判断它是否会停机。证明就是 Chapter 0.9 的自指/对角线 —— 让程序把自己喂给自己，逼出矛盾（和 Y 组合子、康托对角线、哥德尔句子是同一招）。
• 哥德尔不完备（1931）：任何足够强的形式系统里，都有真但不可证的命题。本质上，"可证"是一种可计算的枚举，而真理超出了任何单一枚举。
• 莱斯定理（Rice 1953）：程序的任何非平凡语义性质（"这段代码会不会崩""它算的是不是排序"）都不可判定。这就是为什么静态分析、类型检查、病毒查杀永远只能近似。

这些"算不出来"的边界，在实践里天天撞见：

# Collatz（3n+1）：规则简单到小学生能懂，却没人知道是否对所有 n 都停机
# —— 这是"计算不可约 + 停机不可判定"活生生的日常样本
def collatz_steps(n, cap=10_000):
    steps = 0
    while n != 1 and steps < cap:         # 只能真跑；没有已知捷径能预言步数
        n = n // 2 if n % 2 == 0 else 3 * n + 1
        steps += 1
    return steps                          # 每个 n 的步数杂乱无章 —— 复杂从简单里涌现

把这份"边界地图"叠到本项目上，很多事情豁然开朗：

一句话：可计算性既是许可证，也是禁令。 它一边说"凡物理能发生的，程序都能建模"（放心大胆写代码去逼近世界），一边说"有些问题没有捷径、甚至没有答案"（别浪费生命找不存在的解析解）。分清这两侧，是把力气花在刀刃上的前提。

0.96.6 可计算性 ↔ 数学 / 深度学习字典

0.96.7 可视化与代码

• 可视化（每个脚本都先给出"能跑起来的程序"，再揭示它对应的数学观念）：
• 三个 1936 殊途同归：λ 演算 / 图灵机 / 递归函数三种实现算同一个函数，输出逐位对齐的对照表
• Rule 30 计算宇宙：从单颗种子长出的乱花图，旁边叠上"中心列比特流"当伪随机数——简单规则里涌现的复杂
• argmax vs softmax：一维分数扫描下，argmax 的台阶（导数处处为 0）与不同温度 softmax 的平滑曲线并排，动画展示 \(\tau\to 0\) 如何连续地退回 argmax
• 可微松弛全家福：step→sigmoid、hard-max→softmax、hinge→softplus 三组"硬 vs 软"并排，标注各自的梯度
• 复合封闭性：把一段程序拆成基本步骤的 comp，可视化"每步都停机 ⇒ 整体停机"
• 计算不可约：Collatz 步数散点图 + Rule 30，展示"没有捷径，只能跑"
• 停机边界：对角线论证的图示，与 Chapter 0.9 的 Y 组合子自指同框
• 代码：ch00_96_computability/
• three_1936.py —— λ / 图灵机 / 递归函数三写阶乘，断言输出相等，画"殊途同归"对照表
• rule30_universe.py —— Rule 30 元胞自动机演化图 + 中心列伪随机比特流可视化
• argmax_vs_softmax.py —— softmax 作为 argmax 的可微松弛，温度扫描动画（本章核心脚本）
• differentiable_relaxations.py —— step/sigmoid、max/softmax、relu/softplus 三组硬软对照及其梯度
• composition_is_computation.py —— 可计算函数在 comp 下封闭：把网络前向写成 lambda 的复合
• computational_irreducibility.py —— Collatz 步数 + Rule 30，"只能一步步跑"的实证
• halting_diagonal.py —— 停机问题的对角线论证图解（呼应 0.9 的自指与 Y 组合子）
• turing_lambda_equiv.clj —— Clojure 版：同一个函数用 λ 与"纸带 + 状态"两种写法，实证丘奇-图灵论题

元教学意义：本章是元章节群的收束。Chapter 0.9 说"一切可计算的都是函数"，本章说"一切真实发生的都是计算"，于是每学一个新数学对象，都自动多问三句： 1. 它是可计算的吗？（能不能写成一段跑得完的程序？） 2. 如果要用梯度去优化它，它可微吗？不可微就找它的软化身（softmax 家族）。 3. 它落在计算不可约 / 不可判定的哪一侧？——决定了该去找闭式解，还是老老实实迭代。

把这三问内化，你就把"数学"彻底翻译成了"在宇宙这台计算机上能跑的程序"——这正是从牛顿的流数走到 PyTorch 自动微分的那条暗线的终点站。