量子計算学習ノート - チューリング機械3

---

この記事は「量子コンピュータと量子通信 (オーム社)」の読書ノートです。

---

ここではチューリング機械が計算できる範囲について説明しよう。

実際、チューリング機械を使うと非常に多くの種類の関数を計算できることがわかっている。具体的には基本的な算術演算、ビット列で表現されたテキストの検索などだ。

実はチャーチとチューリングによって独立に発表された論文によると、現代のコンピュータで行えるすべての演算（現代の解釈における任意のアルゴリズムに対応）をチューリング機会を使ってシミュレートできることが示されている！このことを厳密に言うと、次のチャーチ・チューリングの提唱に集約される。

チューリング機械で計算可能な関数のクラスは、アルゴリズムで計算可能とみなされる関数のクラスと一致する

チャーチ・チューリングの提唱

これは本来直感的であったアルゴリズムによって計算可能とみなされる関数のクラスと数学的に厳密なチューリング機械によって計算可能な関数のクラスが一致することを示すものであり、現代におけるアルゴリズムというものを数学的に厳密に定義するものといえよう。

一方でこのことは自明なことではない。多くの人々がチャーチ・チューリングの提唱に対する根拠を見出すのに多くの時間を費やした。少なくともその過程で現時点まで反証は見つかっていない。

もしチューリング機械で計算できない関数を計算する手続き、アルゴリズムを見出したとき、私達はこれを計算することができる計算モデルを見直す必要がある。その時にまたアルゴリズムとはなにか、それを扱うコンピュータ科学とは何なのか、といったことを徹底的に再構築する必要があるだろう。

要するにチャーチ・チューリングの提唱というのは現時点でのアルゴリズムの定義を提唱するものであるということだ。

なお、量子コンピュータも今後の議論でチャーチ・チューリングの提唱にしたがう事がわかる。つまり、量子アルゴリズムによる計算可能な関数のクラスはチューリング機械の計算可能な関数のクラスと一致する。量子コンピュータとチューリング機械の差分は効率的に計算できる関数のクラスの大きさにある。要するにチューリング機械では効率的に計算できないが、量子コンピュータでは効率的に計算可能な関数が存在するのだ。