フリードバーグ・ナンバリング
フリードバーグ・ナンバリングは、帰納的関数や帰納的可算集合に対して、重複なく一意に対応させるナンバリング（枚挙）の一種です。このナンバリングは、1958年にリチャード・フリードバーグによって、0'-優先法という手法を用いてその存在が証明されました。その後、1990年にはマルティン・クンマーが優先法を用いない別の構成法を提案しています。
フリードバーグ・ナンバリングは、通常のアクセプタブル・ナンバリングとは異なる、いくつかの重要な性質を持っています。
アクセプタブル・ナンバリングはPadding lemmaにより、単射ではありません。つまり、一つの帰納的関数に対して、無限個の指標が存在します。しかし、フリードバーグ・ナンバリングは単射であるため、各関数に一意の指標が対応します。これが、フリードバーグ・ナンバリングの大きな特徴です。
Smn定理が成立するナンバリングはアクセプタブルであるため、フリードバーグ・ナンバリングにはSmn定理が成立しません。同様に、クリーネの再帰定理も成立しません。これは、以下の矛盾を示すことで証明できます。
もし、フリードバーグ・ナンバリング \( \varphi \) に対して再帰定理が成立すると仮定します。\( f(x) = x + 1 \) という全域帰納的関数を考えると、再帰定理から \( \varphi_e = \varphi_{f(e)} \) となる自然数 \( e \) が存在するはずです。しかし、フリードバーグ・ナンバリングは単射であるため、\( e = f(e) \) 、つまり \( e = e + 1 \) が成り立ち、これは矛盾です。
アクセプタブル・ナンバリングに対しては、ライスの定理が成立します。例えば、2つの自然数が同じ関数の指標であるかどうかは決定不能です。しかし、フリードバーグ・ナンバリングは単射であるため、2つの自然数が同じ関数の指標であるかどうかは決定可能です。したがって、フリードバーグ・ナンバリングにはライスの定理は成立しません。
ナンバリング全体の集合は、還元可能性によって上半束の構造を持ちます。これをロジャース半束といいます。\( \varphi \) をフリードバーグ・ナンバリングとし、\( \psi \) を \( \varphi \) に還元可能なナンバリング、\( f \) をその還元関数とします。このとき、\( \psi_i = \varphi_{f(i)} \) が成り立ちます。
\( g(i) = \mu j . (f(j) = i) \) なる帰納的関数 \( g \) を考えると、\( \varphi \) が全単射であること、\( \psi \) が全射であることから、\( f \) は全射でなければなりません。したがって、\( g \) は全域的です。
そして、\( \psi_{g(i)} = \varphi_{f(g(i))} = \varphi_i \) であるため、\( \varphi \) は \( \psi \) に還元可能です。このことから、フリードバーグ・ナンバリングは還元可能性に関して極小であると言えます。
標準的なナンバリングからフリードバーグの方法で得られるフリードバーグ・ナンバリングの他に、還元可能性の意味で同値でない別のナンバリングが存在します。したがって、ロジャース半束は束ではありません。これは、比較不能な2つの極小元が存在し、それらの交わり（下限）が存在しないためです。
フリードバーグ・ナンバリングは、単射性という特徴を持つため、アクセプタブル・ナンバリングとは異なる性質を持ちます。Smn定理や再帰定理、ライスの定理が成立せず、ロジャース半束においては極小元となります。これらの性質は、計算可能性理論における重要な概念を理解する上で役立ちます。
ナンバリング
ゲーデル数
Nigel Cutland (1980), Computability: An Introduction to Recursive Function Theory, Cambridge University Press. ISBN 9780521294652.
Richard M. Friedberg (1958), Three Theorems on Recursive Enumeration. I. Decomposition. II. Maximal Set. III. Enumeration Without Duplication, Journal of Symbolic Logic 23:3, pp. 309–316.
Martin Kummer (1990), An easy priority-free proof of a theorem of Friedberg, Theoretical Computer Science 74(2), pp. 249-251.
Marian B. Pour-El (1964), Gödel Numberings Versus Friedberg Numberings, Proceedings of the American Mathematical Society 15(2), pp. 252-256.
Nikolaj K. Vereščagin and A. Shen (2003), Computable Functions, American Mathematical Soc.
Institute of Mathematics
フリードバーグ・ナンバリングの性質
フリードバーグ・ナンバリングは、通常のアクセプタブル・ナンバリングとは異なる、いくつかの重要な性質を持っています。
単射性
アクセプタブル・ナンバリングはPadding lemmaにより、単射ではありません。つまり、一つの帰納的関数に対して、無限個の指標が存在します。しかし、フリードバーグ・ナンバリングは単射であるため、各関数に一意の指標が対応します。これが、フリードバーグ・ナンバリングの大きな特徴です。
Smn定理と再帰定理
Smn定理が成立するナンバリングはアクセプタブルであるため、フリードバーグ・ナンバリングにはSmn定理が成立しません。同様に、クリーネの再帰定理も成立しません。これは、以下の矛盾を示すことで証明できます。
もし、フリードバーグ・ナンバリング \( \varphi \) に対して再帰定理が成立すると仮定します。\( f(x) = x + 1 \) という全域帰納的関数を考えると、再帰定理から \( \varphi_e = \varphi_{f(e)} \) となる自然数 \( e \) が存在するはずです。しかし、フリードバーグ・ナンバリングは単射であるため、\( e = f(e) \) 、つまり \( e = e + 1 \) が成り立ち、これは矛盾です。
ライスの定理
アクセプタブル・ナンバリングに対しては、ライスの定理が成立します。例えば、2つの自然数が同じ関数の指標であるかどうかは決定不能です。しかし、フリードバーグ・ナンバリングは単射であるため、2つの自然数が同じ関数の指標であるかどうかは決定可能です。したがって、フリードバーグ・ナンバリングにはライスの定理は成立しません。
ロジャース半束における極小性
ナンバリング全体の集合は、還元可能性によって上半束の構造を持ちます。これをロジャース半束といいます。\( \varphi \) をフリードバーグ・ナンバリングとし、\( \psi \) を \( \varphi \) に還元可能なナンバリング、\( f \) をその還元関数とします。このとき、\( \psi_i = \varphi_{f(i)} \) が成り立ちます。
\( g(i) = \mu j . (f(j) = i) \) なる帰納的関数 \( g \) を考えると、\( \varphi \) が全単射であること、\( \psi \) が全射であることから、\( f \) は全射でなければなりません。したがって、\( g \) は全域的です。
そして、\( \psi_{g(i)} = \varphi_{f(g(i))} = \varphi_i \) であるため、\( \varphi \) は \( \psi \) に還元可能です。このことから、フリードバーグ・ナンバリングは還元可能性に関して極小であると言えます。
ロジャース半束における非束性
標準的なナンバリングからフリードバーグの方法で得られるフリードバーグ・ナンバリングの他に、還元可能性の意味で同値でない別のナンバリングが存在します。したがって、ロジャース半束は束ではありません。これは、比較不能な2つの極小元が存在し、それらの交わり（下限）が存在しないためです。
まとめ
フリードバーグ・ナンバリングは、単射性という特徴を持つため、アクセプタブル・ナンバリングとは異なる性質を持ちます。Smn定理や再帰定理、ライスの定理が成立せず、ロジャース半束においては極小元となります。これらの性質は、計算可能性理論における重要な概念を理解する上で役立ちます。
関連項目
ナンバリング
ゲーデル数
参考文献
Nigel Cutland (1980), Computability: An Introduction to Recursive Function Theory, Cambridge University Press. ISBN 9780521294652.
Richard M. Friedberg (1958), Three Theorems on Recursive Enumeration. I. Decomposition. II. Maximal Set. III. Enumeration Without Duplication, Journal of Symbolic Logic 23:3, pp. 309–316.
Martin Kummer (1990), An easy priority-free proof of a theorem of Friedberg, Theoretical Computer Science 74(2), pp. 249-251.
Marian B. Pour-El (1964), Gödel Numberings Versus Friedberg Numberings, Proceedings of the American Mathematical Society 15(2), pp. 252-256.
Nikolaj K. Vereščagin and A. Shen (2003), Computable Functions, American Mathematical Soc.
外部リンク
Institute of Mathematics
もう一度検索
【記事の利用について】
タイトルと記事文章は、記事のあるページにリンクを張っていただければ、無料で利用できます。
※画像は、利用できませんのでご注意ください。
【リンクついて】
リンクフリーです。