チューリング計算可能性とは? わかりやすく解説

Weblio 辞書 > 辞書・百科事典 > ウィキペディア小見出し辞書 > チューリング計算可能性の意味・解説 

チューリング計算可能性

出典: フリー百科事典『ウィキペディア(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を入力したとき停止するチューリングマシン(についての記述)の集合だが、計算不可能な集合のよく知られた例である。計算不可能な集合多数存在することは、次の事実から明らかである。つまり、チューリングマシン枚挙可能(可算)な個数しか存在しないから、計算可能集合枚挙可能な個数しか存在しないが、自然数から作る集合枚挙不可能(非可算)な数だけ存在する停止問題計算可能ではないが、プログラムの実行シミュレートし、実際に停止するプログラムの無限のリスト作成することは可能である。すなわち、停止問題帰納的可算集合計算枚挙可能、半決定可能などとも)の例であり、チューリングマシンによって枚挙可能な集合である。同様に、ある集合帰納的可算であることの必要十分条件は、それが空であるか、または何らかの計算可能関数値域等しいことである。帰納的可算集合一般に決定不能だが、再帰理論が最も詳しく研究してきた領域である。

※この「チューリング計算可能性」の解説は、「再帰理論」の解説の一部です。
「チューリング計算可能性」を含む「再帰理論」の記事については、「再帰理論」の概要を参照ください。

ウィキペディア小見出し辞書の「チューリング計算可能性」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。 お問い合わせ



英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「チューリング計算可能性」の関連用語

チューリング計算可能性のお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



チューリング計算可能性のページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
ウィキペディアウィキペディア
Text is available under GNU Free Documentation License (GFDL).
Weblio辞書に掲載されている「ウィキペディア小見出し辞書」の記事は、Wikipediaの再帰理論 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。

©2025 GRAS Group, Inc.RSS