μ演算子

計算可能性理論では、μ 演算子、最小化演算子、または無制限検索演算子は、与えられた特性を持つ最小の自然数を検索します。μ 演算子を原始再帰関数に追加すると、すべての計算可能な関数を定義できるようになります。

R( y , x ₁ , ..., x _k ) が自然数上の固定された ( k +1) 項関係であるとします。μ 演算子 "μ y " は、無制限形式または制限形式のいずれにおいても、自然数から自然数に定義された "数論的関数" です。ただし、"μ y " には自然数に対する述語が含まれており、述語が満たされる場合はtrueと評価され、満たされない場合は falseと評価される条件と考えることができます。

有界μ演算子は、Kleene (1952)の第9章「原始再帰関数」の§45「述語」の素因数表現に次のように登場します。

「」（p.225）${\displaystyle \mu y_{y<z}R(y).\ \ {\mbox{最小の}}\ y<z\ {\mbox{そのような}}\ R(y),\ {\mbox{if}}\ (\exists y)_{y<z}R(y);\ {\mbox{それ以外の場合}},\ z.}$

Stephen Kleene は、変数yの範囲に関する 6 つの不等式制約のいずれも許容されると指摘しています。つまり、y < z、y ≤ z、w < y < z、w < y ≤ z、w ≤ y < z 、およびw ≤ y ≤ zです。「指定された範囲にR( y ) [が「真」である]ようなy が含まれていない場合、"μ y " 式の値は範囲の基数です」(p. 226)。これが、上記の定義にデフォルトの " z " が表示される理由です。以下に示すように、有界 μ 演算子 "μ y _{y < z} " は、有限和 Σ と有限積 Π と呼ばれる 2 つの基本再帰関数、"テストを実行する" 述語関数、および{t, f} を { 0 , 1 } に変換する表現関数によって定義されます。

第11章§57一般再帰関数において、クリーネは変数y上の無限μ演算子を次のように定義している。

「」（p. 279、「 」は「...となるyが存在する」という意味です）${\displaystyle (\exists y)\mu yR(y)=\{{\mbox{最小の（自然数）}}\ y\ {\mbox{となる}}\ R(y)\}}$${\displaystyle (\exists y)}$

この例では、 R 自体、またはそれを表す関数は、条件が満たされる場合（つまり、true を返す場合）に0 を返します。その後、関数は数値y を返します。 yには上限が存在しないため、その定義には不等式は現れません。

与えられたR( y )に対して、無限大のμ演算子μyR ( y )（「(Ey )」の要件がないことに留意）は部分関数である。Kleeneはこれを全関数として扱っている（317ページを参照）。

${\displaystyle \varepsilon yR(x,y)={\begin{cases}{\text{最小の }}y{\text{、}}R(x,y),&{\text{if }}(Ey)R(x,y)\\0,&{\text{otherwise}}.\end{cases}}}$

無制限μ演算子の全バージョンは、高階 逆数学（Kohlenbach（2005））で次の形式で研究されています。

${\displaystyle (\exists \mu ^{2})(\forall f^{1}){\big (}(\exists n^{0})(f(n)=0)\rightarrow f(\mu (f))=0{\big )},}$

ここで、上付き文字はnが 0 次、fが 1 次、μ が 2 次であることを意味します。この公理は、高次の逆数学の通常の基本理論と組み合わせると、ビッグファイブシステムACA ₀^{を生み出します。 [要出典]}

(i)原始再帰関数の文脈において、 μ演算子の探索変数yが有界である場合、例えば以下の式ではy < zであり、述語Rが原始再帰的である場合（Kleene Proof #E p. 228）、

μ y _{y < z} R( y , x ₁ , ..., x _n ) は原始再帰関数です。

(ii) （全）再帰関数の文脈では、探索変数yは無制限であるが、全再帰述語Rのパラメータの すべての値x _iに対して存在することが保証されている。

( x ₁ ),...,( x _n ) (Ey) R( y , x _i , ..., x _n ) は、μ y R( y , x _i , ..., x _n ) が全再帰関数であることを意味します。

ここで、( x _i ) は「すべてのx _iに対して」を意味し、E y は「...となるyの値が少なくとも 1 つ存在する」を意味します (Kleene (1952) p. 279 を参照)。

すると、5 つの基本再帰演算子と、無制限だが全 μ 演算子を組み合わせると、Kleene が「一般」再帰関数 (つまり、6 つの再帰演算子によって定義される全関数) と呼んだものが生成されます。

(iii)部分再帰関数のコンテキストにおいて、関係 R が成り立つのは、部分再帰関数がゼロに収束する場合のみであるとします。また、その部分再帰関数は、μ y R( y , x ₁ , ..., x _k ) が定義され、yが μ y R( y , x ₁ , ..., x _k ) 以下である場合に、必ず収束する(ゼロとは限らない何かに)とします。この場合、関数 μ y R( y , x ₁ , ..., x _k ) も部分再帰関数です。

μ 演算子は、計算可能な関数をμ 再帰関数として特徴付けるために使用されます 。

構成的数学において、無制限探索演算子はマルコフの原理と関連しています。

以下の xは 文字列 x _i、...、x _nを表します。

有界μ 演算子は、CASE 関数の定義にも使用される 2 つの原始再帰関数 (以下、「prf」)、つまり項の積 Π と項の和 Σ で簡単に表現できます (Kleene #B 224 ページを参照)。 (必要に応じて、変数の境界 ( s ≤ t、t < z、5 < x < 17 など) は任意に指定できます)。 たとえば、次のようになります。

• Π _{s ≤ t} f _s ( x , s ) = f ₀ ( x , 0) × f ₁ ( x , 1) × ... × f _t ( x , t )
• Σ _{t < z} g _t ( x , t ) = g ₀ ( x , 0) + g ₁ ( x , 1) + ... + g _z-1 ( x , z -1)

先に進む前に、述語 R の「表現関数」と呼ばれる関数 ψ を導入する必要があります。関数 ψ は、入力 (t = "真実"、f = "偽り") から出力 (0、1) まで定義されます (順序に注意してください)。この場合、ψ への入力、つまり {t、f} は R の出力から来ます。

• ψ(R = t) = 0
• ψ(R = f) = 1

クリーネは、μ y _{y < z} R( y ) が次のように定義されることを示しています。積関数 Π はブール OR 演算子のように動作し、和 Σ はブール AND のように動作しますが、単に {1, 0} ではなく {Σ≠0, Σ=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) を持つ原始再帰です。

この式は、クリーネの例で観察すると簡単になります。彼は単に、表現関数 ψ(R( y )) のエントリを作成しました。彼は、表現関数を ψ( x , y )ではなくχ( y ) と指定しました。

無制限 μ 演算子 (関数 μ y ) は、テキストで一般的に定義されているものです。しかし、読者は、無制限 μ 演算子が、他の自然数ではなく、 ゼロを生成する関数 R( x , y )を検索する理由を疑問に思うかもしれません。

脚注では、ミンスキーは、内部の関数がパラメータ「k」に一致する結果を生成した場合に演算子を終了することを許可しています。この例は、別の著者の形式を示しているため、有用でもあります。

「μ _t [φ( t ) = k ] の場合」（p. 210）

ゼロになる理由は、無限演算子 μ y が関数「積」Π によって定義され、そのインデックスyはμ 演算子の検索に応じて「増加」することが許可されるためです。上記の例で述べたように、数値の文字列 ψ( x , 0) *、...、* ψ( x , y ) の積 Π _{x < y}は、その要素の 1 つ ψ( x , i ) がゼロである場合は常にゼロになります。

Π _{s < y} = ψ( x , 0) * , ..., * ψ( x , y ) = 0

0≤ i ≤ sの場合、 ψ( x , i ) = 0 となります。したがって、 Π はブール AND のように動作します。

関数 μ y は「出力」として単一の自然数y = {0, 1, 2, 3, ...} を生成します。ただし、演​​算子の内部では、次の 2 つの「状況」のいずれかが発生する可能性があります: (a) 単一の自然数を生成する「数論的関数」 χ、または (b) {t = true、f = false} のいずれかを生成する「述語」 R。(そして、部分再帰関数のコンテキストで、Kleene は後に 3 番目の結果「μ = 未決定」を認めています。^[1] )

クリーネは、2 つの状況 (a) と (b) を扱うために、無制限の μ 演算子の定義を分割しています。状況 (b) では、述語 R( x , y ) が積 Π の算術機能を果たす前に、その出力 {t, f} は、その代表関数 χによって「操作」されて {0, 1} を生成する必要があります。また、状況 (a) では、1 つの定義を使用する場合、数論関数 χ は、 μ 演算子を「満たす」ために 0 を生成する必要があります。この問題が解決されたので、彼は単一の「証明 III」で、タイプ (a) または (b) のいずれかと 5 つの基本再帰演算子を組み合わせると、(全)再帰関数が生成され、全関数に対して次の条件が満たされることを実証しています。

すべてのパラメータ xについて、(a) μ y ψ( x , y )または (b) μ y R( x , y ) を満たすy が存在することを示す証明が提供されなければなりません。

クリーネは、「すべてのx a yに対して、ψ( x , y ) が存在する」という証明を必要としない 3 番目の状況 (c) も認めています。彼はこれを利用して、列挙できるよりも多くの全再帰関数が存在することを証明しています。脚注「全関数の証明」を参照してください。

Kleene の証明は非公式で、最初の例に似た例を使用していますが、最初に μ 演算子を、関数 χ に作用する「項の積」 Π を使用する別の形式に変換します。これにより、任意の自然数nが生成され、u 演算子のテストが「満たされる」場合は 0 が生成されます。

Π関数で書き直した定義:

μ 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 )

何が起こっているかを確認するには、まず、すべての変数x _iにパラメータ（自然数）を割り当てたことを思い出す必要があります。次に、後続演算子がy（つまりy'）を反復処理していることがわかります。そして 3 番目に、関数 μ y _{y < z} χ( y , x ) は、インスタンスが 0 を生成するまで、 χ( y , x )のインスタンス、つまり χ(0, x )、χ(1, x )、... を生成していることがわかります。4 番目に、インスタンス χ( n , x ) が 0 を生成すると、τ の中間項、つまり v = π( x , y' ) が 0 を生成します。最後に、中間項v = 0 のとき、 μ y _{y < z} χ( y ) は行 (iii) を実行して「終了します」。 Kleene の式 (ii) と (iii) の表現は、 (iii) の行が出口を表しているという点を強調するために入れ替えられています。この出口は、探索によってχ( y )を満たすy が見つかり、中間の積項 π( x , y' ) が 0 である場合にのみ取られる出口です。その後、演算子は τ( z' , 0, y ) = yで探索を終了します。

τ(π( x , y ), π( x , y' ), y )、つまり:

• τ(π( 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 _i , ..., x _n ) の任意の固定値を考慮し、'χ( x _i , ..., x _n ), y )' を単に 'χ( y )' と書きます」と述べています。

Minsky (1967) p. 21 と Boolos-Burgess-Jeffrey (2002) p. 60-61 は両方とも、抽象マシンとしての μ 演算子の定義を示しています。脚注「μ の代替定義」を参照してください。

以下のデモンストレーションは、脚注で言及されている「特殊性」を除けば、ミンスキーの法則に従います。デモンストレーションでは、ペアノの公理と原始再帰関数に密接に関連する「後継」カウンターマシンモデルを使用します。このモデルは、(i) 命令のテーブルといわゆる「状態レジスタ」(ここでは「命令レジスタ」(IR) と改名します) を備えた有限状態マシン、(ii) それぞれが 1 つの自然数のみを含むことができるいくつかの「レジスタ」、および (iii) 次の表で説明されている 4 つの「コマンド」の命令セットで構成されます。

以下では、記号「[r]」は「内容」を意味し、「→r」はレジスタrに関する動作を示します。

最小化演算子 μ y [φ( x , y )]のアルゴリズムは、本質的には、パラメータy (自然数)の値が増加するにつれて関数 φ( x , y ) のインスタンスのシーケンスを作成します。このプロセスは、関数 φ( x , y )の出力と事前に設定された数値 (通常は 0) が一致するまで継続されます (以下の注 † を参照)。したがって、 φ( x , y ) の評価では、最初に、各変数xに自然数を割り当て、レジスタ " w "に「一致数」(通常は 0) を割り当て、レジスタyに数値 (通常は 0) を割り当てる必要があります。

注 †:無制限μ 演算子は、一致の試みを無限に、または一致が発生するまで続けます。したがって、「 y 」レジスタは無制限である必要があります。つまり、任意のサイズの数値を「保持」できる必要があります。「実際の」コンピュータ モデルとは異なり、抽象マシン モデルではこれが可能です。制限付きμ 演算子の場合、下限付き μ 演算子は、 yの内容がゼロ以外の数値に設定された状態で開始します。上限付き μ 演算子には、上限を表す数値と追加の比較演算を格納するための追加のレジスタ「ub」が必要です。アルゴリズムは、下限と上限の両方を提供できます。

以下では、命令レジスタ (IR) が命令番号 " n "でμ y "ルーチン" に遭遇すると仮定します。最初のアクションは、専用の " w "レジスタに数値を設定することです。これは、アルゴリズムが終了する前に関数 φ( x、y ) が生成しなければならない数値の "例" です(通常、これは数値 0 ですが、ゼロ以外の数値の使用については脚注を参照してください)。命令 " n +1" でのアルゴリズムの次のアクションは、" y "レジスタをクリアすることです。" y " は、0 から始まる "アップカウンタ" として機能します。次に、命令 " n +2" で、アルゴリズムは関数 φ( x、y ) を評価します。これにはj命令かかると仮定します。評価の最後に、φ( x、 y) は出力をレジスタ "φ" に格納します。 ( n + j +3)番目の命令では、アルゴリズムは「 w 」レジスタの数値(例えば0)を「φ」レジスタの数値と比較します。両者が同じであればアルゴリズムは成功し、exitから抜け出します。そうでない場合は「 y」レジスタの内容を増分し、この新しいy値でループバックして関数φ( x , y )を再度テストします。

• マッカーシー形式主義

関数が全関数になるためには、そのパラメータx _iの値のあらゆる組み合わせに対して、ある自然数y がμ 演算子を満たし、計算を表すアルゴリズムが終了できることを 他の方法(例:帰納法) で証明することが必須です。

「...方程式のシステムが実際に一般再帰関数 (つまり全関数) を定義していると仮定するのは、常にためらわなければなりません。通常、これには補助的な証拠が必要です。たとえば、各引数値に対して、計算が一意の値で終了するという帰納的証明の形式です。」(ミンスキー (1967) p.186)

「言い換えれば、関数が一般再帰的であることの証明が有効でない限り、関数が一般再帰的（つまり全再帰的）であることが示されたという理由で、関数が効果的に計算可能であると主張するべきではない。」（Kleene（1952）p.319）

これが実際に何を意味するかの例については、mu 再帰関数の例を参照してください。最も単純な切り捨て減算アルゴリズム「x - y = d 」でも、 x < y の未定義のケースでは、(1) 終了なし、(2) 数値なし (つまり、形式に問題があるため、結果が自然数とみなされない)、または (3) 不正: 正しい形式で間違った数値が生成されます。「適切な」減算アルゴリズムでは、すべての「ケース」に細心の注意を払う必要があります。

( x , y ) = {(0, 0), ( a , 0), (0, b ), ( a ≥ b , b ), ( a = b , b ), ( a < b , b )}。

しかし、アルゴリズムがインスタンス {(0, 0)、(1, 0)、(0, 1)、(2, 1)、(1, 1)、(1, 2)} で期待される出力を生成することが示されたとしても、( x、y ) = ( n、m )のケースがすべて期待される結果を生成するという「説得力のあるデモンストレーション」を考案するまでは、不安な気持ちが残ります。Kleene のポイントは、私たちの「デモンストレーション」(つまり、デモンストレーションであるアルゴリズム) は、効果的であると見なされるほど説得力があるかどうかです。

無制限の μ 演算子は Minsky (1967) p. 210 によって定義されていますが、特異な欠陥があります。演算子は、述語 (IF-THEN-ELSE テスト) が満たされてもt =0 にならず、 t =2 になります。Minsky のバージョンでは、カウンターは " t " で、関数 φ( t , x ) は、その数をレジスタ φ に格納します。通常の μ 定義では、レジスタwには 0 が含まれますが、Minsky は、レジスタ w には任意の数k を含めることができると述べています。Minsky の命令セットは、次のものと同等です。ここで、"JNE" は、等しくない場合は z にジャンプします。

{CLR( r ),INC( r ),JNE ( rj , _{rk ,} z ) }

無制限の μ 演算子は、Boolos-Burgess-Jeffrey (2002) p. 60-61 によって、次の命令セットと同等のカウンター マシンに対しても定義されています。

{ CLR (r), INC (r), DEC (r), JZ (r, z), H }

このバージョンでは、カウンタ「y」は「r2」と呼ばれ、関数 f( x 、 r2 ) はその数値をレジスタ「r3」に格納します。おそらく、Boolos-Burgess-Jeffrey が r3 をクリアする理由は、ループへの無条件ジャンプを容易にするためです。これは、多くの場合、「0」を含む専用レジスタ「0」を使用して行われます。

• クリーネ、スティーブン（2009）[1952]、メタ数学入門、ノースホランド、ISBN 9780923891572、OCLC  935015457
• コーレンバッハ、ウルリッヒ (2005)、高階逆数学、逆数学 2001、論理学の講義ノート、ケンブリッジ大学出版局、pp. 281–295、CiteSeerX  10.1.1.643.551、doi :10.1017/9781316755846.018、ISBN 9781316755846
• ミンスキー、マーヴィン L. (1972) [1967]、計算：有限機械と無限機械、プレンティス・ホール、ISBN 9780131654495、OCLC  974146753

210-215ページで、ミンスキーはレジスタマシンモデルを使用してμ演算子を作成する方法を示し、一般的な再帰関数との同等性を実証しています。

• Boolos, George ; Burgess, John ; Jeffrey, Richard (2002)、「S6.2 最小化」、Computability and Logic (第 4 版)、Cambridge University Press、pp. 70–71、ISBN 9780521701464