計算可能集合と計算不可能集合
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/06/24 05:44 UTC 版)
「再帰理論」の記事における「計算可能集合と計算不可能集合」の解説
再帰理論は、1930年代のクルト・ゲーデル、アロンゾ・チャーチ、アラン・チューリング、スティーヴン・コール・クリーネ、エミール・ポストらの研究に端を発している。 彼らの基本的な成果を通じて、チューリング計算可能性という概念が樹立された。これは計算の実効性という非形式的な概念に正しい形式化を与えるものである。そこからスティーヴン・クリーネ（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)はこの分野の成果を多数紹介している。
※この「計算可能集合と計算不可能集合」の解説は、「再帰理論」の解説の一部です。
「計算可能集合と計算不可能集合」を含む「再帰理論」の記事については、「再帰理論」の概要を参照ください。
- 計算可能集合と計算不可能集合のページへのリンク
