フランスの学者ピエール＝シモン・ラプラスは、1814年に宇宙は完全に知ることができるという自身の予想を明瞭に述べ、十分に賢い「悪魔」は現在を完全に知っていれば未来全体を予測できると主張した。彼の思考実験は、物理学者が予測するであろうことについての楽観主義の極みを示しました。それ以来、現実は、それを理解しようとする彼らの野心を何度も挫折させてきました。
1900 年代初頭に量子力学の発見により、一撃がもたらされました。量子粒子は、測定されていないときは常に、基本的に曖昧な可能性の領域に存在します。悪魔が知ることができる正確な位置はありません。
もう一つの出来事は、その世紀の後半に起こり、物理学者が「混沌とした」システムがどれほど不確実性を増大させているかに気づいたときでした。悪魔は 50 年後の天気を予測できるかもしれませんが、それはすべての蝶の羽の鼓動に至るまで、現在に関する無限の知識が必要です。
近年、3 番目の制限が物理学に浸透しつつあります。ある意味、これまでで最も劇的なものです。物理学者は、渦巻く海流のような古典的なシステムとともに、量子粒子の集合体でそれを発見しました。決定不能性として知られるそれは、混沌を超えています。システムの状態を完全に知っている悪魔でも、その未来を完全に把握することはできません。
「神の見解をお伝えします」と物理学者からロンドン大学ユニバーシティ・カレッジのコンピューター科学者に転身し、未知への取り組みの先鋒の一人であるトビー・キュービット氏は言う。「それが何をするのかはまだ予測できない。」
スペインのカタルーニャ工科大学 (UPC) の数学者、エヴァ・ミランダは、決定不能性を「次のレベルの混沌としたもの」と呼んでいます。
ピエール＝シモン・ラプラスは、全知の悪魔はあらゆる物理システムの未来を完全に予測できると推測しました。彼は間違っていました。
ヨハン・エルンスト・ハインシウス/ウィキメディア・コモンズ
決定不能とは、特定の質問に単純に答えることができないことを意味します。これは物理学者にとっては馴染みのないメッセージですが、数学者やコンピューター科学者はよく知っているメッセージです。 1世紀以上前、彼らは決して答えることのできない数学的な問題や、決して証明することのできない真の命題が存在することを厳密に確立しました。現在、物理学者は、これらの不可知な数学的システムを、ますます多くの物理的なシステムと接続し、それによって、自分たちの分野における可知性の厳しい境界線を描き始めています。
これらの例は「私たち人間が思いつくことに大きな制限を課している」と、知識の限界を研究しているが最近の研究には関与していないサンタフェ研究所の研究者デビッド・ウォルパート氏は述べた。 「そしてそれらは不可侵です。」
最も黒い箱
不可知性の顕著な例は、1990 年に物理学に現れました。当時、コーネル大学の大学院生だったクリス ムーアは、単一の可動部品を備えた決定不可能な機械を設計しました。
His setup — which was purely theoretical — resembled a highly customizable pinball machine.底が開いた箱を想像してください。プレイヤーはボックスをバンパーで埋め、ランチャーをボックスの底に沿って任意の位置に移動し、ピンボールを内部に発射します。仕掛けは比較的単純でした。 But as the ball ricocheted around, it was secretly performing a computation.
Moore had become fascinated with computation after reading Gödel, Escher, Bach , a Pulitzer Prize–winning book about systems that reference themselves. The system that most captured his imagination was an imaginary device that had launched the field of computer science, the Turing machine.
数学者のアラン・チューリングが 1936 年の画期的な論文で定義したチューリング マシンは、無限に長いテープを上下に移動できるヘッドで構成され、何をすべきかを指示するいくつかの単純なルールに従って、一連のステップで 0 と 1 を読み書きします。 One Turing machine, following one set of rules, might read two numbers and print their product. Another, following a different set of rules, might read one number and print its square root. In this way, a Turing machine could be designed to execute any sequence of mathematical and logical operations.今日では、チューリング マシンは「アルゴリズム」を実行すると言えます。多くの (すべてではありませんが) 物理学者は、チューリング マシンがコンピュータ、人間、悪魔のいずれによって実行されるかに関係なく、計算自体の限界を定義すると考えています。
クリスティーナ・アーミテージ/クアンタ・ マガジン
ムーアは、大学院の研究テーマであるカオスにチューリング マシンの動作の種があることに気づきました。混沌としたシステムでは、無視できるほど小さなディテールは存在しません。悪名高い比喩で言えば、ブラジルで蝶の位置を 1 ミリメートル調整することは、東京を襲う台風とテネシー州を引き裂く竜巻の違いを意味する可能性があります。 Uncertainty that starts off as a rounding error eventually grows so large that it engulfs the entire calculation. In chaotic systems, this growth can be represented as movement across a written-out number:Ignorance in the one-tenths place spreads left, eventually moving across the decimal point to become ignorance in the tens place.
Moore designed his pinball machine to complete the analogy to the Turing machine. The starting position of the pinball represents the data on the tape being fed into the Turing machine.重要なこと（そして非現実的ですが）は、プレーヤーがボールの開始位置を無限の精度で調整できなければなりません。つまり、ボールの位置を指定するには、小数点以下の数字が無限に続く数字が必要になります。 Only in such a number could Moore encode the data of an infinitely long Turing tape.
次に、バンパーの配置により、チューリング マシンのテープの読み取りと書き込みに対応する方法でボールが新しい位置に誘導されます。特定の湾曲したバンパーはテープを一方向にシフトし、カオス システムを彷彿とさせる方法で遠くの小数点に保存されたデータをより重要なものにしますが、反対に湾曲したバンパーはその逆を行います。ボールがボックスの底から出ると計算が終了し、最終的な位置が結果として表示されます。
ムーアは、ピンボール マシンのセットアップにコンピューターの柔軟性を備えました。バンパーの 1 つの配置で円周率の最初の 1,000 桁を計算したり、別の配置でチェスのゲームで最適な次の手を計算したりできます。 But in doing so, he also infused it with an attribute that we might not typically associate with computers:unpredictability.
一部のアルゴリズムは停止し、結果を出力します。しかし、他の人は永遠に走り続けます。 (円周率の最後の桁を出力するプログラムを考えてみましょう。) 任意のプログラムを調べて、それが停止するかどうかを判断できる手順はあるのでしょうか、とチューリングは尋ねました。 This question became known as the halting problem.
チューリングは、そのような手順が存在する場合に何を意味するかを検討することで、そのような手順が存在しないことを示しました。 If one machine could predict the behavior of another, you could easily modify the first machine — the one that predicts behavior — to run forever when the other machine halts.逆も同様です。他のマシンが永久に実行されると、マシンは停止します。次に、ここが気が遠くなる部分ですが、チューリングは、この微調整された予測マシンの記述をそれ自体に入力することを想像しました。機械が停止しても、永遠に動作し続けます。そして永遠に走り続けると、また止まります。どちらの選択肢もあり得ないため、予測マシン自体は存在してはならない、とチューリングは結論付けました。
(His finding was intimately related to a groundbreaking result from 1931, when the logician Kurt Gödel developed a similar way of feeding a self-referential paradox into a rigorous mathematical framework. Gödel proved that mathematical statements exist whose truth cannot be established.)
つまり、チューリングは停止問題の解決が不可能であることを証明したのです。アルゴリズムが停止したかどうかを知る唯一の一般的な方法は、アルゴリズムをできるだけ長く実行することです。それが止まったら、答えは出ます。 But if it doesn’t, you’ll never know whether it truly runs forever, or whether it would have stopped if you’d just waited a bit longer.
「私たちは、それがどうなるかを事前に予測できないような初期状態があることを知っています」とウォルパート氏は言いました。
ムーアはチューリング マシンを模倣するようにボックスを設計したため、それも予測できない動作をする可能性がありました。 The exit of the ball marks the end of a calculation, so the question of whether any particular arrangement of bumpers will trap the ball or steer it to the exit must also be undecidable. 「実際のところ、これらのより精緻な地図の長期的な動向については、いかなる疑問も決断の余地がありません」とムーア氏は言いました。
クリス ムーアは、最も初期かつ最も単純な決定不可能な物理システムの 1 つを開発しました。
クレッサンドラ・ティボドー
ムーアのピンボールマシンは、普通の混乱を超えていました。 A tornado forecaster can’t say exactly where a tornado will touch down for two reasons:the forecaster’s ignorance of the precise position of every Brazilian butterfly, and limited computing power.しかし、ムーアのピンボールマシンは、より根本的な形の予測不可能性を特徴としていました。 Even for someone with complete knowledge of the machine and unlimited computing power, certain questions regarding its fate remain unanswerable.
マドリッド・コンプルテンセ大学の数学者デビッド・ペレス・ガルシア氏は、「これはもう少し劇的だ」と語る。 「たとえ無限のリソースがあっても、問題を解決するプログラムを書くことさえできません。」
Other researchers have previously come up with systems that act like Turing machines — notably checkerboard grids with squares flickering on and off depending on the colors of their neighbors.しかし、これらのシステムは抽象的で複雑でした。ムーアは、研究室にあるものを想像できるような単純な装置からチューリング マシンを作成しました。これは、高校の物理学にのみ従うシステムが予測不可能な性質を持つ可能性があることを鮮やかに実証しました。
“It’s a bit shocking that it’s undecidable,” said Cubitt, who lectured about Moore’s machine after it captured his imagination as a graduate student. 「文字通り、箱の周りを跳ね回る単一の粒子です。」
物理学の博士号を取得した後、キュービットは数学とコンピューター サイエンスに移りました。しかし、彼はピンボール マシンのこと、そしてコンピューター サイエンスがマシンの物理学にどのように限界を設けたかを決して忘れませんでした。彼は、決定不可能性が本当に重要な物理学の問題に影響を与えるのではないかと疑問に思いました。過去 10 年にわたって、彼はそれが可能であることを発見しました。
現代ミステリーの資料
キュービットは、2012 年に決定不可能性を大規模な量子システムとの衝突コースに置きました。
He, Pérez-García and their colleague Michael Wolf had gotten together for coffee during a conference in the Austrian Alps to debate whether a niche problem might be undecidable. When Wolf suggested they put that problem aside and instead tackle the decidability of one of the biggest problems in quantum physics, not even he suspected they might actually succeed.
「それは冗談から始まりました。それから私たちはアイデアを練り始めました」とペレスガルシアは言いました。
Wolf proposed targeting a defining property of every quantum system called the spectral gap, which refers to how much energy it takes to jostle a system out of its lowest energy state.これを行うのにある程度の力が必要な場合、システムには「ギャップ」が生じます。エネルギーを注入しなくても、いつでも興奮できるのであれば、それは「ギャップレス」です。 The spectral gap determines the color that shines from a neon sign, what a material will do when you remove all heat from it, and — in a different context — what the mass of the proton should be.多くの場合、物理学者は特定の原子または材料のスペクトル ギャップを計算できます。他の多くの場合、それはできません。陽子が正の質量を持つはずであることを第一原理から厳密に証明できる人には、100 万ドルの賞金が待っています。
