|
===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 ・ 再 ： [さい] 1. (pref) re- 2. again 3. repeated ・ 再帰 ： [さいき] (n) recursive ・ 理 ： [り] 【名詞】 1. reason ・ 理論 ： [りろん] 【名詞】 1. theory ・ 論 ： [ろん] 【名詞】 1. (1) argument 2. discussion 3. dispute 4. controversy 5. discourse 6. debate 7. (2) theory 8. doctrine 9. (3) essay 10. treatise 1 1. comment
再帰理論（さいきりろん、）は、数理論理学の一分野で、1930年代の計算可能関数とチューリング次数の研究が源となっている。発展の過程で、この分野は計算可能性や定義可能性全般を対象に含むようになった。これらの領域においては、再帰理論は証明論や effective 記述集合論(en)とも密接に関係する。 再帰理論の根本的疑問は「自然数から自然数への関数が計算可能であるとはどういう意味か?」と、「計算不能関数は、その計算不能性のレベルに基づいて階層分けできるか?」である。これらの疑問への答えを探す過程で豊かな理論が生まれ、現在でも活発な研究が行われている。 数理論理学における再帰理論の研究者がよく扱うのは、この記事で触れる相対的な計算可能性、還元性の概念、次数構造などである。これらは、計算機科学における計算可能性理論が、計算複雑性理論、形式手法、形式言語などを主な研究対象とすることと対照を成す。これら二つの研究コミュニティには知識と手法の面で重なる部分が多々あり、はっきりした境界を引くことは出来ない。 == 計算可能集合と計算不可能集合 == 再帰理論は、1930年代のクルト・ゲーデル、アロンゾ・チャーチ、アラン・チューリング、スティーヴン・コール・クリーネ、エミール・ポストらの研究に端を発している。〔彼らの基本的な論文の多くは Martin Davis ''The Undecidable'' (1965) に集成されている。〕 彼らの基本的な成果を通じて、チューリング計算可能性という概念が樹立された。これは計算の実効性という非形式的な概念に正しい形式化を与えるものである。そこからスティーヴン・クリーネ（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)はこの分野の成果を多数紹介している。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「再帰理論」の詳細全文を読む スポンサード リンク
|