再帰理論
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2023/12/24 16:20 UTC 版)
![]() | この記事は、全部または一部が他の記事や節と重複しています。 具体的には計算可能性理論との重複です。 |
再帰理論(さいきりろん、英:Recursion theory)は、数理論理学の一分野で、1930年代の計算可能関数とチューリング次数の研究が源となっている。
発展の過程で、この分野は計算可能性や定義可能性全般を対象に含むようになった。これらの領域においては、再帰理論は証明論や エフェクティブ記述集合論(en)とも密接に関係する。
再帰理論の根本的疑問は「自然数から自然数への関数が計算可能であるとはどういう意味か?」と、「計算不能関数は、その計算不能性のレベルに基づいて階層分けできるか?」である。これらの疑問への答えを探す過程で豊かな理論が生まれ、現在でも活発な研究が行われている。
数理論理学における再帰理論の研究者がよく扱うのは、この記事で触れる相対的な計算可能性、還元性の概念、次数構造などである。これらは、計算機科学における計算可能性理論が、計算複雑性理論、形式手法、形式言語などを主な研究対象とすることと対照を成す。これら二つの研究コミュニティには知識と手法の面で重なる部分が多々あり、はっきりした境界を引くことは出来ない。
計算可能集合と計算不可能集合
再帰理論は、1930年代のクルト・ゲーデル、アロンゾ・チャーチ、アラン・チューリング、スティーヴン・コール・クリーネ、エミール・ポストらの研究に端を発している。[1]
彼らの基本的な成果を通じて、チューリング計算可能性という概念が樹立された。これは計算の実効性という非形式的な概念に正しい形式化を与えるものである。そこからスティーヴン・クリーネ(1952年)は、「チャーチのテーゼ」(Kleene 1952:300)と「チューリングのテーゼ」(p.376)という2つの用語を作った。現在では、これらはしばしばチャーチ=チューリングのテーゼという一つの仮説と看做されているが、これはアルゴリズムで計算可能な関数は如何なるものであろうと計算可能関数だ、と述べるものである。当初は懐疑的だった[要出典]ゲーデルも、1946年には賛同を示した。
- 「タルスキは彼の講義において、一般再帰性(またはチューリング計算可能性)が大変重要だと強調したが、これは正しいと思う。これが何故重要かと言えば、この考え方によって人が初めて、ある興味深い認識論的観念について、(特定の形式主義に囚われない様な)絶対的な観念を与えることに成功したから、という理由が大だと私には思える」(Gödel 1946 in Davis 1965: 84)
実効的な計算というものの定義に伴い、数学には実効的に決定できない問題があることを示す最初の一連の証明が得られた。チャーチ(1936a、1936b)とチューリング(1936)はゲーデルの不完全性定理の証明(1931)で用いられた技法に触発され、それぞれ独立に、ダフィット・ヒルベルトが1928年に提示した Entscheidungsproblem(決定問題)(en)が実効的に決定できないことを示した。この結果は、任意の数学的命題が真か偽かを正しく判定するアルゴリズムが存在しないことを明らかにした。
これらの初期の例に続いて、多くの数学問題が決定不能であることが示された。1947年、Markov とポストはそれぞれ独立に半群の word problem が実効的に決定できないことを示す論文を発表した。その結果に基づき、1950年代、Pyotr Sergeyevich Novikov (en)と William Boone はそれぞれ独立に群の word problem (en)が実効的に解けないことを示した。これは有限に表現された群におけるある語(word)が与えられたとき、その語が指す元がその群の単位元かどうかを実効的に決定する手続きが存在しないということである。1970年、ユーリ・マチャセビッチはマチャセビッチの定理(en)を証明し、その系としてヒルベルトの第10問題が実効的な解法を持たないことを示した。この問題は整数上で定義されたディオファントス方程式が整数解を持つかどうかを判定する手続きを求めるものであった。
何らかの数学的行為が実効的に実行できるかを問う研究は、ときに再帰数学と呼ばれることがある。Handbook of Recursive Mathematics (Ershov他、1998)はこの分野の成果を多数紹介している。
チューリング計算可能性
再帰理論における計算可能性の研究はチューリング(1936)に端を発している。自然数の集合と自然数 n を考える。n がその集合の元なら 1 を返して停止し、そうでないなら 0 を返して停止するチューリングマシンが存在するなら、その集合は帰納的集合(または、決定可能集合、計算可能集合、チューリング計算可能集合とも)と呼ばれる。自然数から自然数への関数 f があるとする。任意の自然数 n を入力されたときに f(n) を出力して停止するチューリングマシンが存在するとき、その関数を再帰関数あるいは(チューリング)計算可能関数と呼ぶ。ここでは定義に必ずしもチューリングマシンを持ち出す必要はない。チューリングマシンと同等の能力を持つ計算模型は他にも存在する(例えば、原始再帰関数とμ作用素からなるμ再帰関数)。
再帰関数と集合に関する用語は完全に一定しているわけではない。μ再帰関数による定義や、ゲーデルによる rekursiv(再帰)関数の定義から、伝統的に「再帰的; recursive」という言葉でチューリングマシンで計算可能な集合や関数を意味するようになった。「決定可能; decidable」という用語はチューリングらが論文で使っていたドイツ語 Entscheidungsproblem に由来する。現在では「計算可能関数; computable function」という用語には様々な定義がある。Cutland(1980)によればそれは部分再帰関数(入力値によっては動作が未定義となる関数)を意味し、Soare(1987)によれば、それは全域再帰関数(一般再帰関数)を意味する。この記事では後者の意味で用いる。Soare(1996)には、他にも用語についてのコメントがある。
自然数の集合は常に計算可能という訳ではない。チューリングマシンの停止問題は、0を入力したとき停止するチューリングマシン(についての記述)の集合だが、計算不可能な集合のよく知られた例である。計算不可能な集合が多数存在することは、次の事実から明らかである。つまり、チューリングマシンは枚挙可能(可算)な個数しか存在しないから、計算可能集合も枚挙可能な個数しか存在しないが、自然数から作る集合は枚挙不可能(非可算)な数だけ存在する。
停止問題は計算可能ではないが、プログラムの実行をシミュレートし、実際に停止するプログラムの無限のリストを作成することは可能である。すなわち、停止問題は帰納的可算集合(計算枚挙可能、半決定可能などとも)の例であり、チューリングマシンによって枚挙可能な集合である。同様に、ある集合が帰納的可算であることの必要十分条件は、それが空であるか、または何らかの計算可能関数の値域に等しいことである。帰納的可算集合は一般には決定不能だが、再帰理論が最も詳しく研究してきた領域である。
再帰理論の研究領域
上述のような再帰的な集合や関数の理論を出発点として、再帰理論は関連する主題を巻き込んで成長してきた。以下に挙げるのはそれぞれ独立した研究分野というわけではない。各分野は結果や考え方を相互に応用しており、再帰理論の研究者であればこれらの大半に親しんでいる。
相対計算可能性とチューリング次数
数理論理学における再帰理論は、伝統的に相対計算可能性(relative computability)に注目してきた。これは、チューリングが1939年に神託機械を使って定義したチューリング計算可能性を一般化したものである。神託機械は、普通のチューリングマシンにオラクルへの質問機能を加えた仮説的な機械である。オラクルは自然数の特別な集合であり、「n はオラクル集合の中にあるか?」という形式の問いにだけ答えることができる。その回答は、たとえそのオラクル集合が計算不可能であっても即座に行われる。従って、計算不可能なオラクルを持った神託機械は、オラクルなしでは計算不可能な集合を計算することができる。
非形式的に言えば、自然数の集合 A が集合 B にチューリング還元可能であるとは、B をオラクル集合として持つ神託機械を用いれば、ある数が A に属するかどうかを正しく示せることを意味する(この例では、集合 A は B から(相対的に)計算可能、 B について再帰的とも称する)。集合 A が集合 B にチューリング還元可能であり、かつ、B が A にチューリング還元可能であるとき、これらの集合は同じチューリング次数(「決定不能性の次数」とも)を持つと言う。ある集合のチューリング次数は、その集合の計算不能な度合いの正確な尺度となる。
計算不能な集合の自然な例として、さまざまな形の停止問題を符号化して得られる互いに異なる集合たちがあるが、それらには次のような共通点がある。
- それらは帰納的可算集合である。
- 多対一還元によって互いに変換可能である。すなわち、集合 A と B について、A = {x : f(x) ∈ B} となる計算可能関数 f が存在する。これらの集合を多対一同値(またはm-同値)であるという。
多対一還元はチューリング還元より強い。計算不能集合の自然な例は全て多対一同値だが、A を B にチューリング還元可能だが多対一還元不可能な帰納的可算集合 A と B を構築することもできる。すべての帰納的可算集合は停止問題に多対一還元可能であることが判っているので、多対一還元とチューリング還元の観点で、停止問題は最も複雑な帰納的可算集合である。1944年、ポストは、すべての帰納的可算集合は計算可能かあるいは停止問題にチューリング同値かのいずれかだろうか、という疑問を投げかけた。つまり、チューリング次数がこの2つの間になるような帰納的可算集合は存在するか、という問いである。
その問題を考える過程で、ポストは帰納的可算集合の分類として単純集合/超単純集合/超々単純集合といった自然な型を定義した。ポストはこれらの集合が、多対一還元の観点から見たとき、計算可能集合と停止問題の厳密に中間に位置することを示した。ポストはまた、チューリング還元よりも強い意味の還元(真理値表還元)を用いた場合においても、それらの一部が厳密に中間に位置することを示した。しかし、結局ポストは中間のチューリング次数を持つ帰納的可算集合が存在するかという主問題は未解決のまま残し、これはポストの問題(en)と呼ばれるようになった。10年後の1954年、クリーネとポストは計算可能集合と停止問題の間のチューリング次数が存在することは示せたが、そのチューリング次数に属する帰納的可算集合が存在するかは示せなかった。その直後、Friedberg と Muchnik がそれぞれ独立に中間次数の帰納的可算集合が存在することを示し、ポストの問題を解決した。この画期的な成果により、帰納的可算集合のチューリング次数に関する広範な研究が始まり、非常に複雑かつ自明でない構造の存在が明らかになった。
帰納的可算でない集合は非可算個存在しており、一般の集合のチューリング次数に関する研究も、帰納的可算なチューリング次数に関する研究と同様に、再帰理論における主要な研究対象である。様々な特定の次数が構成されている。
- hyperimmune-free degrees:この次数から相対的に計算可能な関数は(非相対化された)計算可能関数によって majorize される
- high degrees:この次数からは(全ての計算可能関数 g を支配するような)関数 f が相対的に計算可能。ここでいう支配とは、g に依存する定数 c が存在し、全ての x > c についてg(x) < f(x)が成り立つことを指す
- random degrees:アルゴリズム的ランダムな無限列が該当
- 1-generic degrees:1-generic集合の次数
- 極限再帰集合の停止問題より下の次数
任意のチューリング次数(帰納的可算とは限らない)の研究では、チューリングジャンプの研究が関係してくる。ある集合 A のチューリングジャンプとは、オラクル集合 A を持つ神託機械の停止問題を符号化した自然数の集合である。任意の集合のチューリングジャンプは、元の集合よりチューリング次数が常に高く、Friedberg の定理によって、停止問題を計算する任意の集合は別の集合のチューリングジャンプとなることが示されている。ポストの定理は、チューリングジャンプと算術的階層(算術における定義可能性に基づいて自然数の部分集合を分類したもの)との密接な関係を示している。
チューリング次数に関する近年の研究は、チューリング次数の集合の全体構造と、帰納的可算集合のチューリング次数の集合に注目してきた。Shore と Slaman (1999)の深い定理によれば、次数 x をそのチューリングジャンプの次数に変換するような関数は、チューリング次数のなす半順序の中で定義できる。Ambos-Spies and Fejer (2006) にそのような研究の歴史が概観されている。
還元可能性
チューリング還元可能性以外の還元可能性(reducibility)の研究も盛んである。ポスト(1944)は、真理値表還元可能性を含む強い還元可能性をいくつか提唱した。強い還元可能性を定義する神託付きチューリング機械は、付加されたオラクルがどういうものであろうと全域関数を計算する。弱い還元可能性とは、還元過程が必ずしも全てのオラクルで停止しない(つまり全域関数を計算しない)可能性があるものである。チューリング還元可能性は弱い還元可能性の一種である。
強い還元可能性には、次のものが含まれる。
- 一対一還元可能性
- A が B に一対一還元可能であるとは、全域計算可能な単射 f があり、n が A に属すことと f(n) が B に属すこととが同値になることをいう。
- 多対一還元可能性
- 一対一還元可能性とほぼ同じだが、f の単射性を仮定しない。
- 真理値表還元可能性
- A が B に真理値表還元可能であるとは、どんなオラクルに対しても全域関数を計算するような神託機械によってA が B にチューリング還元可能である場合を指す。神託の使用回数を制限したり、神託機械に条件を課すことで、様々な変種が得られる。それらも研究されている。
強い還元可能性に関する主要な研究においては、帰納的可算集合のクラスに対する理論と自然数からなる集合のクラスに対する理論との比較が行われてきた。さらに、各種還元可能性間の関係も研究されている。例えば、チューリング次数は真理値表次数であるか、または無限個の真理値表次数の和集合のどちらかであることが知られている。
チューリング還元可能性よりも弱い還元可能性(つまり、チューリング還元可能性を内包する還元可能性)も研究されている。よく知られている例として、算術的還元可能性と超算術的還元可能性がある。これらの還元可能性は、算術の標準モデルにおける定義可能性と密接に関連している。
ライスの定理と算術的階層
ライスの定理は、すべての自明でないクラス C(帰納的可算集合からなるクラスであって空でも全体でもないもの)において、インデックス集合 E = {e: e番目の帰納的可算集合 We が C に含まれる} を考えると、停止問題かその補問題が E に多対一還元可能という属性を持つことを示す。しかし、このようなインデックス集合の多くは停止問題以上に複雑である。このような集合は算術的階層によって分類される。例えば、すべての有限集合のクラスのインデックス集合 FIN の階層レベルは Σ2、すべての帰納的集合のクラスのインデックス集合 REC の階層レベルは Σ3、すべての補有限集合のクラスのインデックス集合 COFIN の階層レベルは Σ3、すべてのチューリング完全な集合のクラスのインデックス集合 COMP の階層レベルは Σ4 である。
逆数学
逆数学のプログラムは、二階算術の中の部分体系において、ある定理を証明するのにどの程度の集合存在公理が必要かを問うものである。この研究は Harvey Friedman が創始し、Stephen Simpson らが進めた。Simpson(1999)で、これに関する詳細が議論されている。対象となる集合存在公理は、自然数のべき集合が様々な還元可能性の概念の下で閉じていることを言う公理群とほぼ対応している。逆数学で研究されているそのような公理の中で最も弱いものは「再帰的内包公理; Recursive Comprehension Axiom」であり、これは自然数のべき集合はチューリング還元可能性の下で閉じているとするものである。
ナンバリング
再帰理論
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2022/08/08 05:41 UTC 版)
詳細は「再帰理論」を参照 再帰理論(計算可能性理論とも呼ばれる)は計算可能関数とチューリング次数(これは計算不可能関数を同じレベルの計算不可能性を持つ集合に分ける)の性質を研究する。再帰理論はまた一般計算可能性と定義可能性の研究を含む。再帰理論はアロンゾ・チャーチとアラン・チューリングによる1930年代の仕事(これはクリーネとポストによって1940年代に大きく拡張された)から生まれた。 古典再帰理論は自然数から自然数への関数の計算可能性に着目する。基本的な結果は、チューリング機械やラムダ計算やその他のシステムなど、多数の独立だが同値な特徴づけを持つ、ロバストかつカノニカルな計算可能関数のクラスを確立したことである。より高度な結果はチューリング次数の構造や帰納的可算集合の成す束に関するものである。 一般再帰理論は再帰理論の諸概念をもはや有限ではないような計算へと拡張する。そこには高階の型の計算可能性の研究や超算術的理論(英語版)や&alpha-再帰理論(英語版)などの分野を同様に含む。 再帰理論の現代的研究には、純粋な再帰理論の新しい結果と同様に、その応用研究(例えばアルゴリズム的ランダムネス、計算可能モデル理論(英語版)、逆数学など)が含まれる。
※この「再帰理論」の解説は、「数理論理学」の解説の一部です。
「再帰理論」を含む「数理論理学」の記事については、「数理論理学」の概要を参照ください。
固有名詞の分類
- 再帰理論のページへのリンク