量子コンピューターでも計算不能。科学の「決定不能性」問題に挑み始めた研究者たち

1814年、フランスの学者ピエール＝シモン・ラプラスは、現状のすべてを知ることができる賢い「悪魔」がいれば、その悪魔にとっては未来もすべて予測可能だと主張した。それは、この宇宙は完全に理解可能だという彼の考えを明快に表す思考実験であり、物理学があらゆるものを予測可能にするはずだという当時の楽観主義の高まりを示すものだった。それ以来、そうした野心は現実によって繰り返し屈服させられるのだが。

そんな一撃のひとつが、1900年代前半の量子力学の発見だ。量子の世界において、粒子は測定されない限り常に曖昧な「可能性」の領域に存在する。厳密な位置というものがないため、悪魔にも知ることはできない。

同じ世紀のうちに次の一撃が来た。「カオス」理論の登場が世界の不確実性をさらに増大させたのだ。その理論では、悪魔が50年後の天気を予測するなら、1羽の蝶の羽ばたきひとつに至るまで無限に現在を知ることができなければならない。

そして近年、第3の制約が物理学界に広がりつつある。ある意味これまでで最もショッキングな制約とも言えるそれは、量子粒子の集まりにも、海流などの古典物理学的現象においても発見された。「決定不能性」と呼ばれるこの問題は、カオス理論を超える。現在の状態をすべて知る悪魔でさえ、未来を完全に把握することができなくなるのだ。

決して答えの出ない疑問が存在する

「たとえ神の視点を与えられても、どうなるのか予測できないのです」と、物理学者からコンピューターサイエンティストに転身したユニバーシティ・カレッジ・ロンドンのトビー・キュビットは言った。彼はそんな不可知の領域に攻め込もうとしている先駆的研究者のひとりだ。

スペインのカタルーニャ工科大学（UPC）の数学者エヴァ・ミランダは、決定不能性を「次のレベルのカオス」と呼ぶ。

ピエール＝シモン・ラプラスは、全知全能の悪魔があらゆる物理システムの未来を完璧に予測できると推測した。その推測は間違っていた。

PHOTOGRAPH: JOHANN ERNST HEINSIUS/WIKIMEDIA COMMONS

決定不能性とはつまり、決して答えの出ない疑問が存在するということである。物理学者にとっては馴染みがないが、数学者やコンピューターサイエンティストにはよく知られた概念だ。実際、数学とコンピューターサイエンスの分野では、決して答えることのできない数学的問題、決して証明できない真理が存在することが1世紀以上前に厳密に証明されている。いま、物理学者たちはそうした不可知の数学的問題が物理的な現実世界にも存在することを次々と発見し、物理学で知りうることの限界を定義し始めている。

それらの例は「人間が考え出せることに大きな制限を課すものです」と、サンタフェ研究所で知識の限界について研究しているデヴィッド・ウォルパートは言う。「その制限は、決して侵すことのできないものです」

チューリングと計算可能性の限界

不可知の強力な例が物理学にもたらされたのは1990年、当時コーネル大学の大学院生だったクリス・ムーアが、たったひとつの可動部分しかもたない決定不能な機械を設計したときだ。

その装置は理論上のものであって実際につくられたわけではないが、高度にカスタマイズ可能なピンボールマシンのようなものだった。底が開いた箱を想像してほしい。プレイヤーは箱の中に自由にバンパーを配置でき、ランチャーを箱の底の好きな位置に設置してピンボールを発射する。仕掛けは比較的シンプルだ。しかし、跳ね回るボールが密かに計算を実行するのである。

ムーアが計算処理に強い興味を抱いたきっかけは、自己言及するシステムについて論じるピュリッツァー賞受賞作『Gödel, Escher, Bach』［邦訳『ゲーデル、エッシャー、バッハ　あるいは不思議の環』］を読んだことだった。なかでも彼の想像力をかき立てたシステムは、コンピューターサイエンスという研究分野そのものの出発点となった理論上の装置、チューリングマシンだった。

数学者アラン・チューリングが1936年の画期的な論文で定義したチューリングマシンは、無限の長さをもつテープとその上を上下に動く読み書き装置で構成される。読み書き装置は、単純なルールに従ってテープを左右に動かしながら0と1を読み取ったり書いたりする。それぞれのチューリングマシンは特定のルールに従って動き、ふたつの数を読み取ってその積を出力するものもあれば、ひとつの数を読み取ってその平方根を出力するものもありうる。

このように、チューリングマシンはあらゆる数学的・論理的操作の手順を実行するように設計できる。現代ではその手順を「アルゴリズム」と呼ぶだろう。多くの（ただしすべてではない）物理学者は、実行者がコンピューター、人間、悪魔のいずれかにかかわらず、チューリングマシンは計算可能性そのものの限界を定めると考えている。

チューリングマシンの仕組み

チューリングマシンは、左右に動くテープに0と1を読み書きすることで計算を行なう。その動作は特定のルールセットに従う。

マシンは1度にひとつのルールに従う。それぞれのルールは、何を書き、どちらに動き、次にどのルールに従うかを指示する。ルールAから始まったとき、チューリングマシンは最終的に停止するか、あるいは永遠に動き続ける。

すべてのルールは上図のような小さな表にまとめることができる。

ILLUSTRATION: KRISTINA ARMITAGE/QUANTA MAGAZINE

ムーアは、自身の卒業研究のテーマであるカオス現象のなかにチューリングマシンの動作の可能性を見出した。カオス的なシステムでは、どれほど小さな出来事も無視できない。お決まりの比喩によれば、ブラジルで1頭の蝶が1ミリ動くだけで、東京に台風が直撃するかテネシー州で竜巻が猛威を振るうかが変わる。初めはほんの小さな誤差だった不確実性が、やがて計算結果全体を覆すほど大きくなる。

カオス的システムにおけるこの成長は、数字の変化で表すことができる。少数点以下1桁の誤差だったものがじわじわと左側に動き、やがては小数点を横切って10の位にまで達するのだ。

ムーアは、カオスとチューリングマシンの類似を理論モデルとして完成させるためにピンボール装置を設計した。ピンボールの発射位置は、チューリングマシンに入力されるテープ上のデータに相当する。重要なのは、（非現実的ではあるが）ボールの発射位置を無限の精度で調整できることが前提になっている点である。

つまり、ボールの位置を指定するためには、小数点以下に無限に続く桁数をもつ数字が必要なのだ。このような数字でなければ、チューリングマシンの無限の長さをもつテープ上のデータをエンコードすることはできない。

そして、チューリングマシンのテープ上の読み書き操作に対応するかたちで、バンパーの配置がボールの次の動きを決定する。特定のカーブの形状をもつバンパーがテープを一方向に動かし、逆向きにカーブしたバンパーがあれば逆の効果をもたらし、そうして小数点以下に存在していたデータが徐々に重要性を増していく。カオスシステムを思わせる性質だ。ボールが箱の底から出てくるときが計算の終了で、出てきた位置が最終的な計算結果となる。

ムーアはピンボールマシンにコンピューターのような柔軟性をもたせた。バンパーの配置を変えれば、円周率の最初の1,000桁を計算させることもできるし、チェスの次の最善手を計算させることもできる。しかし同時に、通常のコンピューターとは結びつかない性質、つまり予測不能性も備わってしまった。

アラン・チューリングは1936年に発表した画期的な論文のなかで、現在「チューリングマシン」として知られる万能な計算装置の主な特徴を説明し、計算可能性の限界を定義した。

PHOTOGRAPH: GL ARCHIVE/ALAMY/AFLO

アルゴリズムには、計算を終えて停止するものもあれば、永遠に計算を実行し続けるものもある（例えば、円周率の最後の桁を出力せよと命じられたプログラムは永久に止まらない）。あらゆるプログラムに対して、それが最終的に停止するのかどうかを判定できる方法はあるのだろうか、とチューリングは問うた。この問いが有名な「停止性問題」である。

チューリングは、停止性を判定する方法の存在が何を意味するかを考え、そのような方法が存在しないことを証明した。あるマシンがほかのマシンの動作を予測できると仮定する。予測マシンを軽く改造し、ほかのマシンが停止したときに永遠に動作を続けるようにする。逆に、ほかのマシンが永遠に動き続けるときには予測マシンが停止するようにする。

そして、ここが理解の難しい部分だが、チューリングはこの改造版予測マシンにそれ自身の設計図を入力して動かすことを想像した。もしマシンが停止するなら、その同じマシンは永遠に動くことになる。マシンが永遠に動くなら、停止することになる。どちらの場合も成り立たないので、チューリングは予測マシン自体が存在しえないと結論づけた。

（彼の発見は、31年に論理学者クルト・ゲーデルが同様の方法で自己言及性のパラドックスを数学的枠組みに組み込んだ際の画期的結果と密接に関連している。ゲーデルは、数学には真偽を証明できない命題が存在することを証明した。）

つまり、チューリングは停止性問題を解くことは不可能であると証明したのだ。プログラムが停止するかどうかを知る唯一の一般的な方法は、それをできる限り長く実行することである。停止すれば、それで答えが出る。しかし止まらない場合、そのまま永遠に動き続けるのか、もう少し待てば止まるのか、決してわからない。

「初期状態によっては、未来の動きを予測できないプログラムがあるのです」とウォルパートは言った。

カオスを超越したピンボールマシン

ムーアはあらゆるチューリングマシンの動作を再現できるようにピンボールマシンを設計したので、同じく動きが予測不能になるケースがありうる。ボールが出たときが計算の終わりだが、バンパーの配置によっては、ボールが永遠に中に閉じ込められるのか、やがて出てくるのかが判定できない場合もある。「実際のところ、こうした複雑なモデルの長期的な動きについては、あらゆる問いが決定不能です」とムーアは言った。

クリス・ムーアは、決定不能な物理システムを極めてシンプルなかたちで最初期に考案した。

PHOTOGRAPH: CRESSANDRA THIBODEAUX

ムーアのピンボールマシンは一般的なカオスを超えた。竜巻の発生地を正確に予報できない理由はふたつ。ブラジルのすべての蝶の位置が正確にわからないことと、コンピューターの計算能力が限られていることだ。しかし、ムーアのピンボールマシンはさらに根本的な予測不能性を備える。マシンの仕組みを完全に知り、無限の計算能力をもつ者でも、その未来に関する特定の問いには決して答えられないのだ。

「さらに少しドラマチックな話です」と、マドリード・コンプルテンセ大学の数学者ダヴィド・ペレス＝ガルシアは言う。「無限のリソースがあっても、問題を解くプログラムを書くことすらできないのですから」

これまでに、チューリングマシンのような性質をもつシステムはほかにも提案されてきた。隣の色に応じてマス目が点滅する格子状のモデルが特に有名だ。しかし、それらは抽象的で複雑なものだった。それに対してムーアは、実際に研究室にありそうなシンプルな装置でチューリングマシンをつくり上げた。高校レベルの物理だけを使ってつくったシステムでも予測不能な性質をもちうることを鮮やかに示したのだ。

「あれが決定不能性をもつというのは、少しショッキングです」と語るキュビットは、大学院時代にムーアのピンボールマシンに感銘を受け、のちに講義でも紹介するほど魅了された。「ひとつの粒子が箱の中で跳ねているだけなのに」

物理学で博士号を取得した後、キュビットは数学とコンピューターサイエンス分野の研究者へと転身した。それでも、ピンボールマシンのこと、コンピューターサイエンスがマシンの物理学に限界を与えたことは決して忘れなかった。決定不能性は現実の重要な物理問題にも現れうるのだろうか、と彼は考えた。そしてこの10年の研究を通して、それがありうるということがわかった。