ここでは主に ChatGPT を使って調べています。説明してくれるため単に検索するよりキーワードにたどり着きやすいと思われるのですが、この件はなかなかキーワードにたどり着きません。
- (1) 有限長のリストを返す関数
- (2) 無限長のリストを返す関数(変更可能な変数がない)
- (3) 無限長のリストを返す関数(変更可能な変数がある)
が異なることを示すために、帰納的関数の理論の何かに対応させます。その何かは関数ではないので何と言えば良いかよくわかりませんが「写像の集合」のようなものと考えられます。対角線論法で示すことができると考えられます(小数・実数・実数の集合に対応)。以前は実行順序で分類するということを試みていましたが、それを「写像の集合」の形に書き直すことも考えていきます。この議論によって
ということを示すのが目標です。
これを示すために関数型言語のようなプログラミング言語を定義します。これは F# 形式と C# 形式でも定義します。
(3) を (1) の無限列で表すことによって自動アップデートを実現します。例えば、将棋ではパターンは有限で、パターンの間の関係を調べることにより(詳細は知らないのですが)機械学習でアップデートできます。それと同様の手法で (1) のパターンの間の関係を調べることによって自動的にアップデートすることを考えます。
手がかりがないのでいったん ChatGPT で調べてみました。
- (1) 有限長のリストを返す関数
- (2) 無限長のリストを返す関数(変更可能な変数がない)
- (3) 無限長のリストを返す関数(変更可能な変数がある)
について、計算理論の帰納的関数の分類、帰納的関数ではないものの分類の中で(1)、(2)、(3)のそれぞれが当てはまるものはありますか
と入力すると以下の結果となりました。recursively enumerable の分類はできないのでしょうか。
計算理論の観点から、(1)、(2)、(3) の関数がどのように分類されるかを考えてみます。
(1) 有限長のリストを返す関数
この場合、関数の出力は常に有限なデータ列なので、チューリング機械や帰納的関数の枠組みで扱うことができます。
- 一般的なプログラミング言語の決定的な関数（例えば F# や Haskell で `List
-> List ` のような型を持つ関数）が有限長のリストを返す場合、その計算は全域帰納的関数（total recursive function）に含まれる可能性が高いです。 - ただし、関数が停止しない可能性がある場合（例えば停止性が不明な計算を伴う場合）、部分帰納的関数（partial recursive function）になります。
分類:
(2) 無限長のリストを返す関数 (変更可能な変数がない)
変更可能な変数を持たずに無限長のリストを返す関数は、遅延評価（lazy evaluation）のような仕組みを用いることが一般的です。例えば、Haskell の `stream = 1 : map (+1) stream` のように無限リストを作る場合があります。
このような関数は、理論的には停止しない部分帰納的関数に分類されることが多いです。
- ある時点で生成されたリストの有限部分（例えば最初の `n` 要素）を返す関数は帰納的（計算可能）ですが、全体の無限リストを一度に出力することはできません。
- 実際の計算機上では、無限リストを遅延的に生成するため、任意の有限部分を計算できるとはいえ、全体を完全に計算することは不可能です。
分類:
(3) 無限長のリストを返す関数 (変更可能な変数がある)
変更可能な変数を持つ場合、状態を更新しながら無限リストを生成することができます。例えば、Python のジェネレータや F# の `Seq.unfold` を使うと、状態を持つ形でストリームを生成できます。
- 変更可能な変数があることで、関数の振る舞いはチューリング完全な計算モデルの一部となり得ます。
- 例えば `while` ループを用いた無限リストの生成は、明らかに停止しない計算と関係があります。
- しかし、変更可能な変数があるからといって、計算理論上の分類が大きく変わるわけではなく、結局のところ「無限リストの有限部分を計算できる」という性質は (2) と変わりません。
分類:
まとめ
種類 停止性 変更可能な変数 計算理論上の分類 (1) 有限長のリストを返す関数 必ず停止 (または停止しない) なし/あり 全域帰納的関数（停止するなら） / 部分帰納的関数（停止しない可能性があるなら） (2) 無限長のリストを返す関数 (変更可能な変数なし) 停止しない なし 部分帰納的関数（有限部分は計算可能） / 帰納的でない関数（無限全体として見た場合） (3) 無限長のリストを返す関数 (変更可能な変数あり) 停止しない あり 部分帰納的関数（有限部分は計算可能） / 帰納的でない関数（無限全体として見た場合） 補足
無限長のリストを返す関数が、有限の入力を受け取る場合でも、常に無限長の出力を持つならば、関数全体としては「計算可能関数」として扱いにくくなります。このような場合、通常は帰納的可算（recursively enumerable） な性質を考えるのが自然です。有限の部分は計算可能ですが、全体としての計算が完了することはありません。
