一般递归——μ 算子即图灵能力

上级：recursive-functions

在原始递归之上添加一个构造，你就到达了可计算性的全部——代价是可能不终止。

最小化（

μ 算子） μn. [ f(n, x) = 0 ] = 使 f(n,x)=0 成立的最小 n（且对所有 k<n，f(k,x) 都有定义且非零）；若不存在这样的 n，则无定义。 这是一种无界搜索——一个没有已知上界的 while 循环。

一般（

μ）递归函数 基本函数 + 复合 + 原始递归 + μ。这些就是部分递归函数。

一般递归 = 图灵可计算

μ 递归函数恰好就是图灵可计算（=λ 可定义）的函数——这正是把丘奇–图灵论题精确化的表述。

为什么 μ 是整个跃迁所在

• for → while。 原始递归 = 有界的 for 循环（总会终止，但能力有限，无法便宜地达到 Ackermann 级别的增长速度）。μ = 无界的 while 循环。
• 不终止由此进入。 搜索 μn.[…] 可能永远运行下去，因此 μ 递归函数是部分的——而"这个 μ 搜索会不会停机"这个问题，正是halting-problem本身。
• 这就是那个相变。 有界递归是可判定且全定义的；无界递归是图灵完备且不可判定的。μ 是最小不动点／无界搜索算子——与[[lambda-calculus|Y 组合子]]同等的能力。一切可计算的东西，不多不少，都活在这里。