関数プログラミングの帰納的関数(5) - 非専門的シンギュラリティー研究所

F# の終了しない関数と「帰納的関数」の関係はまだよくわかりません。そこで終了しない関数を終了する関数で表すことについて ChatGPT で調べてみました。以下のように入力しました。

F# の再帰的呼び出しで無限に繰り返される関数を $f$ とします(再帰的呼び出し以外は有限回で終わるとする)。
$f$ の定義中の再帰的呼び出しは一度とし、その結果の先頭に要素を一つ追加して、 $f$ は無限リストを返すとします。

関数の列 $f_n$ を

$f_0$ は空リストを返す

$f_{n+1}$ を $f$ の定義の $f$ の呼び出しを $f_n$ で置き換えたもの

とします。

$f_n$ の結果と $f$ の結果の最初の $n$ 項を比較してください

と入力すると以下の結果となりました。

この問題は、F# の関数 $f$ とその有限近似 $f_n$ の関係について考えるもので、特に無限リストを有限回の近似で表現する方法に関する興味深い問題です。以下に、問題の構造と答えを整理します。

問題の設定

1. 関数 $f$ は無限リストを生成します。
定義中で 1回だけ再帰的に自分自身を呼び出す。
再帰呼び出しの結果の先頭に 要素を1つ追加 して無限リストを生成します。
2. 関数の列 $f_n$ は次のように定義されます：
$f_0$ : 空リストを返す。
$f_{n+1}$ : $f$ の定義中での再帰呼び出し $f$ を、前の段階の $f_n$ で置き換えたもの。

$f_n$ の結果と $f$ の結果の比較

$f_n$ : 長さ $n$ の有限リスト。

$f$ : 無限リスト。

1. $f_1$ の場合：

$f_1$ は $f_0$ を基に構築されます。

$f_0$ は空リスト。

$f_1$ は空リストの先頭に1つの要素を追加するだけなので、1つの要素を持つリストになります。

結果： $f_1$ は $f$ の最初の1項と一致する。

2. $f_2$ の場合：

$f_2$ は $f_1$ を基に構築されます。

$f_1$ は長さ1のリスト。

$f_2$ は $f_1$ のリストに要素を追加する形で作られる。

結果： $f_2$ は $f$ の最初の2項と一致する。

3. 一般の場合 $f_n$ ：

$f_n$ は $f$ の定義での再帰呼び出しを有限回展開したものです。

$f_n$ は $f$ の最初の $n$ 項を生成する。

無限リスト $f$ の最初の $n$ 項は $f_n$ に完全に一致する。

結論

関数 $f_n$ の結果と無限リスト $f$ の最初の $n$ 項は常に一致します。
つまり、 $f_n$ を増やすことで $f$ の無限リストを逐次的に近似できることがわかります。

これをフィボナッチ数列に適用してください

と入力すると以下の結果となりました。

フィボナッチ数列を求める関数を $f$ の形に適用し、近似列 $f_n$ を構築してみます。
1. フィボナッチ数列の無限リスト

通常、フィボナッチ数列は以下の漸化式で定義されます：
$\displaystyle F_0 = 0, \quad F_1 = 1, \quad F_n = F_{n-1} + F_{n-2} \quad (n \geq 2)$
F# では 無限リスト (lazy sequence) を使って次のように表現できます：
let rec fibs = seq {
    yield 0
    yield 1
    yield! Seq.map2 (+) fibs (Seq.skip 1 fibs)
}
この `fibs` は無限に続くフィボナッチ数列を表します。
2. $f$ の形に変形

問題の形式に合わせて、無限リストを生成する関数 $f$ を考えます：

`f` は 自身を一度だけ再帰的に呼び出し、その結果の先頭に要素を1つ追加 します。

したがって、
$\displaystyle f = \lambda (). 0 :: 1 :: \text{zipWith}(+) f (\text{tail} f)$
という形になります。
F# で書くと：
let rec f () = seq {
    yield 0
    yield 1
    yield! Seq.map2 (+) (f()) (Seq.skip 1 (f()))
}
この `f()` は無限リストを返します。
3. $f_n$ の定義

関数列 $f_n$ を次のように定義します：

$f_0$ は空リスト `[]`。

$f_{n+1}$ は $f$ の再帰呼び出しを $f_n$ に置き換えたもの。

具体的に求めると：

$f_0 = []$

$f_1 = [0]$

$f_2 = [0; 1]$

$f_3 = [0; 1; 1]$

$f_4 = [0; 1; 1; 2]$

$f_5 = [0; 1; 1; 2; 3]$

$f_6 = [0; 1; 1; 2; 3; 5]$

...

つまり、
$f_n$ はフィボナッチ数列の最初の $n$ 項と一致する！

4. 結論

無限リスト $f()$ はフィボナッチ数列全体を生成する。

$f_n$ はフィボナッチ数列の最初の $n$ 項を含む有限リスト。

$f_n$ を増やしていくと、フィボナッチ数列に収束する！

$f_n$ を $f$ の「射影」として説明してください

と入力すると以下の結果となりました。

関数列 $f_n$ を無限リスト $f$ の「射影」として説明するために、数学的な観点から整理してみます。

1. 「射影」とは？

射影 (projection) とは、大きな対象 (例えば無限集合) から小さな対象 (有限集合) を取り出す操作のことです。
例えば、無限リスト $f$ に対して 最初の $n$ 項を取り出す関数 を考えると、それは $f$ を有限な部分に射影する操作になります。
このような射影を次のように定義します：
$\displaystyle P_n(f) = \text{take } n \text{ 項 from } f$
つまり、 $f$ の最初の $n$ 項を抜き出す関数 $P_n$ を考えると、 $f_n$ は
$\displaystyle f_n = P_n(f)$
という射影の形で表現できます。

2. $f_n$ の構築と射影

関数列 $f_n$ の定義を振り返ると：
1. $f_0 = []$ (空リスト)
2. $f_{n+1}$ は $f_n$ に1つ新しいフィボナッチ数を追加したもの
これを数学的に書き直すと：
$\displaystyle f_n = [F_0, F_1, \dots, F_{n-1}]$
これは無限リスト $f$ の最初の $n$ 項を取り出す操作 $P_n(f)$ に等しいです。
つまり、 $f_n$ は無限リスト $f$ の「有限部分への射影」になっている。

3. 射影の極限としての $f$

射影 $P_n(f)$ を無限に適用すると、最終的に元の無限リスト $f$ に収束します：
$\displaystyle \lim_{n \to \infty} P_n(f) = f$
これは、フィボナッチ数列の部分列が、全体のフィボナッチ数列に 一様収束 することを意味します。

4. 結論

$f_n$ は無限リスト $f$ の 最初の $n$ 項を取り出す射影 になっている。

射影演算 $P_n$ を適用すると、無限リストの有限近似が得られる。

$n \to \infty$ で $P_n(f)$ は元の $f$ に収束する。

したがって、 $f_n$ は $f$ の射影列として、無限リストの有限部分を捉えたものと解釈できる！