チャーチ=チューリングのテーゼとは? わかりやすく解説

Weblio 辞書 > 辞書・百科事典 > ウィキペディア小見出し辞書 > チャーチ=チューリングのテーゼの意味・解説 

チャーチ=チューリングのテーゼ

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2022/08/30 09:34 UTC 版)

チャーチ=チューリングのテーゼ (Church-Turing thesis) もしくはチャーチのテーゼ (Church's thesis) とは、「計算できる関数」という直観的な概念を、帰納的関数と呼ばれる数論的関数のクラスと同一視しようという主張である。テーゼの代わりに提唱(ていしょう)あるいは定立(ていりつ)の語が用いられることもある。このクラスはチューリングマシンで実行できるプログラムのクラス、ラムダ記法で定義できる関数のクラスとも一致する。よって簡単にはテーゼは、計算が可能な関数とは、その計算を実行できるような有限のアルゴリズムが存在するような関数、よっておおよそコンピュータで実行できる関数と同じだと主張する。




「チャーチ=チューリングのテーゼ」の続きの解説一覧

チャーチ=チューリングのテーゼ

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2016/02/29 16:21 UTC 版)

計算可能関数」の記事における「チャーチ=チューリングのテーゼ」の解説

詳細は「チャーチ=チューリングのテーゼ」を参照 チャーチ=チューリングのテーゼは、上述3つの特性を持つ手続き計算可能な関数計算可能関数であると主張したものである。それら3つの特性形式的に表現できないため、チャーチ=チューリングのテーゼは証明できない。以下の事実がしばしばこのテーゼ証拠とされる様々な等価な計算模型知られていて、いずれも計算可能関数の同じ定義を与える(それらより弱いモデル存在する)。 それらの計算模型より強力なモデルは、これまで提唱発見されていない。 チャーチ=チューリングのテーゼは、ある関数計算可能であることを証明するときに特定の具体的な計算模型手続き記述することを正当化するのに使われる。これが許されているのは、(少なくとも既知の)どの計算模型であっても記述能力に差がないことが分かっていて、単に様々な記述省略するためにテーゼ利用していると見なせるからである

※この「チャーチ=チューリングのテーゼ」の解説は、「計算可能関数」の解説の一部です。
「チャーチ=チューリングのテーゼ」を含む「計算可能関数」の記事については、「計算可能関数」の概要を参照ください。

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


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

辞書ショートカット

すべての辞書の索引

「チャーチ=チューリングのテーゼ」の関連用語

チャーチ=チューリングのテーゼのお隣キーワード
検索ランキング

   

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



チャーチ=チューリングのテーゼのページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアのチャーチ=チューリングのテーゼ (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。
ウィキペディアウィキペディア
Text is available under GNU Free Documentation License (GFDL).
Weblio辞書に掲載されている「ウィキペディア小見出し辞書」の記事は、Wikipediaの計算可能関数 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。

©2022 GRAS Group, Inc.RSS