チューリング計算可能性
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/06/24 05:44 UTC 版)
再帰理論における計算可能性の研究はチューリング（1936）に端を発している。自然数の集合と自然数 n を考える。n がその集合の元なら 1 を返して停止し、そうでないなら 0 を返して停止するチューリングマシンが存在するなら、その集合は帰納的集合（または、決定可能集合、計算可能集合、チューリング計算可能集合とも）と呼ばれる。自然数から自然数への関数 f があるとする。任意の自然数 n を入力されたときに f(n) を出力して停止するチューリングマシンが存在するとき、その関数を再帰関数あるいは（チューリング）計算可能関数と呼ぶ。ここでは定義に必ずしもチューリングマシンを持ち出す必要はない。チューリングマシンと同等の能力を持つ計算模型は他にも存在する（例えば、原始再帰関数とμ作用素からなるμ再帰関数）。 再帰関数と集合に関する用語は完全に一定しているわけではない。μ再帰関数による定義や、ゲーデルによる rekursiv（再帰）関数の定義から、伝統的に「再帰的; recursive」という言葉でチューリングマシンで計算可能な集合や関数を意味するようになった。「決定可能; decidable」という用語はチューリングらが論文で使っていたドイツ語 Entscheidungsproblem に由来する。現在では「計算可能関数; computable function」という用語には様々な定義がある。Cutland（1980）によればそれは部分再帰関数（入力値によっては動作が未定義となる関数）を意味し、Soare（1987）によれば、それは全域再帰関数（一般再帰関数）を意味する。この記事では後者の意味で用いる。Soare（1996）には、他にも用語についてのコメントがある。 自然数の集合は常に計算可能という訳ではない。チューリングマシンの停止問題は、0を入力したとき停止するチューリングマシン（についての記述）の集合だが、計算不可能な集合のよく知られた例である。計算不可能な集合が多数存在することは、次の事実から明らかである。つまり、チューリングマシンは枚挙可能（可算）な個数しか存在しないから、計算可能集合も枚挙可能な個数しか存在しないが、自然数から作る集合は枚挙不可能（非可算）な数だけ存在する。 停止問題は計算可能ではないが、プログラムの実行をシミュレートし、実際に停止するプログラムの無限のリストを作成することは可能である。すなわち、停止問題は帰納的可算集合（計算枚挙可能、半決定可能などとも）の例であり、チューリングマシンによって枚挙可能な集合である。同様に、ある集合が帰納的可算であることの必要十分条件は、それが空であるか、または何らかの計算可能関数の値域に等しいことである。帰納的可算集合は一般には決定不能だが、再帰理論が最も詳しく研究してきた領域である。
※この「チューリング計算可能性」の解説は、「再帰理論」の解説の一部です。
「チューリング計算可能性」を含む「再帰理論」の記事については、「再帰理論」の概要を参照ください。
- チューリング計算可能性のページへのリンク
