查看“︁Μ算子”︁的源代码

{{Lowercase}}
{{expert|time=2016-03-11T18:29:46+00:00}}
{{untranslated-jargon}}
{{NoteTA
|G1 = IT
|G2 = Math
}}
'''μ算子'''（{{lang-en|μ operator}}）或者'''极小化算子'''（{{lang|en|minimization operator}}），'''无界查找算子'''（{{lang|en|unbounded search operator}}）在[[递归论|可计算性理论]]中，被用來尋找给定性质下的最小[[自然数]]。

== 定义 ==

R( y, x<sub>1</sub> , . . ., x<sub>k</sub> ) 是固定的在自然数上的 ''k+1'' 元关系。低洼“μy”，在无界和有界形式下，都是从自然数 { 0, 1, 2, . . . } 到自然数的“数论函数”。但是，“μy”包含在谓词被满第三代
有界μ算子最早出现在 Kleene（1952年）书中的“第4章原始递归函数，§45 谓词，素因子表示”中：大幅度
:“μy<sub>y<z</sub>R(y)。最小的 y < z 使得 R(y)，如果 (Ey)<sub>y<z</sub> 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”出现在上述定义中的原因。如下面要证明的，有界μ算子“μy<sub>y<z</sub>”是凭借两个原始递归函数有限和 Σ 与有限积 Π，“做测试”的一个谓词函数，和转换 { 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），则
: μy<sub>y<z</sub> R( y, x<sub>1</sub>,..., x<sub>n</sub> ) 是原始递归函数。

(ii) 在（全）[[递归函数]]的上下文中：这里的查找变量是无界的，但是保证对全递归谓词 R 的参数的所有值 x<sub>i</sub> 都存在，
:(x<sub>1</sub>), ..., (x<sub>n</sub>) (Ey) R( y, x<sub>i</sub>, ... x<sub>n</sub> ) 蕴涵了 μyR(y, x<sub>i</sub>, ... x<sub>n</sub>) 是全[[递归函数]]。
:: 这里的 (x<sub>i</sub>) 意味着“对于所有 x<sub>i</sub>”而 Ey 意味着“存在着至少一个 y 的值使得”（cf Kleene (1952) p. 279.）。

则五个原始递归算子加上无界但完全μ算子给出了 Kleene 所称的“一般”递归函数（就是由六个递归函数定义的全函数）。 

(iii) 在[[偏递归函数]]的上下文中：假设关系 ''R'' 成立，当且仅当一个偏序递归函数收敛于零。并假设这个偏递归函数收敛（到某个东西不一定为零）只要 <math>\mu y R(y,x_1,\ldots,x_k)</math> 有定义而且 ''y'' 是 <math>\mu y R(y,x_1,\ldots,x_k)</math> 或更小。则函数 <math>\mu y R(y,x_1,\ldots,x_k)</math> 也是偏递归函数。

μ算子用在可计算函数作为[[μ递归函数]]的特征化中。

== 例子 ==

=== 例子 #1：有界μ算子是原始递归函数 ===

:在下文中，为了节省空间使用粗体字 '''x''' 来表示字符串 x<sub>i</sub>, . . ., x<sub>n</sub>。

有界μ算子可以非常简单的用两个原始递归函数（简写为"prf"）来表达，它们是项的积 Π 与项的和 Σ，还被用来定义 CASE 函数 (cf Kleene #B page 224)。（按照需要，变量的任何界限比如 s≤t 或 t<z 或 5<x<17 等都是适当的）。例如：
:*Π<sub>s≤t</sub> f<sub>s</sub> ('''x''', s) = f<sub>0</sub>('''x''', 0) * f<sub>1</sub>('''x''', 1) * . . . * f<sub>t</sub>('''x''', t)
:*Σ<sub>t<z</sub> g<sub>t</sub> ( '''x''', t ) = g<sub>0</sub>( '''x''', 0 ) + g<sub>1</sub>('''x''', 1 ) + . . . + g<sub>z-1</sub>('''x''', z-1 ) 

我们先要介入叫做谓词 R 的[[表示函数]]的一个函数ψ。函数 ψ 定义为从输入（t= "真", f="假"）到输出 ( 0, 1 ) 的映射（'''注意次序!'''）。在这种情况下给 ψ 的输入 { t, f } 来自 R 的输出：
:* ψ( R = t ) = 0
:* ψ( R = f ) = 1
  
Kleene 展示了μy<sub>y<z</sub> R(y)的如下定义；我们看到积函数 Π 充当了布尔 AND 算子，而和函数 Σ 充当布尔 OR 算子，不同的是它生成 { Σ≠0, Σ=0 } 而不是 { 1, 0 }: 
: μy <sub>y<z</sub> R(y) = Σ<sub>t<z</sub> Π<sub>s≤t</sub> ψ( 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 ): 
{| class="wikitable" style="text-align: center; vertical-align: bottom;"
|-   
| width="209"| y
| width="24"| 0
| width="24"| 1
| width="24"| 2
|style="background-color:#C0C0C0;" width="24"| '''3'''
| width="24"| 4
| width="24"| 5
| width="24"| 6
| width="25.2"| 7=z

|-   
| χ(y)
| 1
| 1
| 1
|style="background-color:#C0C0C0;font-weight:bold"| 0
| 1
| 0
| 0
| 

|-   
| π(y) = Π<sub>s≤y</sub> χ(s)
| 1
| 1
| 1
|style="background-color:#C0C0C0;font-weight:bold"| 0
| 0
| 0
| 0
| 0

|-   
| σ(y) = Σ<sub>t<y</sub> π(t)
| 0
| 1
| 2
|style="background-color:#C0C0C0;"| '''3'''
| 3
| 3
| 3
| 3

|- 
| 最小的 y<z 使得 R(y) 为"真": φ(y) = μy <sub>y<z</sub> R(y)
| 
| 
| 
|style="background-color:#C0C0C0;font-weight:bold" | 3
| 
| 
| 
| 

|}

=== 例子 #2：无界μ算子不是原始递归函数 ===
  
无界μ算子 -- 函数 μy -- 经常定义于教科书中。但是读者可能奇怪于为什么无界μ算子查找生成零而不是某个其他自然数的函数 R('''x''', y) -- 现代教科书没有给出原因。
:在脚注中 Minsky 的确允许他的算子在内部过程生成一个对参数 "k" 的匹配的时候终止；这个例子也是有用的因为它展示了另一个作者的格式：''
::" For μ<sub>t</sub>[ φ(t) = k ] "(p. 210)

使用零的原因是无界算子μy将依据其索引 y 允许随着μ算子的查找而增长的函数"积" Π 来定义。如上述例子提及的，一串数ψ('''x''', 0) *, . . ., * ψ('''x''', y)的积 Π <sub>x<y</sub> 生成零，只要它的成员 ψ('''x''', i) 之一为零：
: Π<sub>s<y</sub> = ψ('''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 <sub>y<z</sub>χ(y) = 
:*(i): π('''x''', y) = Π<sub>s<y</sub> χ( '''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'''）接下来如何？首先，我们提醒自己我们已经指派一个参数（自然数）到所有变量 x<sub>i</sub>。其次，我们确实看到一个后继算子在做迭代 y（就是 y'）的工作。第三，我们看到函数 μy <sub>y<z</sub>χ(y, '''x''') 正好生成 χ(y,'''x''') i.e. χ(0,'''x'''), χ(1,'''x'''), ... 的实例，直到一个实例生成 0。第四，在一个实例 χ(n,'''x''') 生成 0 的时候，它导致τ的中间项，就是 v = π( '''x''', y' ) 生成 0。最后，当中间项 v = 0 的时候，μy <sub>y<z</sub>χ(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 的例子，"...考虑 x<sub>i</sub>, ... x<sub>n</sub> 的任何固定值并简写 "χ(x<sub>i</sub>, ... x<sub>n</sub>,y)" 为 "χ(y)":
{| class="wikitable" style="text-align: center; vertical-align: bottom;"
|-   
| width="208.8"| y
| width="24"| 0
| width="24"| 1
| width="24"| 2
|style="background-color:#C0C0C0;" width="24"| '''3'''
| width="24"| 4
| width="24"| 5
| width="24"| 6
| width="25.2"| 7
| width="25.2"| etc

|-   
| χ(y)
| 3
| 1
| 2
|style="background-color:#C0C0C0;"| '''0'''
| 9
| 0
| 1
| 5
|style="font-weight:bold"|  . . .

|-   
| π(y) = Π s≤y χ(s)
| 1
| 3
| 3
|style="background-color:#C0C0C0;"| '''6'''
| 0
| 0
| 0
| 0
|style="font-weight:bold"|  . . .

|- 
| 
| 
| 
| 
|style="background-color:#C0C0C0"| '''↑'''
| 
| 
| 
| 
| 

|- 
| 最小的 y<z 使得 R(y) 为"真": φ(y) = μy y<z R(y)
| 
| 
| 
|style="background-color:#C0C0C0;font-weight:bold"| 3
| 
| 
| 
| 
| 

|}

=== 例子 #3：无界μ算子的抽象机定义 ===

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

下列示范跟从 Minsky 但不带有其怪癖。这个示范将使用密切关于[[皮亚诺公理]]和[[原始递归函数]]的"后继"[[计数器机]]模型。模型由（i）带有指令的表格和我们重命名为“指令寄存器”（IR）的所谓“状态寄存器”的有限状态自动机，（ii）每个都可以只包含一个单一自然数的一些寄存器，和（iii）在下列表格中描述的四个“命令”的指令集：

:在下面，符号 " [ r ] " 意味着" r 的内容"，而 " →r " 指示关于寄存器 r 的一个动作。

{|class="wikitable"
|-
! 指令
! 助记符
! 对寄存器 "r" 的动作
! 对指令寄存器 IR 的动作

|- 
| 清除寄存器
|style="text-align:left;"| CLR ( r )
|style="text-align:center;"| 0 → r 
|style="text-align:center;"| [ IR ] +1 → IR 

|- 
| 增加寄存器
| INC ( r )
|style="text-align:center;"| [ r ] +1 → r 
|style="text-align:center;"| [ IR ] +1 → IR 

|- 
| 等于时跳转
| JE (r<sub>1</sub>, r<sub>2</sub>, z)
|style="text-align:center;"| 无
|style="text-align:center;"| IF [ r1 ] = [ r2 ] THEN z → IR <br />ELSE [ IR ] +1 → IR   

|- 
| 停机
| H
|style="text-align:center;"| 无
|style="text-align:center;"| [ 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 )。

{| class="wikitable" style="vertical-align: bottom;"
|-   
! IR
!
! 指令
! 对寄存器的动作
! 对指令寄存器 IR 的动作

|- 
| n
| μy[ φ( '''x''', y ) ]：
| CLR ( w )
|style="text-align:center;"| 0 → w
| [ IR ] +1 → IR

|-
| n+1
|
| CLR ( y )
|style="text-align:center;"| 0 → y
| [ IR ] +1 → IR

|-
| n+2
| ''loop:''
| φ ( '''x''', y )
|style="text-align:center;"| φ（['''x''']，[y]）→ φ
| [ IR ] +j+1 → IR

|-
| n+j+3
|
| JE (φ, w, exit)
|style="text-align:center;"| 无
| CASE: { IF [φ]=[w] THEN ''exit'' → IR <br />ELSE [IR] +1 → IR }

|-
| n+j+4
|
| INC ( y )
|style="text-align:center;"| [ y ] +1 → y
| [ IR ] +1 → IR

|-
| n+j+5
|
| JE (0, 0, loop)
|style="text-align:center;"| 无条件跳转
| CASE: { IF [r0] =[r0] THEN ''loop'' → IR <br />ELSE ''loop'' → IR }

|-
| n+j+6
| ''exit:''
| ''etc.''
|
|
|}
==參見==
{{mathportal}}
* [[图灵度]]
* [[多一归约]]
* [[枚举归约]]
* [[超算术理论]]
* [[算术层次]]
* [[分析层次]]
* [[能行描述集合论]]
* [[图灵机]]

==參考文獻==
*[[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.

[[Category:递归论]]