μ 递归函数（μ-Recursive Function）

μ 递归函数（μ-Recursive Function，又称一般递归函数）是数理逻辑与可计算性理论中定义可计算函数的一种方式。它从少数基本函数出发，通过若干构造算子（尤其是μ最小化算子）生成全部可计算的数论函数。

概述

该体系以自然数上的函数为对象。基本函数包括零函数、后继函数和投影函数，再允许用复合、原始递归两种操作组合，构成原始递归函数类。在此基础上加入μ算子（最小化算子），便得到更广的μ递归函数类。丘奇-图灵论题指出，这一类恰与图灵可计算函数、λ可定义函数完全一致。

核心原理

μ递归函数的构造依赖以下要素：

• 基本函数：零函数恒返回0，后继函数加一，投影函数取出参数中某一分量。
• 复合：将若干函数的输出作为另一函数的输入。
• 原始递归：按自然数归纳定义函数，处理有界循环。
• μ最小化：对给定函数寻找使其取零的最小自变量，对应无界搜索，可能不停机。

μ算子是关键所在。原始递归函数总是全函数（对所有输入都有定义且停机），但无法表达阿克曼函数等增长极快者。μ算子引入了无界搜索，使函数可能成为偏函数——某些输入下永不停机，这恰对应图灵机可能不停机的本质。

应用场景

μ递归函数主要用于奠定可计算性的数学基础，为丘奇-图灵论题提供一个纯算术、无需机器模型的等价刻画。它在数理逻辑、证明论、递归论教学中作为标准工具，也用于比较不同可计算性形式体系之间的等价性。

常见问题

问：原始递归函数和μ递归函数差别在哪？答：原始递归函数都是全函数、必定停机，但表达力有限；μ递归函数因引入无界搜索的μ算子，能表达全部可计算函数，代价是可能对某些输入不停机。

问：μ递归函数和图灵机等价意味着什么？答：意味着两种看似不同的可计算性定义刻画的是同一类函数，为丘奇-图灵论题提供了有力佐证，说明可计算这一概念是稳健的。