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

ウィキペディア

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

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2024/08/19 15:40 UTC 版)

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

概要

1932年にエルブラン、および1934年にゲーデルが、原始帰納的関数と呼ばれる自然数上の関数の明示的構成法を拡張して帰納的関数（もしくは一般帰納的関数）と呼ばれる関数の構成法を作り上げた。1933年から1935年ごろには、チャーチやクリーネがやはり関数の構成的な定義法であるラムダ記法を用いて定義可能な関数のクラスを定めた。さらに、1935年から1936年にかけてポストとチューリングは、チューリングマシンの概念を用いてこの理念的計算機械で実行可能なプログラムのクラスを定めた。

こうしてほぼ同時期に出現したさまざまな計算できる数論的関数のクラスは、実は互いに同じものであることが証明された。これにより、それまで非形式的に「実質的に計算できる関数」(effectively computable function) と呼び慣わされていたこのクラスをもってして「計算できる関数」とみなそうという主張がなされることになった。これがチャーチ＝チューリングのテーゼと呼ばれている主張である。この意味で計算できる関数はチューリング計算可能な関数、あるいは単に計算可能関数と呼ばれるようになった。この主張自体はチャーチ、チューリング論文を参照して1943年にクリーネによってなされた。

この主張は数学的定理ではないので証明されるべき事柄ではない。「計算できる」という日常的な意味を考慮せず、純粋に形式的に考えるなら、この主張は単に計算可能関数の概念を定義したとも受け取れる。また逆に、これを「計算できる」という直観的概念に対する一種の仮説と受け取ることもできる。この最後の場合、チャーチ＝チューリングのテーゼは、手続きに従って実際に行えるいかなる計算も、ここで示された帰納的関数のクラスを越えることはできないことを主張する。

関連項目

• 決定可能性

外部リンク

• The Church-Turing Thesis （英語） - スタンフォード哲学百科事典「チャーチ＝チューリングのテーゼ」の項目。

ウィキペディア小見出し辞書

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

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

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

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