複雑性理論と人工知能技術（５） ドイッチェ

ファインマンの「量子コンピュータによる自然のシミュレーション」という刺激的な問題提起を受け、それを「計算可能性理論」の中心的な原理である「チャーチ＝チューリングのテーゼ」との関連で整理しなおして「計算可能性」を再定式化したのは、ドイッチェである。

1985年の論文 "Quantum theory, the Church-Turing principle and the universal quantum computer" https://goo.gl/PVHGKa で、ドイッチェは、「チューリング・マシンのクラスの量子論的一般化である計算機械のクラス」＝「万能量子コンピュータ」を構成して見せる。

彼は、「チャーチ＝チューリングのテーゼ」を次のように捉える。

『「計算可能と自然に見なされる関数」は、全て、万能テューリング・マシンで計算可能である。.』

ただ、彼は、この「チャーチ＝チューリングのテーゼ」の基礎には、暗黙の物理学的主張がある」という。これが、この論文の眼目である。

彼は、彼が構成して見せた「万能量子チューリング・マシン」＝「万能計算機械」を用いて、「チャーチ＝チューリングのテーゼ」を書き換える。

「この物理学的主張は、次のような物理学的原理として、明確に表現することが出来る。」

『有限な方法で実現可能な物理システムは、有限な手段によって操作される万能計算機械のモデルで完全にシミュレート可能である。』

これを、「チャーチ＝チューリング＝ドイッチェのテーゼ」という。

ドイッチェは、論文で、これらの原理が、次の熱力学の第三法則に似ていること注意を向けているのは、興味ふかい。

『どのような有限のプロセスも、有限な手段実現可能な物理システムのエントロピーあるいは温度をゼロにはできない。』

形式的・数学的で抽象的な「計算可能性」の原理だった「チャーチ＝チューリングのテーゼ」は、ここに「チャーチ＝チューリング＝ドイッチェのテーゼ」として、実在的な過程としての「計算」の原理として「物理化」されることになる。

「計算可能性」の原理の「物理化」は、関連する諸科学に、一つのインパクトをもたらすことになる。なぜなら、それは、それまで別々の学問の対象だった「計算過程」「物理過程」「情報過程」（それぞれ、数学・物理学・コンピュータ科学が扱っていた）に対して、「計算過程」＝「物理過程」＝「情報過程」という、強力な三位一体の図式が、しかも、物理学の優位の元に生まれたことを意味することになるからである。

こうした動きのすぐれた解説は、彼の死後に発刊されたファインマンの最後の著作である "Feynman Lectures on Computation" https://goo.gl/PyqgyT の第５章 "Reversible Computation and the Thermodynamics of Computing" と第６章 "Quantum Mechanical Computers" をみるのがいい。30年前のものだが、少しも古くない。

ただ、「チャーチ＝チューリング＝ドイッチェのテーゼ」は、その認識論的意味を考えると、本当は、なかなか手強いものだ。その辺の議論は、あとで振り返ることがあると思うが、ニールセンの次の投稿を見て欲しい。 "Interesting problems: The Church-Turing-Deutsch Principle" https://goo.gl/Q6EiYi