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

『数学基礎論　増補版』に書かれていた「半計算可能集合」という用語を検索したら「極限計算可能関数」という用語が出てきたので、「半計算可能集合」についても ChatGPT で調べてみます。

これらの概念はプログラミング言語の無限列を返す関数に使えそうですが、さらに適切な用語があるかもしれません。今後調査します。プログラミング言語の無名関数を返す関数は、帰納的関数なのかもしれませんが、無名関数から値を取得する関数として見ると帰納的関数ではないようです。

状態を持ち無限に動作するプログラムを、状態を持たないプログラムの列で表すことが目標なので、まずそれを調べていきます。

半計算可能集合とはどのようなものですか

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

半計算可能集合とは
半計算可能集合（semi-decidable set, $Σ_1^0$ 集合）とは、チューリング機械を用いた計算理論の概念であり、次のように定義されます。
ある集合 $A \subseteq \mathbb{N}$ （自然数の部分集合）が半計算可能であるとは、次のいずれかの同値な条件を満たすことを意味します：
1. 列挙可能性: $A$ は、あるチューリング機械によってすべての要素を出力できる（ただし、順番は保証されない）。つまり、あるチューリング機械 $M$ が存在して、入力なしで動作し、無限に計算を続ける過程で、ちょうど $A$ の要素すべてを（重複してもよい）出力する。

2. 半判定可能性: あるチューリング機械 $M$ が存在して、 $A$ の要素 $x$ を入力すると停止して "YES" と出力し、 $A$ に含まれない要素 $x$ に対しては停止しないか、無限ループに陥る（明示的に "NO" を出すとは限らない）。
3. 存在量化による定義（算術階層）: $A$ は、次のような形の述語で定義できる：
$\displaystyle x \in A \iff \exists y \; \varphi(x, y)$
ここで、 $\varphi(x, y)$ は決定可能（すなわち、あるチューリング機械が有限時間で計算できる）な述語である。

半計算可能集合の特徴

決定可能集合（recursive set）は、あるチューリング機械によってYES/NO 両方が有限時間で判定できる集合のこと。決定可能集合は半計算可能であり、かつその補集合も半計算可能（共半計算可能, co-semi-decidable）。

一般には、半計算可能だが決定可能でない集合が存在する（例: 停止問題の集合）。

半計算可能集合の補集合が半計算可能であるとは限らない。

例

1. 停止問題の集合
$\displaystyle K = \{ e \mid \text{プログラム } e \text{ は入力 } e \text{ で停止する} \}$
は半計算可能だが、決定可能ではない（チューリング不可解）。
2. ペアノ算術の証明可能な定理の集合

ある形式体系（例えばペアノ算術）の定理の集合は、ある計算機によってすべてを列挙できるため、半計算可能。

3. すべての素数の集合

ある数 $n$ が素数であるかどうかは有限時間で決定できるため、この集合は決定可能（したがって半計算可能）。

半計算可能集合と帰納的定義

ユーザーが興味を持っている「数式を帰納的に定義された構造として考える」という視点から見ると、半計算可能集合は帰納的に定義された構造の一種と見なせます。

帰納的定義とは、ある基本的な要素から出発し、再帰的な規則によって集合を拡張していくこと。

半計算可能集合は、チューリング機械が逐次的に要素を列挙するという形で定義できるため、帰納的に構成されていると解釈できる。

したがって、「帰納的に定義された数式の集合」を考える場合、半計算可能性は自然な制約となりうる概念です。