μ算子

✍ dations ◷ 2025-09-09 16:42:48 #递归论

μ算子(英语:μ operator)或者极小化算子(minimization operator),无界查找算子(unbounded search operator)在可计算性理论中,被用来查找给定性质下的最小自然数。

R( y, x1 , . . ., xk ) 是固定的在自然数上的 元关系。低洼“μy”,在无界和有界形式下,都是从自然数 { 0, 1, 2, . . . } 到自然数的“数论函数”。但是,“μy”包含在谓词被满第三代有界μ算子最早出现在 Kleene(1952年)书中的“第4章原始递归函数,§45 谓词,素因子表示”中:大幅度

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 上的无界μ算子,

在这个实例 R 自身内,或它的表示函数,在它被满足的时候得出 0(就是得出);这个函数接着得出数 y。在 y 上不存在上界,所以在它的定义中不出现不等式。

对于一个给定 R(y) 无界μ算子 μyR(y)(注意不要求“(Ey)”)可以导致全函数或偏函数。Kleene 以不同的方式写这个潜在的偏函数(cf. p. 317):

(i) 在原始递归函数的上下文中,这里的 μ算子的查找变量 y 是有界的,也就是在下面公式中的 y<z,如果谓词 R 是原始递归的(Kleene Proof #E p. 228),则

(ii) 在(全)递归函数的上下文中:这里的查找变量是无界的,但是保证对全递归谓词 R 的参数的所有值 xi 都存在,

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

(iii) 在偏递归函数的上下文中:假设关系 成立,当且仅当一个偏序递归函数收敛于零。并假设这个偏递归函数收敛(到某个东西不一定为零)只要 μ y R ( y , x 1 , , x k ) {\displaystyle \mu yR(y,x_{1},\ldots ,x_{k})} μ y R ( y , x 1 , , x k ) {\displaystyle \mu yR(y,x_{1},\ldots ,x_{k})} 或更小。则函数 μ y R ( y , x 1 , , x k ) {\displaystyle \mu yR(y,x_{1},\ldots ,x_{k})} 也是偏递归函数。

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

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

我们先要介入叫做谓词 R 的表示函数的一个函数ψ。函数 ψ 定义为从输入(t= "真", f="假")到输出 ( 0, 1 ) 的映射(注意次序!)。在这种情况下给 ψ 的输入 { t, f } 来自 R 的输出:

Kleene 展示了μyy<z R(y)的如下定义;我们看到积函数 Π 充当了布尔 AND 算子,而和函数 Σ 充当布尔 OR 算子,不同的是它生成 { Σ≠0, Σ=0 } 而不是 { 1, 0 }:

通过 Kleene 给出例子很容易理解这个等式。他只为指示函数 ψ(R(y))构建了表格。他用表示函数 χ(y) 简写 ψ( x, y ):

无界μ算子 -- 函数 μy -- 经常定义于教科书中。但是读者可能奇怪于为什么无界μ算子查找生成零而不是某个其他自然数的函数 R(x, y) -- 现代教科书没有给出原因。

使用零的原因是无界算子μy将依据其索引 y 允许随着μ算子的查找而增长的函数"积" Π 来定义。如上述例子提及的,一串数ψ(x, 0) *, . . ., * ψ(x, y)的积 Π x<y 生成零,只要它的成员 ψ(x, i) 之一为零:

如果任何 ψ(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) 与五个原始递归函数一起产生(全)递归函数 ... 带有对全函数的限制:

Kleene 的证明是非形式的并使用了类似第一例子的例子。他首先把μ算子强制为运算于生成自然数 n 的χ函数上的“项的积”的不同形式, 这里的 n 可以是任何自然数,而 0 在 u 算子的测试被满足的时候出现。

这是微妙的。在第一眼看来这些等式好像使用了原始递归。但是 Kleene 仍未提供通用形式的基本步骤或归纳步骤:

对于 Kleene 的例子,"...考虑 xi, ... xn 的任何固定值并简写 "χ(xi, ... xn,y)" 为 "χ(y)":

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

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

给极小化算子μy 的算法在本质上创建函数φ( x, y ) 的一个实例序列,随着参数 y 的值(自然数)增加;这个处理将继续(见下面的注释 †)直到在函数φ( x, y ) 的输出和某个预先确立的数(通常为 0)之间的匹配出现。所以 φ(x, y) 的求值需要在最开始时指派一个自然数到 x 的每个变量,指派一个“匹配数”(通常为 0)到一个寄存器 "w",一个数(通常为 0)到寄存器 y。

在下面我们假定指令寄存器 (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 )。

相关

  • 非洲苏铁非州苏铁是非洲苏铁属(Encephalartos)的苏铁,原产于非洲,但却处于濒危。它们是最原始的裸子植物之一。非洲苏铁是由德国植物学家Johann Georg Christian Lehmann于1834年描述的
  • 浪漫主义音乐浪漫时期的音乐是维也纳古典乐派的延续和发展,是西方音乐史上的一种音乐风格或者一个时代。浪漫主义主要用于描述1830年—1850年间的文学创作,以及1820年—1900年间的音乐创作
  • 孚日省孚日省(法语:Vosges,法语发音:.mw-parser-output .IPA{font-family:"Charis SIL","Doulos SIL","Linux Libertine","Segoe UI","Lucida Sans Unicode","Code2000","Gentium","Ge
  • 中继透镜中继透镜(relay lens)通常有两组镜片,安装在镜筒中组成,镜片可以是普通球面透镜,也可以是非球面透镜。虽然名称叫做中继透镜,但它并不是透镜。两组镜片,至少有两个配对透镜或两个配
  • 薛定谔猫薛定谔猫(英语:Schrödinger's Cat)是奥地利物理学者埃尔温·薛定谔于1935年提出的一个思想实验。通过这思想实验,薛定谔指出了应用量子力学的哥本哈根诠释于宏观物体会产生的问
  • 布哈拉汗国坐标:39°46′40″N 64°24′39″E / 39.77778°N 64.41083°E / 39.77778; 64.41083布哈拉(乌兹别克语:Buxoro)是位于乌兹别克斯坦西南部的一座城市,也是该国第五大城市和布哈拉
  • 莱芜莱芜,可能有以下含义:
  • 芬斯特拉峰芬斯特拉峰(Finsteraarhorn,4274米),属瑞士阿尔卑斯山脉部分伯尔尼阿尔卑斯山脉中的最高峰。芬斯特拉峰首次登顶者长期存在一些争议。Johann Rudolf Meyer声称与登山导游 Arnold
  • 新竹物流新竹物流成立于1938年。由传统运输公司转型为现代化服务业,提供物流、商流、金流、资讯流整合之综合型物流服务。2017年营业额已达到150亿台币,代收货款金额达210亿,为台湾物流
  • 同尾酶同尾酶(英语:Isocaudomers)是指一组识别序列不同,但切出的粘性末端相同的限制性内切酶。比如限制酶 Mbo I 和 BamH I 就是一对同尾酶:Mbo I N*GATC N N CTAG*NBamH I G*GATC