μ-遞迴函數（mu-recursive functions）
/ mu -> MYOO /
假設你想從零開始定義出每一個「原則上人能用手算出來」的自然數函數。你從幾個極其平凡的基本零件與幾條把它們黏起來的規則出發，然後問：這些能搆到多遠？μ-遞迴函數（mu-recursive functions）就是數學家在 1930 年代給出的答案——一個純算術的可計算性定義，從不提機器、紙帶或步驟，只有由函數建構的函數。
你從三個基本函數出發：零函數（永遠回傳 0）、後繼函數（n 對應到 n+1）、與投影函數（從多個引數中挑出一個）。你用兩條安全的規則把它們組合起來：複合（把若干函數的輸出餵進另一個函數）與原始遞迴（用 f(n) 來定義 f(n+1)，像一個 for 迴圈）。這些產生原始遞迴函數（primitive recursive functions），涵蓋幾乎所有尋常的算術，但結果發現並非「凡可計算者皆在其中」。最後一味材料是 μ-運算子（最小化）：mu m [g(m) = 0] 意思是「搜尋 m = 0, 1, 2, ...，回傳第一個使 g 為零的 m」。這是一個無界搜尋，像一個可能永不停止的 while 迴圈，而它正是把原始遞迴函數提升到完整類別的關鍵。
μ-遞迴函數之所以重要，是因為它定義的類別恰好就是圖靈可計算的函數，卻由一套與機器毫無相似之處的裝置算出。這是邱奇-圖靈論題背後那場大匯聚的又一條線索：圖靈機、λ 演算與 μ-遞迴，三個全然不同的定義，劃出的卻是同一組函數。誠實的微妙之處在 μ-運算子：因為當沒有任何 m 可用時搜尋會永遠跑下去，μ-遞迴函數一般是部分函數（partial，在某些輸入上沒有定義），這恰好對應圖靈機可能永遠迴圈。沒有最小化，你只會得到原始遞迴函數——一個嚴格更小、處處有定義（total）的類別。
加法是原始遞迴的：add(m, 0) = m 且 add(m, n+1) = succ(add(m, n))。但阿克曼函數（Ackermann's function）成長得太快，並非原始遞迴，卻仍是 μ-遞迴的（也是圖靈可計算的）。最小化運算子正是搆到這類函數的工具，代價是可能永遠搜尋下去。
光靠複合與遞迴只給出原始遞迴函數；加入最小化才搆到所有可計算的函數。
μ-運算子的無界搜尋正是使這些函數可能成為部分函數的原因，恰好對應一台會迴圈的圖靈機。原始遞迴函數（不含最小化）處處有定義，但嚴格較弱。