帰納的関数の入門書『復刊 帰納的関数』を見ています。関数プログラミングの関数と帰納的関数を比較して分類する予定です。ChatGPT も使って調べていきます。
目次は以下のようになっています。
- 第4章 帰納的関数を定義する形式的体系
- 4.1 形式的体系R
- 4.2 形式的体系Rの算術化
- 4.3 T-述語と枚挙可能定理
- 4.4 標準形定理
- 第6章 決定不可能次数
- 6.1 決定不可能次数の概念
- 6.2 決定不可能次数の基本的構造
- 6.3 帰納的可算次数と算術的次数
- 6.4 完全次数
- 6.5 Postの問題とFriedberg-Мучникの定理
- 第7章 決定問題――ヒルベルトの第10問題を中心に――
まず第2章を見ていきたいと思いますが、その前に ChatGPT で調べてみます。
帰納的関数と原始帰納的関数について教えてください
と入力すると以下の結果となりました。
帰納的関数と原始帰納的関数は、計算理論や数理論理学で重要な概念です。これらは「計算可能性」や「関数の定義可能性」を形式的に捉えるために使われます。それぞれについて詳しく説明します。
1. 帰納的関数（Recursive Functions）
帰納的関数（または μ-帰納的関数）は、計算可能な関数のクラスを形式化したものです。このクラスには、以下のような特性を持つ関数が含まれます。
重要性
帰納的関数のクラスは、計算可能な関数すべてを表現します。具体的には、Turing Machine（チューリング機械）で計算可能なすべての関数が帰納的関数に対応します。
2. 原始帰納的関数（Primitive Recursive Functions）
原始帰納的関数は、帰納的関数のサブクラスで、再帰的な構造を持ちながらも「計算の終了が保証される」関数を表します。
定義
原始帰納的関数は、次の基本関数と操作によって構成されます：
1. 基本関数:
- 定数関数
- 後者関数
- 射影関数
2. 閉包操作:
- 合成: 既存の関数を組み合わせる。
- 原始再帰: 次の形式で関数を定義する。
ここでと
は既知の原始帰納的関数。
制約
原始帰納的関数には「最小化（μ演算）」が含まれないため、無限ループの可能性がなく、計算が必ず終了します。
