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

チャーチ＝チューリングのテーゼ (Church-Turing thesis) もしくはチャーチのテーゼ (Church's thesis) とは、

テーゼの代わりに提唱（ていしょう）あるいは定立（ていりつ）の語が用いられることもある。

このクラスはチューリングマシンで実行できるプログラムのクラス、ラムダ記法で定義できる関数のクラスとも一致する。

よって簡単にはテーゼは、

計算が可能な関数とは、

その計算を実行できるような有限のアルゴリズムが存在するような関数、

よっておおよそコンピュータで実行できる関数と同じだと主張する。