マッカーシー形式主義

コンピュータサイエンスと再帰理論において、コンピュータ科学者ジョン・マッカーシーのマッカーシー形式論( 1963) は、コンピュータサイエンスで一般的な IF-THEN-ELSE 構造と、基本再帰関数の 4 つの演算子 (ゼロ、後続、数の等価性、合成) を使用して、再帰関数の概念を明確にします。条件演算子は、基本再帰とmu 演算子の両方に代わるものです。

導入

マッカーシーの考え条件式

マッカーシー（1960）は彼の形式主義を次のように説明した：^[1]

「この記事では、まず関数を再帰的に定義するための形式について説明します。この形式は、プログラミング言語としても、計算理論を開発するための手段としても利点があると考えています。

関数一般に関する数学的なアイデアや表記法がいくつか必要になります。アイデアのほとんどはよく知られていますが、条件式の概念は新しいと考えられており、条件式を使用すると、関数を新しい便利な方法で再帰的に定義できます。

ミンスキーの「形式主義」の説明

マービン・ミンスキーは、1967 年の著書『計算: 有限マシンと無限マシン』の「§ 10.6条件式: マッカーシー形式主義」で、「形式主義」を次のように説明しています。

「実用的なコンピュータ言語は、形式的な数学的処理には向いていません。つまり、記述する手順に関する定理を簡単に証明できるようには設計されていません。McCarthy [1963] の論文では、再帰関数の概念の実用的な側面を強化しながら、その数学的な明瞭さを維持し、改善する形式主義が見つかりました。¶ McCarthy は、次の形式の「条件式」を導入しています。

f = (もし p ₁ ならば e ₁ そうでなければ e ₂ )

ここで、e _{i は}式であり、p _{1 は}真または偽の可能性があるステートメント（または方程式）です。¶ この式は

p _{1 が}真かどうかを確認します。真であれば、 fの値はe ₁で与えられます。

p1が偽の場合、 fの値はe ₂で与えられます。

この条件式には、最小化演算子の力もあります。

マッカーシー形式論は、いくつかの基本関数、合成、および等式に基づいている点で一般的な再帰的（クリーネ）システムに似ていますが、条件式のみが原始再帰スキームと最小化演算子の両方を置き換えます。（ミンスキー 1967:192-193）

ミンスキーは、その実証において以下の演算子を使用している。^[2]

ゼロ
後継
数の平等
合成（置換、置き換え、代入）^[3]
条件式

これらから、彼は先行関数 (つまり DECREMENT)を導出する方法を示します。このツールを使用して、彼は「一般的な」再帰と原始再帰定義に必要な最小化演算子を導出します。

IF-THEN-ELSE の CASE 演算子への拡張

1952 年の著書『メタ数学入門』 で、スティーブン・クリーネは原始再帰関数が何を意味するのかを定義しています。

「関数

φ

が

ψ

1

, ..., ψ

k

(以下Ψ )において原始再帰的 であるとは、関数 (の発生) の有限シーケンス

φ

1

, ..., φ

k

が存在し、シーケンスの各関数が関数Ψ (想定される関数) の 1 つ、最初の関数、または前の関数の直接の従属関数のいずれかであり、最後の関数

φ

k

が

φ

である場合をいう。」(Kleene 1952:224)

言い換えれば、"基底"関数（0などの定数でもよい）が与えられた場合、原始再帰は基底関数または関数の以前の値のいずれかを使用して関数の値を生成します。原始再帰は数学的帰納法と呼ばれることもあります。

Minsky (上記) は、2 つの CASE 演算子について説明しています。ネストされたIF-THEN-ELSE (「case ステートメント」(または「switch ステートメント」)) が原始的な再帰であることのデモンストレーションは、Kleene 1952:229 ^[4]の「#F (「相互に排他的な述語」)」に記載されています。CASE 演算子は論理マルチプレクサのように動作し、AND-OR-SELECT と呼ばれることもあるより単純な 2 つのケースの論理演算子の単なる拡張です (詳細は命題式を参照)。3 つのケースの CASE 演算子は、次のように言葉で説明されます。「X が CASE 1 の場合は「p」を実行し、そうでない場合は X が CASE 2 の場合は「q」を実行し、そうでない場合は X が CASE「3」の場合は「r」を実行し、そうでない場合は「default」を実行します。」

Boolos-Burgess-Jeffrey 2002 は、特定のインスタンスでは、CASE 演算子、つまりネストされた IF-THEN-ELSE ステートメントのシーケンスは、相互に排他的(つまり、1 つの「ケース」のみが成立する (真である)) かつ集合的に網羅的(つまり、すべての可能な状況または「ケース」が「カバーされる」) でなければならないと述べています。これらの要件は、命題論理の決定性の結果です。正しく実装するには、真理値表とカルノーマップを使用してケースを指定および簡略化する必要があります。詳細については、命題式を参照してください。著者は、「ケースによる定義」の威力を次のように指摘しています。

「...より複雑な例では、ケースによる定義によって、重要な関数の (原始的な) 再帰性を確立することがはるかに容易になります。これは主に、古い関係から新しい関係を定義するためのさまざまなプロセスがあり、それらを (原始的な) 再帰関係に適用すると、新しい (原始的な) 再帰関係が生成されることが示されるためです。」(Boolos-Burgess-Jeffrey 2002:74)

彼らは特に、置換、グラフ関係（変数のリストから特定の変数（の値）を取り出す恒等関係に似ている）、否定（論理否定）、連言（論理積）、選言（論理和）、有界全称量化、または有界存在量化のプロセスを、事例による定義と一緒に使用して、新しい原始再帰関数を作成できることを証明しています（Boolos-Burgess-Jeffrey 2002:74-77 を参照）。

参照

注記

^ マッカーシー 1960年。
^ミンスキー（1967）は 原始再帰関数の記述に恒等演算子を含めていない。その理由は不明である。
^ さまざまな著者がこの操作にさまざまな名前を使用しています。Kleene はこれを「置換による定義のスキーム」と呼んでいます。 ψ の変数を χ ₁、...、χ _mの曖昧な値の式で置換することによって、 φ の曖昧な値を表す式が得られます。このスキームの適用によって定義された関数 φ は、時々 st S _mⁿ (ψ, ₁、...、χ _m ) と書きます。(Kleene 1952:220)。Knuth はこれを「最も重要な置換操作 (代入または置換と呼ばれることもあります)」と名付け、それを「←」矢印で表します。たとえば、「m ← n」は、変数mの値が変数nの現在の値で置き換えられることを意味します(cf Knuth 1973:3)。
^
Kleene の 5 つの基本再帰「スキーマ」には次のものが含まれます。
1. ゼロ定数: 0 または 0 の可能性がある()
2. 後継: $S (0) = "1"、 S (1) = "2"、$ など。
3. 投影: $U i n (x 1, ..., x n) = x i$ 、 $x i$ は計算全体を通じて固定された「パラメーター」であり、 $U i n は$ それらの 1 つを投影します。 $π i n (x 1, ..., x n) = x i$ という表記も使用されます。
4. 置換 $φ(x 1, ..., x n) = ψ(χ 1 (x 1, ..., x n), ..., χ m (x 1, ..., x n))$
5. 原始再帰。Kleene 1952:219 を参照。

参考文献

マッカーシー、ジョン（1960）。「記号式の再帰関数と機械による計算、パートI」。Communications of the ACM。3（4）：184–195。doi ：10.1145 / 367177.367199。
George S. Boolos、John P. Burgess、Richard C. Jeffrey、2002、「Computability and Logic: Fourth Edition」、Cambridge University Press、Cambridge UK、ISBN 0-521-00758-5ペーパーバック。
ジョン・マッカーシー（1963）「計算の数学的理論の基礎」、コンピュータプログラミングと形式システム、pp.33-70。
マービン・ミンスキー(1967)、「計算：有限マシンと無限マシン」、Prentice-Hall Inc、ニュージャージー州エングルウッドクリフス。

[FOOTNOTEMcCarthy1960-1] マッカーシー 1960年。

[2] ^ミンスキー（1967）は 原始再帰関数の記述に恒等演算子を含めていない。その理由は不明である。

[3] さまざまな著者がこの操作にさまざまな名前を使用しています。Kleene はこれを「置換による定義のスキーム」と呼んでいます。 ψ の変数を χ ₁、...、χ _mの曖昧な値の式で置換することによって、 φ の曖昧な値を表す式が得られます。このスキームの適用によって定義された関数 φ は、時々 st S _mⁿ (ψ, ₁、...、χ _m ) と書きます。(Kleene 1952:220)。Knuth はこれを「最も重要な置換操作 (代入または置換と呼ばれることもあります)」と名付け、それを「←」矢印で表します。たとえば、「m ← n」は、変数mの値が変数nの現在の値で置き換えられることを意味します(cf Knuth 1973:3)。

[4] Kleene の 5 つの基本再帰「スキーマ」には次のものが含まれます。
ゼロ定数: 0 または 0 の可能性がある()
後継: $S (0) = "1"、 S (1) = "2"、$ など。
投影: $U i n (x 1, ..., x n) = x i$ 、 $x i$ は計算全体を通じて固定された「パラメーター」であり、 $U i n は$ それらの 1 つを投影します。 $π i n (x 1, ..., x n) = x i$ という表記も使用されます。
置換 $φ(x 1, ..., x n) = ψ(χ 1 (x 1, ..., x n), ..., χ m (x 1, ..., x n))$
原始再帰。Kleene 1952:219 を参照。

[5] ゼロ定数: 0 または 0 の可能性がある()

[6] 後継: $S (0) = "1"、 S (1) = "2"、$ など。

[7] 投影: $U i n (x 1, ..., x n) = x i$ 、 $x i$ は計算全体を通じて固定された「パラメーター」であり、 $U i n は$ それらの 1 つを投影します。 $π i n (x 1, ..., x n) = x i$ という表記も使用されます。

[8] 置換 $φ(x 1, ..., x n) = ψ(χ 1 (x 1, ..., x n), ..., χ m (x 1, ..., x n))$

[9] 原始再帰。Kleene 1952:219 を参照。

[10] ゼロ定数: 0 または 0 の可能性がある()

[11] 後継: $S (0) = "1"、 S (1) = "2"、$ など。

[12] 投影: $U i n (x 1, ..., x n) = x i$ 、 $x i$ は計算全体を通じて固定された「パラメーター」であり、 $U i n は$ それらの 1 つを投影します。 $π i n (x 1, ..., x n) = x i$ という表記も使用されます。

[13] 置換 $φ(x 1, ..., x n) = ψ(χ 1 (x 1, ..., x n), ..., χ m (x 1, ..., x n))$

[14] 原始再帰。Kleene 1952:219 を参照。