過去・現在・未来

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」と呼ぶことがあります。彼は、全知全能で、どんな問題も瞬時に答えを返す能力をもっています。ただし、ここが重要なのですが、彼は誠実ではなく、時々、人を欺く嘘をつきます。 一方の「普通の

コロナの年、何をしてきたかまとめてみました。 毎月一回のペースでセミナーを開催しました。 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

先に、「\(n^2\) あるいは\(n \log(n)\)に対応した計算複雑性を考えることは、もちろんできます。\(n^2\)は、多項式時間のPに属しますが、\(n\log(n)\)は、nの多項式ではありません。Pとは別の、\(n\log(n)\)という計算複雑性を考えることは可能です。」と書きました。 ここでは、ある関数f(n)が、nが増えるにつれてどのように増大するかを具体的に見ておきましょう。次の図を見てください。 ここでは、次の8つの関数が表示されています。\(n!,  2^n,  n^2, n\log{n}, n, \sqrt {n}, \log {n}, 1 \) \(n!,  2^n,  n^2, n\log{n} \)が nと比べて急速に大きくなることがわかります。それでも、\(n! > 2^n >  n^2 > n\log{n} \)ですね。nが大きくなるにつれて、その差はもっと大きなものになります。例えば、n=10の時、\(2^n\)は1024ですが、\(n^2\)は100、\(n\log{n}\)は、10の自然対数は、2.302... ですので、約23になります。 二つの関数 f(x)とg(x)があって、xがある値以上の時、ある正の定数cが存在して、常に f(x)よりcg(x)が大きい時、\(f(x) \in O(g(x))\)と表します。これをBig O記法と言います。イメージとしては、関数の値の増大に一番寄与している項を上限として取り出したものです（他の項は捨てます）。関数の定数倍の定数cも捨てます。 例えば、\(f(x)=4x^3-2x^2+5 \)という関数のBig O 表記を考えましょう。xが大きくなるにつれてf(x)の値の増大に一番寄与するのは、\(4x^3\)の項です。\(f(x)=O(4x^3)\)ですが、この定数の部分も省略して、\(f(x)=O(x^3)\)と表すことができます。 この表記で、多項式中のnの最大次数をkとして、多項式 poly(n)は、\(O(n^k)\)と表すことができます。

 複雑性理論で、もっとも基本的なクラスは、「多項式時間で計算可能なクラス P」です。このクラスは、人間にとってコンピュータで実際に計算できる計算と、ほぼ同じものです。 「人間にとって」というのが、奇妙におもわれるかもしれませんが、これはこれで大事なことです。見かけは単純に見える問題でも、アルゴリズムによっては、その計算には信じられないほど長い時間がかかる計算があります。人間は、多分、計算終了まで待つことができません。 だいぶ前になりますが、一部では話題になった動画があります。「『フカシギの数え方』 おねえさんといっしょ！ みんなで数えてみよう！」 https://www.youtube.com/watch?v=Q4gTV4r0zRs 是非、ご覧になってください。 こうした問題を「数え上げ問題」というのですが、複雑性理論で個数の数え上げが、重要な意味を持つことを初めて示したのは、日本のコンピュータ・サイエンティスト 戸田誠之助 氏です。彼は、日本人で唯一人のゲーデル賞の受賞者(19998年)です。

ここでは複雑性理論での「多項式時間」について話してみようと思います。 \(xもx^2もx^3もx\)の多項式です。もっと一般に、\(a_0+a_1x+a_2x^2+a_3x^3+...+a_nx^n \)の形の式を「xの多項式関数」と呼びます。それぞれの項が、\(x^n\)に係数\(a_n\)が掛かった形をしていて、それらの和で表される関数です。xの多項式関数を\(poly(x)\)で表します。 ただ、\(2^xや3^x\)は、xの多項式とは呼びません。\(a^x\)は、aについてみればaの多項式ですがxについてみればxの多項式ではありません。変数xが「x乗」の形である項の肩に現れる関数を「xの指数関数」と言います。 複雑性の理論では、多項式時間で計算される問題のクラスを Pで表します。 ただ、いくつか注意すべきことがあります。 第一に、何についての多項式かを決めておく必要があります。1+1よりは、1000+1000の方が計算には時間がかかります。一般に、入力に与えられるデータが単純なものより複雑なものに計算には時間がかかるはずです。入力の大きさをnで表した時、計算時間をnの関数\(f(n)\)で表します。「多項式時間で計算される」というのは、入力の大きさをnとする時、その計算時間が、多項式\( poly(n)\)で表せるということです。 第二に、注意すべきことは、計算量を時間ではかるには、二つのやり方があるということです。一つは、実際に実行時間を実時間ではかるやり方です。もう一つは、たとえて言えば、コンピュータで何クロックその処理にかかるのかをはかるやり方です。 複雑性理論での時間計算量は、後者のアプローチをとります。計算を、基本的な要素に分解して、その基本操作の何ステップで処理が終わるかで、時間をはかります。正確な定義は後で述べますが、直感的にいうとチューリングマシンの一命令の実行を時間の単位にします。 そうすると面白いことが起きます。 ある問題が多項式時間で計算される複雑性のクラスPに属するとします。ムーアの法則で、コンピュータの処理速度が指数関数的に増大したとしても、基本動作が早くなるだけで、処理に必要なステップが短くなる訳ではありません。ですので、実際の実行時間がいくら速くなっても、その問題が多項式時間のクラスPに属することに変わりはありません。 もっと面

私たちの認識は単純なものから複雑なものに進みます。世界は複雑なものであふれているので、我々の認識もどんどん複雑になっていきます。ただ、こうした私たちの認識の前進がいつまでも続くとは限りません。私たちの認識は、しばしば、複雑さの前に立ちすくみます。複雑なものを理解するのには、長い時間と膨大な知識の集積が必要であることは、科学の歴史を見れば分かります。 僕は、対象の複雑さと認識の複雑さは同じものだと考えています。そうした認識は「複雑さ」そのものを対象とした認識が可能だということを意味します。現代の計算科学のもっとも活発な研究分野はの一つは「複雑性理論」なのですが、そうした理論が登場したことの意味は、そう考えれば、よく理解できると思います。 今回のセミナーでは、様々なチューリングマシンの拡大と複雑性のクラスの対応を紹介したいと思います。次のようなチューリングマシンを取りあげます。 https://turing-complex.peatix.com/view 　● 決定性チューリングマシン 　● 非決定性チューリングマシン 　● 確率性チューリングマシン 　● 量子チューリングマシン 先に、「複雑なものを理解するのには、長い時間と膨大な知識の集積が必要である」と書きましたが、このチューリングマシンによる複雑さのモデルでは、複雑なものを理解するのに必要な「長い時間」がチューリングマシンの「計算時間」に、「膨大な知識の集積」がチューリングマシンの「テープの長さ」に対応すると思って構いません。 「そんな単純化で大丈夫か？」 確かに。 もちろん、科学の歴史をチューリングマシンに喩えようと思っているわけではありません。ただ、こうした単純化（「抽象化」は、単純化に他なりません）された切り口が、「認識の有限性と対象の無限性」「古典論と量子論」「決定論と確率論」といった認識の大きな問題にアプローチする一つの有効な手段を提供するという話ができればと思っています。

有限と無限は対の概念です。英語でも、"finite"と "infinite" と対になっていますね。ただ、有限と無限の対比の仕方は、日本語と英語とでは、少し違います。日本語では、有限は「限界があるもの」で、無限は「限界がないもの」ですが、英語では、「無限」は「有限でないもの」です。日本語の方が、定義が踏み込んでいます。 ここでは、「限界がある」という有限の定義で、有限には、どんな限界があるのかを考えてみましょう。 有限の身近なモデルとして、自然数を考えましょう。ある具体的な自然数nを考えて、nは有限であると考えることは自然なことのように思われます。具体的な自然数を有限のモデルだとして、今度は、有限の「限界」を、どんな自然数nに対しても、n < N なるNが存在することだと考えましょう。有限な自然数には、大きさで超えられない壁があって、それが有限の「限界」だと考えるということです。 ただ、この有限の「限界」の特徴づけは、いくつか奇妙なところがあります。 限界Nが存在して、それが自然数だとします。その時、N+1も自然数で、N < N+1 ですので、限界はNではなく、N+1になります。これは矛盾です。ですから限界Nが、自然数だと考えることはできません。これは、素直に考えれば、最大の自然数は存在しないということです。また、それは、具体的に与えられた自然数nより大きい自然数は「無限」に存在することを意味します。 先に、ユークリッドが素数が無限に存在することの証明を、無限という言葉を使わずに行ったと書きましたが、彼が行ったのは、次のような証明です。基本的には、上と同じ論理です。 最大の素数pが存在するとする。p以下の全ての素数の積に1を加えた数をPとする。Pは、全ての素数で割っても、1が余って割り切れない。よってPは素数で、p < P で、pは最大の素数ではない。これは矛盾。よって、最大の素数は存在しない。 色々奇妙なところもあるのですが、「具体的に与えられた自然数＝有限」というモデルを維持することにこだわりましょう。このモデルは、自然なものにおもえますので。 それでは、この有限のモデルで、その「限界」は、どう考えればいいのでしょう？ 次のようなωを考えます（先に見たように、ωは自然数ではありません）。 　 　「全ての自

無限は、古来から、多くの哲学的・数学的な関心を引き付けてきました。 時間や空間が連続的で無限であると仮定すると引き起こされる「ゼノンの逆理（アキレスはかめに追いつけない）」は有名ですね。 ユークリッドは、素数が無限にあることを証明したのですが、その証明では、慎重に、「無限」という言葉を使うことを避けました。アリストテレスは、もっと踏み込んで、無限について語っています。彼は、無限を「実無限」と「可能的無限」に分けました。 数学では、連続と無限の問題は、ニュートンやライブニッツが微積分法を始めた時にも、「無限大」「無限小」の概念を巡って大きな議論が巻き起こりました。現代の数学の出発点の一つであるカントールの集合論は、無限についての数学といってもいいのですが、ここでも多くの論争がありました。 20世紀になっても、超限解析(Non-Standard Analysis)の登場や、連続体仮説の独立性証明といったトピックでも、議論は尽きません。 物理学についても、現代の物理学の歴史を「連続的なものとの格闘」という視点から振り返った数理物理学者のJohn Baezは、次のように述べています。"Struggles with the Continuum"  https://johncarlosbaez.wordpress.com/2016/09/08/struggles-with-the-continuum-part-1/ 「すべての主要な物理学の理論は、時空が連続的なものであるという想定から生まれる数学的問題に対する挑戦であることを、この一連の投稿でみてきた。連続的なものは、無限によって、我々をおびやかす！　これらの無限は、これらの理論から予測を行う我々の能力を脅かすのだろうか？　あるいは、これらの無限は、こうした理論を正確な形で定式化する我々の能力さえも脅かしているのであろうか？」 こうした無限と連続をめぐる議論は、とても興味深いものです。昨年発見された、MIP*=RE定理も、こうした議論に一石を投じることになるのは確実です。ただ、今回は、そうした議論の紹介は、割愛します。 と言いますのは、今回フォーカスしたいのは、複雑性理論での無限と有限の捉え方だからです。誤解を恐れず単純化していうと、複雑性理論は無限を直接の対象とはしません。複雑性理論がまず関心を持つのは、

人工知能技術というのは、最終的には、人間の知能の機械による代替を目指す技術です。 ただ、人間の知能といってもいろいろあります。人間の知能自身が、生物学的な進化や文明史的な進歩の産物として、歴史的に形成された階層構造をもつのですから、それぞれの階層に対応する人工知能技術が存在します。 以下に、それぞれの知能の階層に対応する、現在の人口知能技術をあげてみました。 これらの技術は、知能のある能力の一面をカバーするのですが、一つの人工知能技術が、人間の知能を全てカバーすることはないと僕は考えている。 ただ、多分、問題はその先にもあります。こうした現在芽生え始めたばかりの人工知能技術が成熟すると、我々は「考える機械」「人間と同じ機械」を構成できるのだろうかという問題です。僕は、まだ、何かが欠けていると感じています。 感情、自由意志、創造性、芸術、.... こうした人間にとっては、ある意味もっとも人間らしい能力を、機械は獲得できるのか？　そのことは、人工知能の「研究者」じゃない多くの人が、自然に感じている疑問です。 そのあたりの問題を 「8/1 丸山x山賀対談「科学と虚構の未来を語る」」で話せればと思います。　もちろん、答えはありません。

この間、大規模システムでのディープラーニング技術の応用事例を調べていたのだが、こういう文章に出会う。 「ビッグ・ソフトウェアは、人間が一人で設計、展開、運用することができない（？）ような、非常に多くの動く部分で構成されたソフトウェアのクラスである。これらは、そもそもは単一のマシンに格納できないビッグデータを呼び起こすことを目的としていた。 」 まあいいだろう。現代は、ビッグ・ソフトウェアの時代なのは確かだ。確かに、大規模システムの管理は難しい。 「ここにこそ、AIが登場する。我々は、ディープラーニングが大規模システム管理の未来だと考えている。ニューラルネットは、大量のデータから、干し草の山から、針を見つけることができる。ニューラルネットは、従来のシステム管理者の能力を大幅に拡張し、その役割を変革するツールとなる。」 これも、まあいいだろう。大規模システムの管理に使えるツールがあるなら、なんでも使えばいい。ただ、次の未来像は怪しい。 「AIが学ぶにつれて、最後には、自己修復型データセンターが標準になる。 AIは、手元のリソースに適応したより優れたモデルを発見するので、最終的にはインフラストラクチャを改善および再構築するためにコードを修正することができる。」 ディープラーニングには、プログラムのロジックが理解できない。コードを読んでバグを見つけて、それを修正するなんて、ディープラーニングには、逆立ちしたってできないのだ。 多少、鼻が歪んでいても、目がつり上がっていても、ディープラーニングは、それを同じ人間だと同定できる。それはそれで素晴らしい。ただ、ソフトウェアの場合には、それがどんなに大きなソフトウェアでも、一箇所でもバグがあれば、それがシステム全体をダウンさせる可能性がある。 ビッグ・データとビッグ・ソフトウェアを、どちらも「ビッグ」だからと、同じ仲間だと考えるのは大きな間違いだ。 幸いなことに、このビッグ・ソフトウェアの分野では、ディープラーニングではない「Yet Another AI」技術が、花開こうとしている。 どういうムーブメント（ディープラーニングに対して、「ディープ・スペシフィケーション」 Deep Specification と言ったり、あるいは、数学基礎論にならって、「ソフトウェア基礎論」と言ったりする）かは