μ算子
![本頁使用了標題或全文手工轉換](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/c/cd/Zh_conversion_icon_m.svg/35px-Zh_conversion_icon_m.svg.png)
![]() | 此條目需要精通或熟悉相關主題的編者參與及協助編輯。 (2016年3月11日) |
![]() |
μ算子(英語:μ 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 成立,若且唯若一個偏序遞迴函數收斂於零。並假設這個偏遞迴函數收斂(到某個東西不一定為零)只要 有定義而且 y 是 或更小。則函數 也是偏遞迴函數。
μ算子用在可計算函數作為μ遞迴函數的特徵化中。
例子
例子 #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 ):
y | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7=z |
χ(y) | 1 | 1 | 1 | 0 | 1 | 0 | 0 | |
π(y) = Πs≤y χ(s) | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 |
σ(y) = Σt<y π(t) | 0 | 1 | 2 | 3 | 3 | 3 | 3 | 3 |
最小的 y<z 使得 R(y) 為"真": φ(y) = μy y<z R(y) | 3 |
例子 #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)":
y | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | etc |
χ(y) | 3 | 1 | 2 | 0 | 9 | 0 | 1 | 5 | . . . |
π(y) = Π s≤y χ(s) | 1 | 3 | 3 | 6 | 0 | 0 | 0 | 0 | . . . |
↑ | |||||||||
最小的 y<z 使得 R(y) 為"真": φ(y) = μy y<z R(y) | 3 |
例子 #3:無界μ算子的抽象機定義
Minsky (1967) p. 21 和 Boolos-Burgess-Jeffrey (2002) p. 60-61 都提供了μ算子的抽象機定義。
下列示範跟從 Minsky 但不帶有其怪癖。這個示範將使用密切關於皮亞諾公理和原始遞迴函數的"後繼"計數器機模型。模型由(i)帶有指令的表格和我們重新命名為「指令暫存器」(IR)的所謂「狀態暫存器」的有限狀態自動機,(ii)每個都可以只包含一個單一自然數的一些暫存器,和(iii)在下列表格中描述的四個「命令」的指令集:
- 在下面,符號 " [ r ] " 意味著" r 的內容",而 " →r " 指示關於暫存器 r 的一個動作。
指令 | 輔助記憶碼 | 對暫存器 "r" 的動作 | 對指令暫存器 IR 的動作 |
---|---|---|---|
清除暫存器 | CLR ( r ) | 0 → r | [ IR ] +1 → IR |
增加暫存器 | INC ( r ) | [ r ] +1 → r | [ IR ] +1 → IR |
等於時跳轉 | JE (r1, r2, z) | 無 | IF [ r1 ] = [ r2 ] THEN z → IR ELSE [ IR ] +1 → IR |
停機 | H | 無 | [ IR ] → IR |
給極小化算子μ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 )。
IR | 指令 | 對暫存器的動作 | 對指令暫存器 IR 的動作 | |
---|---|---|---|---|
n | μy[ φ( x, y ) ]: | CLR ( w ) | 0 → w | [ IR ] +1 → IR |
n+1 | CLR ( y ) | 0 → y | [ IR ] +1 → IR | |
n+2 | loop: | φ ( x, y ) | φ([x],[y])→ φ | [ IR ] +j+1 → IR |
n+j+3 | JE (φ, w, exit) | 無 | CASE: { IF [φ]=[w] THEN exit → IR ELSE [IR] +1 → IR } | |
n+j+4 | INC ( y ) | [ y ] +1 → y | [ IR ] +1 → IR | |
n+j+5 | JE (0, 0, loop) | 無條件跳轉 | CASE: { IF [r0] =[r0] THEN loop → IR ELSE loop → IR } | |
n+j+6 | exit: | etc. |
參見
參考文獻
- 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.