過去・現在・未来

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定理の概要の説明です。

認識の客体としての「エンタングルする自然」の理解の進行と、認識の主体としての人間の認識能力の深化は、お互いに絡み合っていますが、相対的には独立の過程です。4月のセミナー「エンタングルする認識」では、後者に焦点を当てようと思います。 【エンタングルメントの実在の認識 -- CHSHゲーム】 「それは馬鹿げた遠隔作用だ。」 アインシュタインは、エンタングルメントのことをそう呼びました。確かにそれは、二つの量子がどんなに離れていても、片方の量子の状態を観測すると他方の量子の状態が瞬時に分かる現象のように見えます。 それは、アインシュタインが特殊相対論で確立した、ある事象の影響は光のスピードを上限としてしか他の事象に影響を及ぼさないという「事象の局所性」に反しているように見えます。物理的な「因果関係」は、局所的な性質を持ちます。 物理的な「実験」では、単純化していうと、実験の対象と観測機器と観測者の知覚が、すべて物理的な因果関係のチェーンで結ばれたされたシステムを構成しています。 それでは、そうした局所的な因果関係を破るエンタングルメントのような現象の実在は、どのような「実験的」手段で確かめることができるのでしょうか？　それは、物理的な因果関係に従わない「テレパシー」の存在を、物理的な因果関係に従う実験で証明しようというのに似ていないでしょうか？  ちなみに、こうした理論化は、1960年代になされたものですが、21世紀に入って、Interactive Proofの流れの中で再評価が行われ、次の認識の飛躍 MIP*=RE を準備することになりました。 詳しくは、セミナーで。 --------------------------------------------- 0または1を入力X,Yとして受け取り、0または1を出力A,Bとして吐き出す箱があるとしましょう。内部の仕掛けはわからないブラックボックスです。 ブラックボックスだとしても、入力と出力を観察すれば、両者の「相関 C」は知ることができます。入力と出力の「相関 C」は、入力X, Yが与えられた時の出力A, Bの条件付き確率で与えられます。C = P(A, B | X, Y) です。 今、ブラックボックスの入力 X, Yと出力 A, B が、ある関係 D(X,Y,A,B)=1を満たす時、青いランプがついて、そうでない時は赤

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

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

コロナの年、何をしてきたかまとめてみました。 毎月一回のペースでセミナーを開催しました。 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定理も、こうした議論に一石を投じることになるのは確実です。ただ、今回は、そうした議論の紹介は、割愛します。 と言いますのは、今回フォーカスしたいのは、複雑性理論での無限と有限の捉え方だからです。誤解を恐れず単純化していうと、複雑性理論は無限を直接の対象とはしません。複雑性理論がまず関心を持つのは、

「型の理論」入門 型のないラムダ計算１ https://youtu.be/WEbDbLwEog8 http://bit.ly/2MOQMr5 型のないラムダ計算２ https://youtu.be/sGhiSSNnv0Y http://bit.ly/34dma8l 型付きラムダ計算 https://youtu.be/p9dv0RH4s60 http://bit.ly/32q7GQX 論理的推論１ -- 判断と論理式 https://youtu.be/Nrv5UVeoL4o http://bit.ly/30XTf5W 論理的推論２ -- Natural Deduction https://youtu.be/J-2F2slEqu4 http://bit.ly/2NE0iNo Curry-Howard対応１ https://youtu.be/_QDaoBabMU8 http://bit.ly/2MMVJRv Curry-Howard対応２ --「型の理論」と「証明の理論」 https://youtu.be/47YanruvaLE http://bit.ly/2Uit4oe Dependent Type Theory https://youtu.be/4cH3zWEQ5ko http://bit.ly/2ZpttLu Homotopy Type Theory https://youtu.be/N92Rx4USQPY http://bit.ly/2L96rzw

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