正しいのに、証明できない
隣人たちの群れを思い浮かべてほしい。どの2人の組にも、それぞれの要求がある。すべての要求を同時に満たせれば、全員が満足する。2つの要求がぶつかれば、誰かが譲らなければならない。量子スピンでできた磁石を研究する物理学者は、まさにこの問いに直面している。隣り合うスピンの各組にはエネルギーの規則があり、系は最も低いエネルギーに達しようとする。ただ1つの状態がすべての組を同時に満たせるとき、そのモデルはフラストレーションフリー(frustration-free)と呼ばれる。
こうしたモデルは重宝されている。有名な例にはAKLTモデルやキタエフ(Kitaev)のトーリック符号があり、物質のエキゾチックな相の基準点になっている。フラストレーションフリーであることは、物質が低エネルギーでどうふるまえるかにも強い制約を課す。そこで自然な問いが生まれる。1組に対する規則が与えられたとき、そのモデルはあらゆるサイズの格子でフラストレーションフリーなのか?
東京大学のNaoto Shiraishiは、この問いを正方格子状に並んだスピンで調べた。隣り合うすべての組のあいだで、同じ規則が繰り返される設定だ。各スピンはd通りの状態をとれる。答えは、互いに矛盾するように見える2つの部分からなる。
格子は1つで足りる
1つの格子サイズについてなら、この問いは普通の線形代数だ。厄介なのは、サイズが無限にあることである。どんどん大きな格子を調べていけば破綻が見つかることはあるが、すべてのサイズでうまくいくことを証明することは決してできない。
第1の定理が、その無限を取り除く。dの各値に対して、ありうるすべての規則に共通の有限の打ち切りサイズ(cutoff)が存在する。モデルがそのサイズの格子でフラストレーションフリーなら、すべてのサイズでフラストレーションフリーである。したがってこの問題は決定可能だ。常に「はい」か「いいえ」を答えるアルゴリズムが存在する。
鍵になるのは代数学の古典、ヒルベルトの基底定理である。各サイズでの条件は多項式方程式の集まりとして書くことができ、未知数は常に同じ2d⁴個、すなわち2つの規則行列の成分である。この定理は、そうした方程式の無限のリストが、そのある有限の部分と同じ解をもつことを保証する。フラストレーションフリーな格子は、そこから切り出したどんな小さな格子上でもフラストレーションフリーのままなので、結局1つのサイズで足りることになる。
これは自明な結果ではない。まったく同じ種類のモデルで、関連する問い、つまり最低状態の上にエネルギーギャップがあるかどうかは、dを固定してさえ決定不能であることが示されている。
矛盾を探すタイルの組
第2の定理は逆の方向を向く。ZFCとして知られる数学の標準的な公理系が矛盾を含まないと仮定すると、それらの公理からはフラストレーションフリー性を証明できない、フラストレーションフリーなモデルが存在する。
この構成にはワンタイル(Wang tiles)が使われる。辺に色のついた正方形で、回転させずに並べ、隣り合うタイル同士は色が一致しなければならない。どんなコンピュータプログラムに対しても、そのプログラムが永遠に動き続けるとき、かつそのときに限り無限の平面全体を覆える有限のタイルの組を設計できる。各タイルはスピンの1つの状態になる。隣り合うタイルの禁じられた組は、それぞれ1単位のエネルギーを負う。モデルがフラストレーションフリーになるのは、まさにタイルが平面を覆えるときである。
ここで、ZFCの矛盾を求めてありうるすべての証明を探索し、矛盾を見つけたら停止するプログラムを選ぶ。ZFCが無矛盾なら、プログラムは決して止まらず、モデルはフラストレーションフリーになる。だが、もしZFCがそれを証明できるなら、ZFCは自らの無矛盾性を証明することになり、それはゲーデルの第2不完全性定理が禁じている。
このモデルは明示的に与えられているが、書き出すにはあまりにも複雑だ。その規則は本当の意味で量子的ですらない。エネルギー項はすべて可換で、単純な古典的制約のようなものだ。
存在するのに名指しできない打ち切りサイズ
ある問題が決定可能でありながら、証明できない命題を含むことがどうしてありうるのか? 答えは打ち切りサイズにある。それはどのdに対しても有限だが、どんなアルゴリズムもdからそれを計算できない。証明不能なモデルの次元に対しては、公理は有限の打ち切りサイズが存在することを証明する。それなのに、特定のどの数についても、それが打ち切りサイズであることは証明できない。
打ち切りサイズはまた、とてつもなく速く増大する。少なくともビジービーバー関数と同じ速さだ。これは、与えられた状態数をもつ停止するプログラムがテープに残せる印の最大数であり、コンピュータが計算できるあらゆる関数を上回って増大する。論文によれば、5状態の機械に対するその値が確定したのは2024年になってからで、6状態の値はいまだにわかっていない。
存在することと知ることの隔たり
決定可能性が要求するのは、正しいアルゴリズムが存在することだけで、誰かがそれを構築できることではない。なじみ深いほとんどの場合、この違いは問題にならない。ところがここでは、それがすべてになる、と著者は論じる。しかもそれは、ただの正方格子上の普通の物理の問題に現れるのだ。著者は、決定可能性の結果を確立するため、そしてそれが証明不能性の結果とどう整合するかを明確にするためにChatGPTを使ったと述べている。実際の打ち切りサイズを突き止めることは、ごく小さなスピンについてさえ、未解決の課題として残されている。
