チャーチ・チューリングの定立とは

チャーチ・チューリングの定立

チャーチ・チューリングの定立とは、計算可能な関数とチューリングマシンで計算できる関数（帰納的関数）を同じとする提唱（仮説）です。チャーチ・チューリングの定立は、以下のように表現されています。

「有効的で構成的」とは、実際の計算手順を具体的に書き出すことができるという意味で、計算が可能であることと同義に使われています。つまり、計算可能な関数を最も効率よく計算するシステムは、チューリングマシンであることを表しています。

但し、チャーチ・チューリングの定立は、証明されているわけではありません。これは以下のような理由からです。

これらはいわゆる悪魔の証明であり、「ない」ことの証明は容易ではないためです。しかし、チャーチ・チューリングの定立の反証も見つかっておらず、一般にはこの定立は正しいとして受け入れられています。

尚、２つ目の定立の計算システムの等価性については、これまで考案された計算システムでは証明されています。

計算システムとは、人間が行う計算の手順や道具を抽象化したものです。代表的な計算システムはチューリングマシンですが、それ以外にもチャーチのラムダ計算など、いくつもの計算システムが考案されています。

これまで考案された有効的で構成的な全ての計算システムは、チューリングマシンと高々等価でしかないことが証明されています。計算システムの等価性の利点は以下になります。

つまり、ある関数が計算可能であることを示すのには、実際の計算手順を具体的に書き出すことができれば（有限長の有効的で構成的な計算手順であれば）よいことになります。