Skip to content
←

필사 모드: 普遍的な概念としての計算 — 何が堅牢で、何が誇張なのか

日本語
0%
정확도 0%
💡 왼쪽 원문을 읽으면서 오른쪽에 따라 써보세요. Tab 키로 힌트를 받을 수 있습니다.

はじめに — 一つの言葉に隠れた二つの異なる主張

Tim Roughgardenが教える「普遍的で根本的な概念としての計算(Computation as a universal and fundamental concept)」という短い講義が、このところ話題になっています。タイトルは大きな、ほとんど形而上学的な読み方を誘います。計算とは宇宙が何らかの形でそれでできている素材であり、銀河からニューロンまで、実は走っているプログラムなのだ、というような読み方です。

ところが実際の中身を読むと、はるかに抑制が効いていて、正直なところより堅牢です。計算可能性と計算量の理論を落ち着いて概観する講義です。チューリングの1936年の結果、停止性問題、なぜある問題は巧妙なアルゴリズムに屈し、ある問題は抵抗するのか、そしてPとNP。Roughgardenは計算量の理論家で(スタンフォードとコロンビアを経て、いまは高等研究所(Institute for Advanced Study)に在籍しています)、講義は終始しっかりした数学の地盤の上にとどまります。予備知識は要りません。

つまり「普遍的で根本的」という言葉は、実はまったく異なる二つの主張を抱えています。一つは正確で、証明可能で、本当に深い。もう一つは魅力的だが滑りやすい形而上学的な命題です。この二つを切り分けておくことが、この記事のすべてです。

講義が実際に述べていること

講義は一見単純な問いで幕を開けます。コンピュータにできないことはあるのか。そして本物のコンピュータが登場する十年前、1936年のチューリングの仕事で答えます。チューリングの想像上の機械は、衝撃的な事実を一緒に携えてきました。どれだけ時間やハードウェアを注ぎ込んでも、どんなアルゴリズムでも決して解けない問題がある、というものです。このプログラムはいつか止まるのか、それとも永遠に回り続けるのかを問う停止性問題は、いかなるコンピュータでも解けないことが証明されています。

「証明されている」という箇所が重要です。これは「遅すぎる」とか「メモリが足りない」ではありません。ゲーデルの不完全性と同じ系譜に属する数学の壁です。講義はヒルベルト、ゲーデル、フォン・ノイマンへと続く系譜を伝説ではなく歴史として扱い、アルゴリズムに何ができるかを追う伝統と、その限界を追う伝統とが、ゆっくり一点へ収束していく様子を示します。

そこから講義はより微妙な問いへ舵を切ります。コンピュータが 解ける 問題のうち、どれを速く解けるのか。ある問題は、ダイクストラの最短経路やカラツバの高速乗算のように、たった一つの巧妙な着想に崩れます。巡回セールスマン問題のような別の問題は、頑として抵抗します。そして驚くべき発見が、この難しい問題を数千個まとめて結び付けます。NP完全性を通じて、それらは違う衣装を着た同じ問題なのです。

そのすべてがPとNPへ収束します。講義はこれを、正確にも、計算機科学で最も重要な未解決問題であり数学の大きな難問の一つと呼びます。ある場面は「私たちが暮らしているかもしれない二つの世界」という枠で提示されます。難しく見える問題が実は易しい世界と、私たちがおそらく暮らしている、そうではない世界です。講義はその答えが暗号、AI、量子計算に何を意味するのかを問いながら締めくくられます。

「普遍」という言葉が実際に働く地点

誇張を取り払っても、計算を普遍的と呼ぶ本当の理由があります。そしてそれは二つの形でやってきます。

一つ目は モデル非依存性 です。チューリング機械、チャーチのラムダ計算、レジスタ機械、その他あらゆる合理的な「実効的手続き」のモデルは、まったく同じ関数の集合を計算することが判明します。チャーチとチューリングは1936年に正反対の方向から出発し、同じ場所にたどり着きました。その偶然の一致こそがチャーチ=チューリングのテーゼの中身であり、計算が単なる装置ではなく一つの概念である理由です。同じ計算がシリコンの上でも、紙の上でも、ドミノの上でも、さらにはウルフラムのルール110のように単純なセルオートマトンの上でも走ります。ルール110はチューリング完全です。土台となる素材は問題になりません。これは深く、まったく自明でない事実です。

二つ目は NP完全性 で、これは計算そのものの内部にある別種の普遍性です。スケジューリング、チップの配置、パズル解き、互いに無関係に見える無数の問題が、証明可能に同値です。そのうちたった一つに対する本当に速いアルゴリズムは、そのままそのすべてに対する速いアルゴリズムになります。これは比喩でも類推でもありません。定理であり、世界がこう組み上がっていること自体が驚きです。

そして計算不可能性は、「根本的」という言葉を大げさではなく誠実に保ちます。停止性問題は、未来のどんなハードウェアも、どんな量子の手品も、どんな予算も決して越えられない一線を引きます。自らの永続的な限界を、推測ではなく証明できる分野は、その言葉を使う資格を得ているのです。

どこから誇張になるのか

以上のどれも、宇宙がコンピュータだとも、あなたの心がソフトウェアだとも言っていません。それらは別個の、はるかに大きな主張であり、講義はそのどちらもしません。証明可能な版から形而上学的な版へと滑り落ちる、まさにその地点で、たいてい慎重な思考は死にます。

最も広い版であるデジタル物理学は、長い系譜を持ちます。コンラート・ツーゼの「計算する空間(Rechnender Raum)」(1969)、ジョン・ホイーラーの「it from bit」、ウルフラムの計算的同値性の原理、そしてより最近では宇宙を書き換え系としてモデル化する彼の物理プロジェクト。真剣で想像力に富んだ発想です。しかし「すべては計算だ」には故障モードがあります。考えうるあらゆる観測が、宇宙は計算しているという主張と等しく両立するなら、その主張は何も予測せず、何も排除しません。間違えようのない言明は理論ではなく、一つの枠組みにすぎません。

誠実な中間地帯は、物理的チャーチ=チューリングのテーゼです。どんな物理過程もチューリング機械でシミュレートできる、という主張です。これは本当に 反証可能 です。計算不可能なものを計算する物理装置、つまり本物の超計算機を作れば、このテーゼは死にます。注目すべきは、量子コンピュータがこれを しない ことです。量子コンピュータはチューリング機械が計算できるのと同じ関数を計算し、ただ時に劇的に速いだけです。これは効率についての主張であって、計算可能性についての主張ではありません。ドイチュの1985年の仕事がこの物理的な版を舞台に載せ、リスクを取るからこそ尊重されます。

同じ規律が心にも当てはまります。計算が認知を見るための強力なレンズであること、すなわち心の計算理論は、生産的な研究プログラムです。一方、脳が文字どおり計算以外の何ものでもないというのは、定理ではなく論争中の哲学的立場です。一つの関数が異なるハードウェアで走りうるという良い着想である多重実現可能性は、「生物と心はただの計算だ」という飛躍を許可しません。多くを明かすレンズは、実在がそのレンズでできているという主張と同じではありません。

おわりに

実際に擁護できる「計算は普遍的で根本的だ」の版は、講義が教えるそれです。モデル非依存性、絶対的な計算不可能性、難しい問題どうしの隠れた同値性、そしてPとNPという未解決の問い。開発者としてこれは胸に刻む価値があります。どの壁が永続的で(計算不可能な問題、そしてほぼ確実にNP困難な問題)、どの壁が現時点のものにすぎないかを教えてくれるからです。

実在それ自体が計算だという、より大きな物語は、手に一つの問いを握って読む価値があります。この版は危険な予測をするのか、それともどんな結果も吸収できるほど伸縮する比喩なのか。物理的チャーチ=チューリングのテーゼはその試験に通ります。「宇宙はコンピュータだ、以上」はたいてい通らず、その差は小さくありません。

Roughgardenの講義は、過小評価されやすいまさにその理由で、時間を割く価値があります。堅固な地盤の上にとどまり、誰かが宇宙へ手を伸ばす前に、どれだけ多くのものが本当にそこにあるのかを見せてくれます。モデル非依存性、確かな限界、深い同値性です。

参考資料

현재 단락 (1/24)

Tim Roughgardenが教える「普遍的で根本的な概念としての計算(Computation as a universal and fundamental concept)」という短い講義が、この...

작성 글자: 0자원문 글자: 3,993자작성 단락: 0/24