Μ算子

**μ 算子**（英語：μ operator）或者**極小化算子**（minimization operator），**無界尋找算子**（unbounded search operator）在可計算性理論中，被用來尋找給定性質下的最小自然數。

## 定義

R( y, x1 , . . ., xk ) 是固定的在自然數上的 _k+1_ 元關係。低洼「μy」，在無界和有界形式下，都是從自然數 {0, 1, 2, . . .} 到自然數的「數論函數」。但是，「μy」包含在謂詞被滿第三代
有界 μ 算子最早出現在 Kleene（1952 年）書中的「第 4 章原始遞迴函數，§45 謂詞，質因子表示」中：大幅度

　
: 「μyy<zR (y)。最小的 y <z 使得 R (y)，如果 (Ey)y<z R (y)；否則 z」。 (p.225)

Kleene 提示說對變數 y 的值域的 6 個不等式限制中任何一個都是允許的，它們是 y <z, y ≤ z, w < y < z, w < y ≤ z, w ≤ y < z, w ≤ y ≤ z。「當指示的值域不包含 y 使得 R (y) [為「真」] 的時候，「μy」表達式的值是值域的基數」（p. 226）；這是預設「z」出現在上述定義中的原因。如下面要證明的，有界 μ 算子「μyy<z」是憑藉兩個原始遞迴函數有限和 Σ 與有限積 Π，「做測試」的一個謂詞函數，和轉換 {t, f} 到 {0, 1} 的表示函數而定義的。

在「第 6 章一般遞迴函數」中，Kleene 以如下方式定義了在變數 y 上的無界 μ 算子，

　
: 「（Ey）μyR (y) = {最小的（自然數）y 使得 R (y) }」 (p. 279)，這裡的 「（Ey）」 意味著「存在一個 y 使得 ...」

在這個實例 R 自身內，或它的表示函數，在它被滿足的時候得出 0（就是得出_真_）；這個函數接著得出數 y。在 y 上不存在上界，所以在它的定義中不出現不等式。

對於一個給定 R (y) 無界 μ 算子 μyR (y)（注意不要求「（Ey）」）可以導致全函數或偏函數。Kleene 以不同的方式寫這個潛在的偏函數 (cf. p. 317):

　
: εyR(x, y) =

　
: * 最小的 y 使得 R (x,y) [為真]，如果 (Ey) R (x,y)
* 0 否則的話。

## 性質

(i) 在原始遞迴函數的上下文中，這裡的 μ 算子的尋找變數 y 是有界的，也就是在下面公式中的 y<z，如果謂詞 R 是原始遞迴的（Kleene Proof #E p. 228），則

　
: μyy<z R( y, x1,..., xn ) 是原始遞迴函數。

(ii) 在（全）遞迴函數的上下文中：這裡的尋找變數是無界的，但是保證對全遞迴謂詞 R 的參數的所有值 xi 都存在，

　
: (x1), ..., (xn) (Ey) R( y, xi, ... xn ) 蘊涵了 μyR (y, xi, ... xn) 是全遞迴函數。

　
: 這裡的 (xi) 意味著「對於所有 xi」而 Ey 意味著「存在著至少一個 y 的值使得」（cf Kleene (1952) p. 279.）。

則五個原始遞迴算子加上無界但完全 μ 算子給出了 Kleene 所稱的「一般」遞迴函數（就是由六個遞迴函數定義的全函數）。

(iii) 在偏遞迴函數的上下文中：假設關係 _R_ 成立，若且唯若一個偏序遞迴函數收斂於零。並假設這個偏遞迴函數收斂（到某個東西不一定為零）只要 $\mu yR(y,x_{1},\ldots ,x_{k})$ 有定義而且 _y_ 是 $\mu yR(y,x_{1},\ldots ,x_{k})$ 或更小。則函數 $\mu yR(y,x_{1},\ldots ,x_{k})$ 也是偏遞迴函數。

μ 算子用在可計算函數作為 μ 遞迴函數的特徵化中。

## 例子

### 例子 #1：有界 μ 算子是原始遞迴函數

　
: 在下文中，為了節省空間使用粗體字 **x** 來表示字串 xi, . . ., xn。

有界 μ 算子可以非常簡單的用兩個原始遞迴函數（簡寫為 "prf"）來表達，它們是項的積 Π 與項的和 Σ，還被用來定義 CASE 函數 (cf Kleene #B page 224)。（按照需要，變數的任何界限比如 s≤t 或 t<z 或 5<x<17 等都是適當的）。例如：

　
: * Πs≤t fs (**x**, s) = f0(**x**, 0) \* f1(**x**, 1) \* . . . \* ft(**x**, t)
* Σt<z gt ( **x**, t ) = g0( **x**, 0 ) + g1(**x**, 1 ) + . . . + gz-1(**x**, z-1 )

我們先要介入叫做謂詞 R 的表示函數的一個函數 ψ。函數 ψ 定義為從輸入（t= "真", f="假"）到輸出 (0, 1) 的對映（**注意次序！**）。在這種情況下給 ψ 的輸入 {t, f} 來自 R 的輸出：

　
: * ψ( R = t ) = 0
* ψ( R = f ) = 1

Kleene 展示了 μyy<z R (y) 的如下定義；我們看到積函數 Π 充當了布林 AND 算子，而和函數 Σ 充當布林 OR 算子，不同的是它生成 {Σ≠0, Σ=0} 而不是 {1, 0}:

　
: μy y<z R(y) = Σt<z Πs≤t ψ( R( **x** ,t ,s )) =

* [ ψ( **x**, 0, 0 ) ] **+**
* [ ψ( **x**, 1, 0 ) \* ψ( **x**, 1, 1 ) ] **+**
* [ ψ( **x**, 2, 0 ) \* ψ( **x**, 2, 1 ) \* ψ( **x**, 2, 2 ) ] **+**
* . . . . . . **+**
* [ ψ( **x**, z-1, 0 ) \* ψ( **x**, z-1, 1 ) \* ψ( **x**, z-1, 2 ) + . . . + ψ ( **x**, z-1, z-1 ) ]

　
: 和 Σ 實際上是帶有基礎步驟 Σ(**x**, 0) = 0 和歸納步驟 Σ(**x**, y+1 ) = Σ( **x**, y ) + Π( **x**, y ) 的原始遞迴。積 Π 是帶有基礎步驟 Π( **x**, 0 ) = ψ( **x**, 0 ) 和歸納步驟 Π( **x**, y+1 ) = Π( **x**, y )\*ψ( **x**, y+1 ) 的原始遞迴。

通過 Kleene 給出例子很容易理解這個等式。他只為指示函數 ψ（R (y)）構建了表格。他用表示函數 χ(y) 簡寫 ψ( **x**, y ): 

### 例子 #2：無界 μ 算子不是原始遞迴函數

無界 μ 算子 -- 函數 μy -- 經常定義於教科書中。但是讀者可能奇怪於為什麼無界 μ 算子尋找生成零而不是某個其他自然數的函數 R (**x**, y) -- 現代教科書沒有給出原因。

　
: 在註腳中 Minsky 的確允許他的算子在內部過程生成一個對參數 "k" 的匹配的時候終止；這個例子也是有用的因為它展示了另一個作者的格式：

　
: " For μt[ φ(t) = k ] "(p. 210)

使用零的原因是無界算子 μy 將依據其索引 y 允許隨著 μ 算子的尋找而增長的函數 "積" Π 來定義。如上述例子提及的，一串數 ψ(**x**, 0) \*, . . ., \* ψ(**x**, y) 的積 Π x<y 生成零，只要它的成員 ψ(**x**, i) 之一為零：

　
: Πs<y = ψ(**x**, 0) \* , . . ., \* ψ(**x**, y) = 0

如果任何 ψ(**x**, i)=0 這裡的 0 ≤ i ≤ s。所以 Π 充當了布林 AND。

函數 μy 生成作為 "輸出" 的一個單一的自然數 y = {0, 1, 2, 3 ...}。但是，在算子內可能出現一對「情況」之一：(a) "數論函數" χ 生成一個自然數，或 (b) "謂詞" 生成 {t= true, f = false}。（在偏遞迴函數的上下文中 Kleene 後來允許第三種結果："μ = 不可判定", pp. 332ff）。

Kleene 分解他的無界 μ 算子定義來處理這兩種情況 (a) 和 (b)。對於情況 (b)，在謂詞 R (**x**, y) 可以參於積 Π 的算術運算之前，它的輸出 {t, f} 必須首先被它的「表示函數」χ 運算生成 {0, 1}。而對於情況 (a)，如果要使用一個定義，則「數論函數」 χ 必須生成零來滿足 μ 算子。通過這個問題的確立，他展示了一個單一的 "Proof III"，任何類型 (a) 或 (b) 與五個原始遞迴函數一起產生（全）遞迴函數 ... 帶有對全函數的限制：

　
: 對於所有參數 **x**，必須提供一個證明證實存在一個 y 滿足 (a) μy ψ(**x**, y) 或 (b) μy R (**x**,y)。

　
: Kleene 還有第三個情況 (c) 不要求證明對於所有 **x** 存在一個 y 使得 ψ(**x**, y)。他在他的全遞迴函數要比可列舉的函數要多的證明中用到了它。

Kleene 的證明是非形式的並使用了類似第一例子的例子。他首先把 μ 算子強制為運算於生成自然數 n 的 χ 函數上的「項的積」的不同形式， 這裡的 n 可以是任何自然數，而 0 在 u 算子的測試被滿足的時候出現。

　
: 使用 Π 函數的重新定義：

　
: μy y<zχ(y) =

* (i): π(**x**, y) = Πs<y χ( **x**, s)

　
: * (ii): φ(**x**) = τ( π(**x**, y), π( **x**, y' ), y)
* (iii): τ(z', 0, y) = y ;τ(u, v, w) 是對 u = 0 或 v > 0 未定義的。

這是微妙的。在第一眼看來這些等式好像使用了原始遞迴。但是 Kleene 仍未提供通用形式的基本步驟或歸納步驟：

　
: * 基本步驟：φ( 0,**x** ) = φ( **x** )
* 歸納步驟：φ( 0,**x** ) = ψ（ y, φ(0,**x**), **x**）接下來如何？首先，我們提醒自己我們已經指派一個參數（自然數）到所有變數 xi。其次，我們確實看到一個後繼算子在做迭代 y（就是 y'）的工作。第三，我們看到函數 μy y<zχ(y, **x**) 正好生成 χ(y,**x**) i.e. χ(0,**x**), χ(1,**x**), ... 的實例，直到一個實例生成 0。第四，在一個實例 χ(n,**x**) 生成 0 的時候，它導致 τ 的中間項，就是 v = π( **x**, y' ) 生成 0。最後，當中間項 v = 0 的時候，μy y<zχ(y) 執行行 (iii) 並「登出」。Kleene 的等式 (ii) 和 (iii) 的表述已經作出了交易使行 (iii) 表示登出 -- 登出只在尋找成功的找到一個 y 滿足 χ(y) 並且中間項 π(**x**, y' ) 為零的時候發生；算子接著終止尋找於 τ(z', 0, y) = y。

　
: τ( π(**x**, y), π( **x**, y' ), y), i.e.:

* τ( π(**x**, 0), π( **x**, 1 ), 0),
* τ( π(**x**, 1), π( **x**, 2 ), 1)
* τ( π(**x**, 2), π( **x**, 3 ), 2)
* τ( π(**x**, 3), π( **x**, 4 ), 3)
* . . . .。直到出現一個匹配於 y=n 並接著：
* τ(z', 0, y) = τ(z', 0, n) = n 並且 μ 算子的尋找結束。

對於 Kleene 的例子，"... 考慮 xi, ... xn 的任何固定值並簡寫 "χ(xi, ... xn,y)"為"χ(y)":

### 例子 #3：無界 μ 算子的抽象機定義

Minsky (1967) p. 21 和 Boolos-Burgess-Jeffrey (2002) p. 60-61 都提供了 μ 算子的抽象機定義。

下列示範跟從 Minsky 但不帶有其怪癖。這個示範將使用密切關於皮亞諾公理和原始遞迴函數的 "後繼" 計數器機模型。模型由（i）帶有指令的表格和我們重新命名為「指令暫存器」（IR）的所謂「狀態暫存器」的有限狀態自動機，（ii）每個都可以只包含一個單一自然數的一些暫存器，和（iii）在下列表格中描述的四個「命令」的指令集：

　
: 在下面，符號 "[r]" 意味著 "r 的內容"，而 "→r" 指示關於暫存器 r 的一個動作。

給極小化算子 μy [φ( **x**, y )] 的演算法在本質上建立函數 φ( **x**, y ) 的一個實例序列，隨著參數 y 的值（自然數）增加；這個處理將繼續（見下面的注釋 †）直到在函數 φ( **x**, y ) 的輸出和某個預先確立的數（通常為 0）之間的匹配出現。所以 φ(**x**, y) 的求值需要在最開始時指派一個自然數到 **x** 的每個變數，指派一個「匹配數」（通常為 0）到一個暫存器 "w"，一個數（通常為 0）到暫存器 y。

　
: 注釋 †：無界 μ 算子將繼續這個嘗試匹配過程直到匹配發生或永遠。所以 "y" 暫存器必須是無界的 -- 它必須能夠持有任意大小的數。不像真實電腦模型，抽象機模型允許如此。在有界 μ 算子的情況下，下界 μ 算子將開始於 y 的內容被設定為不是零的一個數。上界 μ 算子將要求一個額外的暫存器 "ub" 來包含表示這個上界的數加上一個額外比較運算；一個演算法可以同時提供下界和上界。

在下面我們假定指令暫存器 (IR) 遇到了在指令號 "n" 的 μy「常式」。它的第一個動作將是在專用的 "w" 暫存器確立一個數 -- 函數 φ( **x**, y ) 在演算法可以終止之前必須生成的數的「例子」（典型的是數零，但也可以使用不是零的數）。演算法的在 "n+1" 指令的下一個動作將是清除 "y" 暫存器 -- "y" 將充當開始於 0 的「上升暫存器」。接著在 "n+2" 指令演算法求值它的函數 φ( **x**, y ) -- 我們假定將取用 j 指令來完成 -- 在它的求值 φ( **x**, y ) 的結束處放置它的輸出在暫存器 "φ" 中。在 n+j+3rd 指令演算法比較在 "w" 暫存器中的數（比如 0）與在 "φ" 暫存器內的數 -- 如果它們是相同的，則演算法成功並通過「exit」登出；否則它增加 "y" 暫存器的內容並回到「loop」再次用新的 y 值去測試函數 φ( **x**, y )。

## 參見

* 圖靈度
* 多一歸約
* 列舉歸約
* 超算術理論
* 算術層次
* 分析層次
* 能行描述集合論
* 圖靈機

## 參考文獻

* Stephen Kleene (1952) _Introduction to Metamathematics_, North-Holland Publishing Company, New York, 11th reprint 1971: (2nd edition notes added on 6th reprint).
* Marvin L. Minsky (1967), _Computation: Finite and Infinite Machines_, Prentice-Hall, Inc. Englewood Cliffs, N.J.

　
: On pages 210-215 Minsky shows how to create the μ-operator using the register machine model, thus demonstrating its equivalence to the general recursive functions.

* George Boolos，John Burgess，Richard Jeffrey (2002), _Computability and Logic: Fourth Edition_, Cambridge University Press, Cambridge, UK. Cf pp. 70-71.