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

/論理・基礎論

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

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

  • 有限長の有効的で構成的な全ての計算手順は、チューリングマシンで実行できる。
  • 有効的で構成的な計算手順を定義するいかなる計算システムも、計算能力においてチューリングマシンを上回ることはない。

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

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

  • 全ての計算可能な関数を列挙して、チューリングマシンで計算できることを証明することができていない。
  • チューリングマシンの計算能力を上回る計算システムが、存在しないことを証明できていない。

しかし、チャーチ・チューリングの定立の反証も見つかっておらず、一般にはこの定立は正しいと受け入れられています。

計算システムの等価性

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

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

  • 異なる計算システムであっても(チューリングマシンと)同じ結果が得られる。
  • 計算可能な関数を調べたいときに、どの計算システムを選んでも構わない(全ての計算システムで調べる必要はない)。

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

 

数学
解析学、代数学、幾何学、統計学、論理・基礎論、情報・暗号、機械学習、金融・ゲーム理論、高校数学
散策路TOP
数学、応用数学、古典物理、量子力学、物性論、電子工学、IT、力学、電磁気学、熱・統計力学、連続体力学、解析学、代数学、幾何学、統計学、論理・基礎論、プラズマ物理、量子コンピュータ、情報・暗号、機械学習、金融・ゲーム理論

 

タイトルとURLをコピーしました