過去・現在・未来

目の前から、人間が作ったもの、人間に関わるものを、すべて消してみましょう。それでも、自然はあるがままの姿で、広がっているように思えます。野に咲く花も、空を飛ぶ鳥も、木々をゆらす風も、夜空の星も。 ただ、そうした空想を行うことが、だんだん、難しくなっています。人間のいない世界のイメージといえば、「廃墟」のイメージを持つ人がむしろ多いかもしれません。それでも自然は残ると僕は思うのですが。それは、私たちの日常的な視界から、自然が見えにくくなっているからだと思います。 一方で、現代は科学の時代だと多くの人が考えています。ただ、科学の主要な対象である自然から、私たちは、どんどん遠ざかっています。そのことは、自然に対する関心だけでなく、いずれ、科学に対する関心をも失わせる力として働くことになると感じています。 科学を私たちにとって疎遠なものにする、もう一つの大きな力があります。 それは、そもそも、科学が歴史的には、冒頭に述べたような素朴な自然観から、自分を意識的に分離することで生まれたことによるものです。 私たちの遠い遠い祖先は、自然と深く結びついていました。というより、圧倒的な自然の力の前に人間は無力でした。ただ、自然に対する畏怖・感嘆の念を持ち得たことは、人間を他の動物とを区別するものです。それは、その後、宗教・芸術・科学等に枝わかれしていく、すべての人間の営みの原始の共通の起源になりました。 時間を何万年か進めます。話は少し飛躍します。 現代では、科学は、主要に「科学者」という専門家集団によって担われています。彼らは、特殊な訓練を受け、特殊な言葉で話します。その言葉は、一般には、わかりにくいものです。 「科学者」が人口に占める割合は、大きなものではありません。おそらく宗教が支配的であった時代、どの村々にも必ず存在していた神職者が人口の中で占めていた比率を上回ることはないと思います。 （科学の世界では、博士号を取得した科学者の卵たちの「過剰」に悩まされています。それは、社会的には「構造的な問題」なのですが、僕は、むしろ、歴史的には必然的な傾向のように考えることができると思っています。） それでは、なぜ、多くの人は、実際にはかなり疎遠なものでしかない科学に対して、現代は「科学の時代」だと考えるのでしょう？ その理由は、明確だと思います。「科学」の応用としての「技術」が、現代の

3月、4月に開催する二つのセミナー「エンタングルする自然 / エンタングルする認識」の参考資料をいくつか紹介したいと思います。 　エンタングルメントの基本 　●「エンタングルメントで理解する量子の世界」           https://www.marulabo.net/docs/entangle-talk/ エンタングルメントの基本的な性質と量子論的な定式化について説明しています。是非、目を通していただければと思います。　 　歴史的背景 　●「コンピュータ・サイエンスの現在 — MIP*=RE定理とは何か？」　　  　　　 　　　 https://www.marulabo.net/docs/cs-mipstar/ 計算可能性理論から複雑性理論の誕生というコンピュータ・サイエンスの歴史の振り返りの中でMIP*=REを位置付けています。 　複雑性理論 　● 「チューリングマシンの拡大と複雑性」 　　　 https://www.marulabo.net/docs/turing-complex/ 第一部の「複雑さについて考える」は、複雑性理論は、どういう問題意識から生まれたものなのか、それがどのように対象を拡大していったかを説明しています。 　Interactive Proof 　●「Interactive Proofと複雑性」 　　　 https://www.marulabo.net/docs/ip-complexity/ Interactive Proofの発展についてです。 　　MIP*=RE 　●「MIP*=RE 入門– Interactive Proofとnonlocal ゲーム」 　　　  https://www.marulabo.net/docs/mipstar/ MIP*=RE定理の概要の説明です。

【「エンタングルする知性」の認識 -- MIP*=RE 】 量子コンピュータの計算能力は、素晴らしいものです。それは、ある問題群（例えば、素因数分解のような）に対しては、古典コンピュータの計算能力の指数関数的高速化を可能にします。 量子コンピュータのアイデアの登場とともに、量子コンピュータが古典コンピュータで解くには指数関数的時間のかかる「NP-完全問題」を多項式時間で解くのではという期待がうまれました。ただ、それは不可能です。 先日の複雑性クラスの関係図を、改めて見て欲しいのですが、「NP-完全」のクラスは、量子コンピュータが多項式時間で解くことができる BQP クラスのはるか外側に存在しています。 今では、GPT3でさえ、「量子コンピューターを使用して、NP完全問題を多項式時間で解決することは可能ですか？」と質問すれば、「量子コンピューターを使用してNP完全問題を多項式時間で解くことはできません。」と答えてくれます。 それでは、量子の力を借りた人間の計算能力拡大の試み、それは人間の認識能力の拡大の試みを意味するのですが、それは現在のスタイルの量子コンピュータの進化の延長上の限界 BQPで頭打ちなのでしょうか？　 もっとも、こうした問題意識自体が、そもそも混乱していることは、次のように考えればわかります。チューリングマシンが多項式時間で計算可能な能力の限界 P は、人間＝機械の双方の計算能力の限界と見做せるのですが、BQPは機械のみが持ちうる能力です。人間は機械の助けなしには単独ではその能力を持つことは出来ません。 ですので、量子の力を借りた人間の認識能力の拡大というのは、量子機械の力を借りた人間の認識能力の拡大に他なりません。人間の認識能力の未来を考えるのなら、裸の人間の生まれ持った能力だけで、人間の認識能力を語ることは出来ないのです。宇宙のどこかには、古典チューリングマシンではなく量子チューリングマシンと同じ計算能力を、単独で生得的に持つ知的生命が存在するかもしれないのですが。 話がSFみたいになってきたのですが、2020年に証明された「MIP*=RE定理」も、それが想定していることを考えれば、SFみたいな話に聞こえるかもしれません。 先に、「数学的全能者」と「人間」の対話によって認識を拡大する枠組みとして「対話型証明  Interactive Proof」を

【 量子コンピュータの能力の認識 -- BQPクラス 】 先に、「人間の能力をコンピュータが超える」という「シンギュラリティ」の議論は、かなり怪しいと書きました。その大きな理由の一つは、「人間の能力」と一括りにするけど、人間の能力は非常に多様で複雑だからです。 例えば、前回の議論では、「全能者」の存在を仮定して「全能者」と「人間」の対話で認識できることを考えようというアプローチを紹介しました。そうした新しい推論方法を思いつく能力を機械が持てるかどうか、僕は懐疑的です。それにしても、そうしたアイデアやそのアプローチで得られる認識結果は、最終的には「人間の能力」に属します。 もっとも僕は、人間の数学的・論理的推論能力に関して言えば、それは機械的なモデルを持つと考えています。それは、おそらくチューリング・マシンの持つ能力に等しいと考えています。また、先日紹介したInteractive Proofのアプローチは、きちんと数学的に定義できます。 人間と機械の能力の比較は、いろいろ難しい問題があるのですが、機械と機械の能力の比較は、どちらも人間が作ったものですので、それよりは簡単にできます。この点で、近年、重要な認識が生まれています。 それは、私たちが普段使っているコンピュータの計算能力を、量子コンピュータの計算能力が上回っている認識が、理論的にだけではなく、実験的にも確立され始めているということです。 私たちが普段使っているコンピュータを「古典コンピュータ」と呼ぶことにします。今使っているものを「古典」と呼ぶのは抵抗があるかもしれませんが。どちらも人間から見れば機械です。どちらも「コンピュータ」と呼ばれます。ただその動作原理は全く異なった機械です。その違いをはっっきりさせるため、「古典」「量子」を頭につけます。 機械だけの世界に限れば、量子コンピュータの登場を、古典コンピュータに対する「シンギュラリティ」と呼ぶことは可能です。機械＝コンピュータの世界では、それは「量子優越性」と呼ばれています。 2019年の10月23日は、特別な日です。それは、Googleが、古典コンピュータに対して量子コンピュータの能力が遥かに高いこと、「量子優越性」を実験的に実証した日です。 この点については、丸山の資料「量子コンピュータの現在 — 量子優越性のマイルストーンの達成 —」https://w

【「全能者」との対話で得られる認識 -- Interactive Proof 】 なんか怪しいタイトルですね。 怪しいついでに、もう一つ怪しい話を。 今から見ればだいぶ前になりますが、「AI=人工知能」の大ブレイクが起きたとき、盛んに使われたのが「シンギュラリティ」という言葉です。機械の知能が人間の知能を超える時がいつか来る。それをこの言葉で呼んでいたように思います。 ただ、この言葉やその意味に、僕はいささか「怪しさ」を感じていました。なにが人間の知能の限界であるのか？　また、シンギュラリティの到来は、機械の知能が人間の知能をどのように超えることを意味しているのか？　当時流行した議論では、そうした基本的なことが、あまりよく考えられていないように感じました。 こうした問題を徹底的に考えるのは意味があることだと、僕は考えています。冒頭のタイトルの「全能者」は、いわば、機械の「シンギュラリティ」をはるかに超えた能力の持ち主です。ただし、「対話型証明 Interactive Proof」に登場する架空の存在です。 「対話型証明 Interactive Proof」というのは、こうした「全能者」と普通の人間が「対話」をしたときに、何が分かるかを考えようという枠組みです。 アーサー王伝説では、アーサーに仕えるマーリンという魔法使いが出てくるのですが、「対話型証明 Interactive Proof」では、「全能者」をマーリン、「全能者」と対話する普通の人間をアーサーと呼ぶことがあります。 アーサー王伝説のマーリンは、魔法使いですので、火を吹く竜を召喚したり、人間を豚に変えたり、文字通りなんでも出来るのですが、Interactive Proofのマーリンは、そういう魔法を使えるわけではありません。 ただ、理論的・数学的能力においては、彼は「全能」です。もし、リーマン予想が正しいのなら、彼はそれを瞬時に証明できます。もちろん、「全能」と言っても、数学的に証明不可能な 1+1=3 を証明できるわけではありません。 Interactive Proofの枠組みでは、「全能者 マーリン」を「証明者 Prover」と呼ぶことがあります。彼は、全知全能で、どんな問題も瞬時に答えを返す能力をもっています。ただし、ここが重要なのですが、彼は誠実ではなく、時々、人を欺く嘘をつきます。 一方の「普通の

「僕はAndroid」だ。 それでclubhouseに部屋を持てない。（iPadで入ることができたのだが、まだ始めていない。） 「僕はうなぎ」「彼はたぬき」「彼女はキツネ」 米津の「迷える羊」というアルバムに、「馬と鹿」という曲を見つけた時、ちょっと笑った。動物づくしをしたいわけではないのだが。実は、彼はAndroidだったので、clubhouseに入れなかったらしい。 冒頭のフレーズは、ある女性作家が、「女性」と「小説」について質問された時、答えた言葉だ。男性との差別に苦しむ女性、創作を志す女性に対するアドバイスだ。 　「自分自身の部屋を持ちなさい。そして、お金も。」 興味深いのは、彼女がこのエッセイで紹介している、かつて、女性は自分の才能を発揮することが、いかに困難だったかをしめす、次のようなエピソードだ。（若干、補足が必要なのだが、それは後日。） シェイクスピアには、Judithという、彼と同じように才能に溢れた妹がいた。兄のように学校に行くことを許されず、両親に望まぬ結婚を押し付けられた彼女は、家出をしてロンドンに出て、兄と同じ役者の道を目指す。ただ、その道は厳しかった。 ある冬の夜、彼女は自殺する。彼女は、Elephant ＆ Castle 郊外の、今はバスが通っている十字路の近くに埋葬された。 　「自分自身の部屋を持ちなさい。そして、お金も。」 僕にとっても、いいアドバイスだと思う。 --------------------------------------------- Shakespeare had a wonderfully gifted sister, called Judith, let us say. Shakespeare himself went, very probably,—his mother was an heiress—to the grammar school, where he may have learnt Latin—Ovid, Virgil and Horace—and the elements of grammar and logic. He was, it is well known, a wild boy who poached rabbits, perhaps shot a deer, and had, ra

 【 3/27 「楽しい科学」ダイジェスト -- エンタングルメントをめぐるドラマ #4 】 【「時空」を生み出す「原理」としてのエンタングルメント 】 アインシュタインは、量子論の中に二つの量子の奇妙なもつれあった関係が存在することを発見して、それを「パラドックス」として提示しました。三人の著者 Einstein, Podolsky, Rosenの頭文字をとって、「EPR論文」と呼ばれます。1935年の5月のことです。 二ヶ月後の7月に、アインシュタインはローゼンとともに、"The Particle Problem in the General Theory of Relativity" 「相対性の一般理論における粒子の問題」という論文を公開します。この論文を「ER論文」と呼びます。   このER論文は、二つのブラックホールを結ぶ「橋」が存在しうることを指摘した論文です。この「橋」は、"Einstein-Rosen Bridge" と呼ばれ、別名「ワームホール」とも呼ばれます。 アインシュタインは、1935年に、「エンタングルメント」（ただし、パラドックスとして）と「ワームホール」を発見しているのです。同時期にアインシュタインによってなされた、この二つの発見に何か関連があるのでしょうか？　 本来は、80年前になされるべきこうした問いかけを、現代に蘇らせたのは、あのマルデセーナとブラックホール／量子重力の専門家のサスキンドでした。 2013年の論文で、二人は、1935年にアインシュタインが発見した「エンタングルメント」と二つのブラックホールを結ぶ「ワームホール」は、スケールが全く違うのですが、同じものだという大胆な仮説を提示します。 「二つのブラックホールの間のワームホールは、二つのブラックホールのエンタングルメントによって生成される。」 時空の性質を記述する相対論（重力理論）と量子の世界を記述する場の量子論に「対応」が存在することをマルデセーナが発見したことは、既に述べました。ただ、その対応が、具体的にどんなものかについては、述べてきませんでした。 マルデセーナとサスキンドの主張は、AdS/CFT対応のもとで、相対論に現れる二つのブラックホールを結びつけるワームホールと、量子論に現れる二つの量子のエンタングルメントは、「対応

【エンタングルメントのエントロピー】 マルデセーナの量子論と相対論（重力理論）の「対応」の発見をきっかけに、エンタングルメントの理解は、飛躍的に深まります。 突破口を開いたのは、二人の日本人、笠真生と高柳匡です。 「「時空」が、二つの部分 AとBに別れているとする。AとBの「境界部分」は、「時空」の「境界」なので、マルデセーナの理論にしたがって量子論で記述できるはず。」 「やってみたら、この「境界」は、なんと、量子論の「エンタングルメント」のエントロピーに対応するんだ！」 彼らは、「エンタングルメント」がエントロピーを持つことの、最初の発見者となります。（2006年） 先にマルデセーナの時空の「境界」の重要性の発見は、「再発見」かもしれないと書いたのですが、それには訳があります。時計を50年ほど巻き戻します。 ブラックホールは、観測可能な物理量としては、質量・電荷・角運動量の三つしか持たないと信じられてきました。ブラックホールは、極めて単純な構造の存在で、上の三つの物理量でその特徴を完全に記述できると。それを、物理学者のウィーラーは、「ブラックホールには毛がない」と表現しました。（「毛は、三本しかない」という意味です） 1973年、ベッケンシュタインは、これを覆す発見をします。彼は、ブラックホールが、先の三つの物理量の他に、エントロピー を持つこと、しかも、そのエントロピーが、ブラックホールの「地平」の表面積に比例することを見出します。 ブラックホールの「地平」とは、その一線を超えると、なにものも（光でさえ！）ブラックホールから脱出できなくなる、ブラックホールを周辺の時空とをへだてる「境界」のことです。 通常、ある空間のエントロピーは、その空間の体積に比例します。ブラックホールのエントロピーが、ブラックホールの体積（質量と言ってもいいです）ではなく、その地平の面積に比例すると言うのは、少し意外に思われるかもしれません。こうしたタイプの物理法則を「エリア則に従う」といいます。 笠-高柳によるエンタングルメントがエントロピーを持つことの発見は、このベッケンシュタインのブラックホールがエントロピーを持つことの発見に匹敵する重要な発見です。 笠-高柳の発見に刺激されて、ラムズダンクが続きます。彼は、こう考えます。（2010年） 「二つの時空 A, B があったとする。二

【3/27 「楽しい科学」ダイジェスト -- エンタングルメントをめぐるドラマ #2 】 量子論と相対論の「対応」の発見 エンタングルメントの発見をきっかけとした、アインシュタインの量子論批判と、ベルによるそれへの反論、量子論の擁護を見てきました。 ただ、こうした「論争」が、20世紀の科学の主要な関心事だったわけではありません。極微な世界を記述する量子力学と巨大な時空を記述する重力の理論である相対論という二つの物理学理論は、それぞれの領域で、大きな成功をおさめてきました。我々の物質・生命・宇宙に対する理解は、20世紀をつうじて飛躍的に進みました。 ただ、それぞれ異なる理論体系に基づく物理学が二つあるというのは、奇妙なことです。少なくない物理学者が、「これこそが、物理学の中心問題だ」と信じて、量子論と相対論を一つの物理学に「統一」する課題に取り組んできました。ただ、それは、20世紀には成功することはありませんでした。 20世紀も終わりの1997年、マルデセーナは21世紀の物理学の扉を開く重要な発見をします。 それは、d+1次元の時空を記述する重力理論AdS(Anti-de Sitter Space)と、d次元の場の量子理論CFT(Conformal Field Theory)が「対応」していることの発見です。この対応を「AdS/CFT対応」と言います。 この「対応」では、重力理論が d+1次元で量子論がd次元ですので、相対論（重力理論）と量子論の次元が一つずれていることに注意してください。スープの入った缶詰で例えて言えば、相対論は缶のない中身のスープの理論で、量子論はスープのないスープをつつむ缶の理論だと言うことです。 このことは、20世紀の多くの物理学者の努力にもかかわらず、相対論と量子論の「統一」の試みが成功しなかった理由を、ある意味で説明します。二つの理論は、棲んでいる世界の次元が違うのです。ブリキの缶の外側をいくらなぞっても、スープのことはわからないし、逆に、いくらスープを舐めても、缶のことはわからないのと同じです。 それにもかかわらず、重要なことは、二つの理論には「対応」が存在すると言うことです。 マルデセーナの発見は、「スープと缶は、無関係ではなく関係がある。」ということでした。「缶を調べれば、スープのことがわかり、スープを調べれば缶のことがわかる！」

【3/27 「楽しい科学」ダイジェスト -- エンタングルメントをめぐるドラマ #1】 科学の世界は、いろいろなドラマに溢れています。 今回の 3/27「楽しい科学」では、「エンタングルメント」を舞台にしたドラマを紹介したいと思います。https://science-entanglement.peatix.com/ ------------------------------------------------------------ 最初の登場人物はアインシュタインです。彼は、量子論では、二つの量子がもつれあう奇妙な状態が現れることを発見します。1935年のことです。その現象に「エンタングルメント」という名前をつけたのは、シュレディンガーだと言われています。 アインシュタインは、もつれあう量子は強く関連した性質を持ち、一方の性質は他方の性質から簡単に決定できること、そのうえ、こうしたもつれあいは、二つの量子の距離に依存しないことに気付きます。 このことは、二つの量子がどんなに離れていても、一方の量子の状態を観測すれば、テレパシーのように、他方の量子の状態が分かることを意味します。「そんな馬鹿なことはありえない。それだと、光のスピードを超えて情報が伝わることになるじゃないか。」 彼は、量子論が不完全な理論であることを示す「パラドックス」として、「エンタングルメント」を提示したのです。ところが、ボーアをはじめとする量子論の陣営は、このアインシュタインの「量子論批判」を、事実上、無視します。 アインシュタインの「神はサイコロをふらない」という言葉がしめすように、彼は最後まで、量子論に懐疑的であったと言われています。 エンタングルメントをめぐるドラマで、アインシュタインに次ぐ重要な役割を演じる第二の登場人物は、ジョン・ベルです。彼と彼の業績が、多くの人にはあまり知られていないのは、とても残念なことです。 ベルは、アインシュタインらが量子論の不完全さを解決するものとして推進した「隠れた変数」理論を、理論的に否定することに成功します。しかも、自然が、「隠れた変数」理論という古典論に従うか、あるいはエンタングルメントを含む量子論に従うかは、実験的に検証できると指摘します。 事実、アスペたちは、1982年、ベルの主張が正しいことを実験で実証します。ここに、アインシュタインの発見か

3月のマルレクは、「自然科学概論 -- エンタングルする自然」というテーマで行います。 https://science-entanglement.peatix.com/ 21世紀の科学・技術の変化を牽引する力の一つが、「自然の至る所に、エンタングルメントは存在し作用している」という「エンタングルメントの遍在」という認識の拡大だという視点から、新しい自然科学のオーバービューを行いたいと思います。 次のようなトピックスを取りあげる予定です。 　● エンタングルメント小史 -- 「パラドックス」から「原理」へ 　● エンタングルメントの科学的認識の理論へのインパクト 　● 量子通信・量子暗号 -- エンタングルメントの技術的応用 　● 物質理論とエンタングルメント 　● 物理学の新しい展開 -- 時空を生み出すエンタングルメント  それぞれのトピックに深入りはしません。いま、何が起きているか、それがどう言う意味を持っているのかを、「概論」として、わかりやすく伝えられたらと思っています。 今回のセミナーの Hard Coreは、最後の「物理学の新しい展開」のトピックなのですが、その内容は、次のセミナーに引継ぎたいと思います。 　4月 マルレク基礎「シャノンの情報理論を学ぼう！ -- 情報とエントロピー」 　5月 マルゼミ      「物理学の新しい展開 -- 時空を生み出すエンタングルメント 」 ご期待ください。

 【Accountable Nature】 白い大きな壁に「可解」と言う文字が書かれていた。 昨日テレビで見た見た、松山智一の上海での個展の会場の入り口の映像だ。 気になって調べてみる。 「Accountable Nature 自然 --- 可解」と言うのが、個展のタイトルだった。 https://bijutsutecho.com/magazine/news/exhibition/22908 松山は英語がうまい。Accountableを「可解」と訳すのは、あまり見たことがなかったのだが。"Accountable Nature"、面白いコンセプトだと思う。 先の「美術手帖」の解説では、「 自然とデジタル、現実と非現実といったいまの時代を構築する不安定な二項対立を描きだす作品群 」だという。あるいは、作家本人もそう考えているのかもしれないが。 ただ、"Accountable Nature" は、「可解な自然」ではないか？　そこには、「二項対立」はない。 「人間と自然」は、「 いまの時代を構築する不安定な二項対立 」の主要な焦点のひとつだ。科学もまた、人間による自然理解の試みとして、この二項を媒介するものだと、僕は思っている。 「説明可能性」としての"Accountable"は、「ことばで表現できる」ことだ。"Countable"であることもまた、「ことばで表現できる」ことと同義である。「可算＝数え上げることができること」を、countableとかenumerableというのだが、 科学では、「可算」であることは、問題が「可解」であることの条件だ。 もっとも、彼の表現をになっているのは、ことばではない。彼が志向しているのも科学ではないだろう。 だから、僕らは、科学とは限らない人間による自然の表現を、あるいは、自然と人間の媒介を人間に可能にするものは、何かを考えないといけない。 「自然と人間」「科学と表現」「可解なものと不可解なもの」「有限と無限」 ...... たまたま、松山が出ていた前日の番組にBumpの藤原基央が出ていた。この前、引用した詩は、藤原のものだ。藤原と松山は、ほぼ同じ世代だということに気づく。

コロナの年、何をしてきたかまとめてみました。 毎月一回のペースでセミナーを開催しました。 3月以降のセミナーは、全てオンラインでした。 YouTubeの利用を拡大しました。 MaruLabo Top Page    (MaruLaboサイト) Maruyama Lectures 　(YouTubeサイト) 21/02/26 マルゼミ「 チューリングマシンの拡大と複雑性理論 」 20/01/29 マルレク基礎「 チューリングマシンを学ぼう！ 」 20/12/25 マルゼミ「 MIP*=RE入門 」 20/11/27 マルレク「 コンピュータサイエンスの現在 — MIP*=RE定理とは何か 」 20/10/15 マルレク「 量子コンピュータ入門 — 量子コンピュータと人工知能 」 20/09/18 マルレク「 人工知能と計算科学 」 20/08/28 マルゼミ「 量子通信入門 」 20/08/18 公開資料 「 MIP*=RE References 」 20/07/26 マルレク基礎「 エンタングルメントで理解する量子の世界 」 20/06/30 楽しい数学　「 2のn乗の話（チューリングマシンの話） 」 20/06/20 マルレク基礎「 ケット|k> で理解する量子の世界 」 20/05/15 マルレク基礎「 たとえ話で理解する量子の世界 」 20/05/05 マルレク「 AWSでの形式手法の利用 」 20/03/27 マルゼミ「 論理学入門 II — ラムダ計算と関数型言語 」  20/02/17 マルレク「 量子コンピュータの現在 — 量子優越性のマイルストーンの達成 」 20/01/28 マルゼミ「 論理学入門 I 」 19/11/28 マルレク「I T技術とCoqの世界 –証明 = プログラム = 計算の意味を考える 」 19/11/07 ハンズオン「 はじめてのCoq 」

先に見てきたのは、図の左側の n-exponential な時間で「検証可能」な複雑性を考えて、複雑性概念を拡張すると、ついには、「帰納的可算」のクラスに至るという話である。 n-exponential な数は、たとえそれがどんなに巨大なものであっても、有限な自然数であることに変わりはない。ただ、その有限の「無限」な連鎖の果てに、良く定義されたある意味自然な概念が、改めて、たち現れるのだ。 振り返ってみよう。 我々は、無限のものを認識できない。まず、認識の対象を形式的に有限な手段で定義可能なものに限る。「帰納的可算」というのは、そうした概念である。ただ、そこには、キチンと定義はできても、計算不可能だったり証明できないものが含まれる。 それで、「帰納的可算」の概念に手を入れ、キチンと定義され、かつ、計算可能なもの・証明可能なものを「帰納的」なものとして再定義する。「チューリング・マシンで実効的に計算可能なものが、計算可能である。」という「チャーチ・チューリングのテーゼ」は「計算可能性理論」（それは、「計算不可能性理論」でもあるのだが）の、ある意味、完成形である。 ただ、この「チャーチ・チューリングのテーゼ」の定義に従えば、「計算可能」であるはずなのだが、現実的には、どうしても計算できないものがたくさんあることに気付く。こうした実際には手に負えないものを、現実的に計算可能なものとを区別しようという動きが生まれる。「計算複雑性」の理論誕生の背景は、そうしたものだと思う。 こうして、「多項式時間」で計算できるものと、「多項式時間」では計算できないものとを区別しようという一つの基準が導入される。この基準は、ある意味合理的なものであった。1970年代に登場した複雑性理論は、コンピュータ・サイエンスの中心分野の一つとして発展し、成功する。それはいいことだ。 ただ、悪いニュースもある。いつの間にか、計算を科学する様々な分野に、次のような考えが生まれてくる。それは、もとの「チャーチ・チューリングのテーゼ」を修正した、「チューリング・マシンで多項式時間で計算可能なものが、計算可能である。」という考えが、「計算可能性」の定義として広まりはじめたことだ。それを「拡大されたチャーチ・チューリングのテーゼ」という。 「拡大されたチャーチ・チューリングのテーゼ」が、おそらく「誤り」であるだろうと

前回、次のような、二つの対をなす複雑性のクラスを三つほど見てきた。  1.   NP        \(O(3^n)\)の証明時間               P         \(O(n)\)の検証時間   2.  NEXP     \(O(3^{2^n})\)の証明時間         EXP      \(O(2^n)\)の検証時間   3.  NEEXP   \(O(3^{2^{2^n}})\)の証明時間         EEXP    \(O(2^{2^n})\)の検証時間  一つ確認しておきたいのは、2番目の NEXPクラスは、NPクラスではないということである。NPクラスは、証明のの検証が多項式時間で終わるクラスのことだが、このNEXPクラスは、検証に指数関数的時間を要するクラスである。多項式時間では、このクラスの検証は終わらない。 同様に、3番目のNEEXPクラスは、NPクラスでもNEXPクラスでもない。それは、証明の検証に、はるかに長い時間を必要とする、それらよりずっと複雑なクラスである。 形から見れば、NP, NEXP, NEEXP, ...という延長上に、NEEEXPなり NEEEEXP ... といった複雑性クラスを考えることができそうである。また、それは、大きな認識の飛躍のようにも思えないかもしれない。 結果的には、確かにそうなのだが、そうしたアイデアは複雑性理論の中で、最初から「自然」に生まれたものではないことには注意が必要である。そのことは、複雑性理論の歴史を振り返ればわかる。 歴史的には、1番目の NPクラスとNP-完全の概念の定式化は、1971年の CookとLevinに遡る。この間紹介してきた「グラフの3色塗り分け問題」がNP-完全であることを示したのはKarpで1972年のことだ。1970年代初頭は、複雑性理論の創世記である。 2番目のNEXPクラスの特徴づけがなされ、その基本的な性質が解明されたのは、BabaiとFortnowとLundが、NEXP = MIP を証明した時である。MIPはMulti-Prover Interactive Proof である。1991年のことだ。1990年代、Interactive Proofの手法の導入によって、複雑性理論は新しい段階に入る。 3番目のNEEXPクラスの特徴づけをあたえたのは

n個の頂点を持つグラフが3色で塗り分けられるかという問題は、代表的なNP-完全問題である。n個の頂点が3色に塗られたグラフは、\(3^n\)個存在する。それらのグラフの中から「塗り分け」の条件を満たすグラフを探すのは、容易ではない。この問題への答えが「YES」であることを示すこと、すなわち、このグラフが3色の塗り分けを持つことを「証明」するのは「むずかしい」。 ただ、その「証明」は、「これがこのグラフの3色の塗り分けだ」という形をしているはずである。こうした「証明」が与えられた時、その「証明」が「正しい」か否かの「検証」は、n個の頂点が「塗り分け」の条件を満たしているかのチェックで、多項式時間で可能である。その「検証」は、元のNP問題より「やさしい」問題で、多項式時間のクラスPに属する。 こうした、PとNPの関係を拡張して、次のようなクラスを考えることができる。 \(2^n\)個の頂点を持つグラフが3色で塗り分けられるかという問題を考える。\(2^n\)個の頂点が3色に塗られたグラフは、\(3^{2^n}\)個存在する。それらのグラフの中から「塗り分け」の条件を満たすグラフを探すのは、もちろん容易ではない。この問題の複雑性クラスをNEXPと呼ぶ。 なぜ、NEXP（それは"N+EXP"だ）という名前がつくかは、次のように考えればいい。この問題が「YES」という解を持つなら、「これがこのグラフの3色の塗り分けだ」という「証明」を持つ。この「証明」が正しいことの「検証」は、\(2^n\)個の頂点を一つづつ調べて、それが「塗り分け」の条件を満たしているかチェックすればいい。 それは、\(3^{2^n}\)個のグラフを検索することの「むずかしさ」とくらべれば、\(2^n\)個の頂点のチェックは、はるかに「やさしい」ことだ。この「検証」の複雑性は、\(2^n\) すなわち、EXP(指数関数的時間の複雑性)に属することになる。 もちろん、EXPクラスは、けっして「やさしい」クラスではない。それは、PやNPよりもずっと複雑なクラスである。それにもかかわらず、NEXPクラスの「むずかしさ」と比べると、EXPクラスはずっと「やさしい」クラスなのだ。 同様に、\(2^{2^n}\)個の頂点を持つグラフが3色で塗り分けられるかという問題を考え、その複雑性NEEXPを考え

 【 グラフの３色塗り分け問題 】 先に「リーマン予想」と等価な「グラフの３色塗り分け問題」があると書いたのだが、グラフの問題に置き換えたからといって、問題がやさしくなるわけではないことを、確認しておこう。 グラフの頂点を、{r(赤) , g(緑) , b(青) }の三色で塗る場合の数がいくつあるかを考えよう。 頂点の数が1つの場合には、{r}, {g}, {b}の 3通り、 頂点の数が2つの場合には、{rr}, {gg}, {bb}, {rg}, {gr}, {gb}, {bg}, {rb}, {br} の 9通り. 一般に頂点の数がn個の場合には、\(3^n\) 通りになる。 頂点の数が20個で頂点が3色に塗られたグラフの数は、\(3^{20}\)である。一つのグラフを見つけるのに1nano秒かかるとしてこの操作は、多分、数秒で終わるだろう。 nが大きくなるにつれて、この\(3^n\)は急速に増大する。n=30となると、\(3^{30}\)という数のグラフを枚挙する操作は、\(3^{30}\) nano秒の時間を要する。それは現在の宇宙が生まれてから現在までの時間の100倍以上の時間が必要になる。 n=30程度であっても、総当たりで、三色グラフを全部数え上げるのは、ほぼ、不可能だ。（「リーマン予想」を表現するグラフが、頂点数が30程度ということはないだろう。） ただ、n個の頂点を持つグラフを3色で「塗り分けろ」というのは、同じ色を持つ頂点は辺で結ばれていてはいけないということだ。 だから、もし、誰かが頂点数30のグラフの「3色塗り分け」を与えたとしよう。この時、この「3色塗り分け」が「正しい塗り分け」になっているかの「検証」は、30個の頂点について、その頂点と辺で結ばれている隣り合う頂点が違う色であることをチェックすれば、簡単に終わる。 一般に、n個の頂点からなるグラフでは、一つの頂点に対して、辺で結ばれた頂点は多くてもn-1個しかない。辺で結ばれた頂点の色が違うことのチェックは、 高々、\(n(n-1)/2\)回のチェックで終わってしまう。これは多項式時間で検証可能である。

先の投稿でこう書きました。 「歴史的には、現代の「複雑性理論」は、NPという複雑性のクラスと「NP-完全」という概念の発見によって始まります。」 複雑性理論の歴史については、以前、角川さんで行った「人工知能を科学する」という連続セミナーの第一回「人工知能と複雑性理論」 https://www.marulabo.net/docs/20180927-kadokawa/ で詳しく触れています。 NP-完全については、この連続セミナーの第三回で、「人工知能と量子コンピュータ — NP-完全問題とその含意」というテーマでお話しをしました。 https://www.marulabo.net/docs/20181119-kadokawa/　 これらの資料を読んでいただければと思います。 ただ、残念なことにい、3年前の僕の認識には、いくつかの点で不十分なところがありました。 例えば、「数学とNP問題」というブログで、こう書いています。 https://maruyama097.blogspot.com/2018/09/np.html 「ただ、こうした考えに立って、数学の証明の「正しさ」が、多項式時間で「検証可能」だということは、数学の証明可能な問題全体が、NPクラスに属するということにならないか？ な、わけはない。（とも、思うのだが。）」 「な、わけはない。（とも、思うのだが。）」と思っていたのが間違いでした。最初の直感に従って進めばよかったのですが、自分で打ち消しています。多項式長の証明を持つ数学的命題の全体は、NP-完全の代表的な例だということを、僕は、Irit Dinurの講演を聴いて確信しました。 こうした認識に従えば、NP-完全な問題は、すべて共通の単一のアルゴリズムに「還元」できますので、もしも、ある人が、リーマン予想を証明したとすれば、その証明がどんなに長いものだったとしても、その証明に対応したグラフの3色塗り分け問題があることになります。 つまり、少し複雑なグラフでしょうが、そのグラフのノードを3色に塗り分けられることを示せば、リーマン予想を解くことができるグラフがあるということです。 「な、わけはない」 と思ってはいけないのです。「NP-完全」というのは、そういう性質を持つのです。それに、多項式長の証明を持つ数学的命題の全体は、NP-完全であるという認識は、「数学的

　リソースによる複雑性の階層 先に、「複雑さ」を、ある問題を計算するのに必要な時間とメモリーの大きさで分類するというアプローチを紹介しました。 ある時間\(T_0\)では解けないけれど、\(T_0\) より大きな時間 \(T_1\)では解ける 問題、あるいは、ある量のメモリー空間\(S_0\)では解けないけれど、\(S_0\) より大きなメモリー空間 \(S_1\)では解ける 問題を考えて、多くの計算リソース（時間、空間）を要する問題を「複雑な問題」と考えることは自然なことです。また、多くの計算リソースを要する問題を「むずかしい問題」、より少ない計算リソースを要する問題を「やさしい問題」と考えることができます。 こうした「時間複雑性」や「空間複雑性」といった階層が存在することは、ある問題をできるだけ効率的に、短いステップで少ないメモリーで書こうとするプログラマーが、日常的に意識していることです。 一つの問題には、それを解く複数のアルゴリズムが存在しえますので、ある問題にとって、それを解くアルゴリズムの数だけ具体的な実行計算複雑性が存在することになります。例えば、n個のものを大きさ順に並べ替えるSORT問題の実行計算複雑性は、bubble sortのアルゴリズムなら \(O(n^2)\)に、quick sort のアルゴリズムなら\(O(n log n)\)になります。  プログラマにとっての実践的な関心は、その下限を目指すことですが、下限を確定することは、理論的にも実践的にも簡単なことではありません。 　コルモゴロフの「複雑性」 複雑性については、今回のセミナーで扱うアプローチとは別の流儀があります。コルモゴロフは、ある対象の複雑性を「その対象を出力するプログラムの最小の大きさ」で定義します。これは、ある問題を解くアルゴリズムの実行計算複雑性の下限を追求するアプローチと、向いているベクトルはよく似ています。それをもっと抽象化・一般化したものです。 ある問題についての最小のプログラムを「エレガントなプログラム」と呼ぶことにすると、チャイティンは、「あるプログラムがエレガントであることを我々は証明できない」ことを証明しました。これを「チャイティンの不完全性定理」といいます。 これらについては、以前の僕のブログを参照ください。 　●「コルモゴロフの複雑性」 　　　 htt

以前、次のように書きました。 「複雑なものを理解するのには、長い時間と膨大な知識の集積が必要である」と。 それは、人間の認識の歴史について語ったものでしたが、具体的な計算の複雑さの尺度にも、この「長い時間と膨大な知識の集積」に対応する量があります。 それは、「その計算にどれぐらいの時間が必要か？」という時間の尺度と、「その計算にどのくらいのメモリー空間が必要か？」という空間の尺度です。前者を「時間計算量」、後者を「空間計算量」と言います。 チューリングマシンで言えば、「時間計算量」はある計算に必要なチューリングマシンの命令の「ステップ数」に、「空間計算量」はある計算に必要なチューリングマシンの「テープの長さ」に対応します。 決定性チューリングマシンで、\(O(f(x))\)で表される時間計算量の複雑性クラスを\({\bf DTIME}(f(x))\)で表し、同じく空間計算量の複雑性クラスを\({\bf DSPACE}(f(x))\)で表します。 \({\bf DTIME}(f(x)),  {\bf DSPACE}(f(x))\)のままでもいいのですが、代表的な複雑性クラスについては、次のような別名を付けます。ここで\(p(n)\)は、入力の大きさnについての多項式です。 時間複雑性については、 　　\({\bf P} = {\bf DTIME}(p(n))\) ; 「多項式時間」です。 　　\({\bf EXP} = {\bf DTIME}(2^{p(n)})\) ; 「指数関数的時間」です。 　　\({\bf 2-EXP} = {\bf DTIME}(2^{2^{p(n)}})\) ; 「二重指数関数的時間」です。 空間複雑性については、 　　\({\bf PSPACE} = {\bf DSPACE}(p(n))\) ; 「多項式空間」です。 　　\({\bf EXPSPACE} = {\bf DSPACE}(2^{p(n)})\) ; 「指数関数的空間」です。 　　\({\bf 2-EXPSPACE} = {\bf DSPACE}(2^{2^{p(n)}})\) ; 「二重指数関数的空間」です。 この時、 時間計算量では、\({\bf P} \subset {\bf EXP}\) という関係が成り立ちます。空間計算量では、\({\bf PSPACE} \sub