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

出典: フリー百科事典『ウィキペディア（Wikipedia）』

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

[編集] 概要

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

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

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