チャーチ＝チューリングのテーゼ
直観的に「実効的に計算可能」なものはすべてチューリングマシン（あるいは等価なラムダ計算）で計算できる、という仮説。証明できる定理ではなく、「計算可能」の定義にあたる。
1936年にチャーチとチューリングがそれぞれ独立に示した。帰結として、チューリングマシン、ラムダ計算、レジスタマシン、再帰関数、セルオートマトン、ライフゲームなど、「妥当な」計算モデルはすべて等価になる。現代的な拡張が強いチャーチ＝チューリングのテーゼで、実効的に計算可能な関数は多項式時間で相互に変換できるとする。量子計算はこの強い版に挑戦している。ショアのアルゴリズムは素因数分解を多項式時間で解くが、古典的手法にはそれができない。