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

/数学基礎

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

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

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

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

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

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

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

計算システムの等価性

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

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

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

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

 

応用数学
数値計算、情報理論、暗号理論、機械学習、金融工学、ゲーム理論
散策路TOP
力学、電磁気・相対論、熱・統計力学、量子力学、物性物理、機械学習、情報処理、金融、物理数学

 

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