Aritalab:Lecture/Algorithm/Churchs Thesis

チャーチの定立

計算という概念を、帰納的関数と呼ばれる関数のクラスに属することと同一視しよう、という主張をしたのが Alonzo Church です。その主張は英語で Church's Thesis になりますが、証明できることではないので日本語では定立（ていりつ）とか提唱とか呼ばれます。帰納的関数のクラスはチューリングマシンが計算出来る関数のクラスとも一致します。

参考

• Stanford 大学 Church-Turing の提唱