mu演算子

以下では、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}は、その要素 ψ( 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。 (そして、部分再帰関数の文脈で、クリーネは後に 3 番目の結果「μ = 未決定」を認めています。^{[ 2 ]} )

クリーネは、無制限μ演算子の定義を分割して、2つの状況(a)と(b)に対応させている。状況(b)では、述語R ( x , y )が積Πにおいて算術的機能を果たすためには、まずその出力{t,f}を表現関数χで「操作」して{0,1}を得なければならない。また、状況(a)では、1つの定義を用いる場合、数論的関数χはμ演算子を「満たす」ためにゼロを生成しなければならない。この問題が解決すると、彼は単一の「証明III」で、タイプ(a)または(b)と5つの原始再帰演算子を組み合わせると、(全)再帰関数が得られることを示している。ただし、全関数には次の但し書きがある。

すべてのパラメータxに対して、(a) μ y ψ( x , y )または (b) μ yR ( x , y ) を満たすyが存在することを示す証明を提供する必要があります。

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

クリーネの証明は非形式的で、最初の例と似た例を使用していますが、まず彼はμ演算子を、関数χに作用する「項の積」Πを使用する別の形式に変換します。この形式は、任意の自然数である自然数nと、μ演算子のテストが「満たされる」場合には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の場合未定義です。

これは微妙な点です。一見すると、これらの式は原始的な再帰を用いているように見えます。しかし、クリーネは、次のような一般的な形式の基底ステップと帰納ステップを私たちに示していません。

• 基本ステップ: φ(0, x ) = φ( x )
• 帰納法ステップ: φ(0, x ) = ψ(y, φ(0, x ), x )

何が起こっているのかを確認するには、まず、すべての変数x _iにパラメータ (自然数) を割り当てたことを思い出す必要があります。次に、 y (つまりy' )を反復する後継演算子が動作していることがわかります。そして、関数 μ 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) を実行して「終了します」。クリーネの式（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となり、μ演算子の探索は完了します。

例として、クリーネは「( x _i , ..., x _n ) の任意の固定値を考慮し、 'χ( x _i , ..., x _n ), y )' に対して単に 'χ( y )'と記述する」と述べています。

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

以下のデモンストレーションは、脚注で言及されている「特異性」を除いたミンスキーのモデルに従います。このデモンストレーションでは、ペアノ公理と原始再帰関数に密接に関連する「後継」カウンタマシンモデルを使用します。このモデルは、(i)命令テーブルと、いわゆる「状態レジスタ」（これを「命令レジスタ」（IR）と改名します）を備えた有限状態マシン、(ii)それぞれが単一の自然数のみを格納できるいくつかの「レジスタ」、および(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 ですが、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)

これが実際に何を意味するのかの例については、一般的な再帰関数の例を参照してください。最も単純な切り捨て減算アルゴリズム「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 )がすべて期待される結果をもたらすことを「説得力のある実証」で示すことができるまでは、不安な気持ちが残ります。クリーネの指摘にあるように、私たちの「実証」（つまり、実証であるアルゴリズム）は、効果的であると見なされるほど説得力があるのでしょうか？

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

{ CLR ( r ), INC ( r ), JNE ( r _j , r _k , 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」を使用することで実現されます。