ハッカーの遺言状──竹内郁雄の徒然苔
第43回：「複雑」って何？

「人生は複雑だ」、「彼女はなんとも複雑な表情を見せた」、「いやぁ、これはすごく複雑な模様だね」、「君の話は複雑で、さっぱり分からん」、「複雑なプログラムを書いてはいけない」などなど、「複雑」という言葉はよく使われる。しかし、「複雑」とは何かをきちんと定義してよと言われたら、皆さん、きっと困るに違いない。

広辞苑をひくと、「複雑」という言葉の意味として「物事の事情や関係、または心理などがこみいっていること、いりくんでいること」とある。（語義説明が簡潔明瞭と私が思っている）新明解によると「すぐには解決（理解）できない事情（関係）がいろいろからみあっている様子」である。これで分かった気になればそれでおしまいだが、「複雑とは入り組んでいることである」と言われても、「楽しいとは愉快なこと」と言いくるめられたような気分だ。

1990年ごろだっただろうか、「複雑系」という言葉が流行し、それを含んだタイトルの本がたくさん出版された。社会学、経済学といった、もともと研究対象が複雑な学問に加え、コンピュータ、通信ネットワークなどといった工学の分野も巻き込んだ学際的な関心を呼び集めた。私も付和雷同した。

コンピュータや通信ネットワークは、システムを要素に分解すれば理解可能という還元的手法をドグマとするエンジニアの生み出したものであるにもかかわらず、これらを「複雑系」として研究対象にすることは矛盾をはらんでいるように見える。自分で作ったものが複雑なので分からない、うまく制御できない、と言っているようなものだからだ。しかし、私はこれが「工学のパラダイムシフト」を示唆する重要な徴候と考えた。

それはともかく、普通に言ってプログラミングが複雑だということは間違いない。それを打破するために先人は苦労を重ねてきた。第35回の遺言状「プログラミング画法」で、ダイクストラの構造化プログラミングや、そのあとのオブジェクト指向について軽く言及した。

さて、最初の問題に戻ろう。複雑さとは何なのだろう？　複雑さは数値で表現できないのだろうか？　面白さや、悲しさが客観的に数値化しにくいのと同様、複雑さも数値化は無理なのだろうか？　定量化できないものは、科学の対象になりにくい。調べると、複雑系の学問は実に多様で、そのこと自体が複雑な様相を見せている。

1995年ごろ、私が昔取ったかもしれない杵柄を頼りに文献を調べてみたところ、ベネットの「論理深度」という概念に遭遇することができた。複雑さの定義はほかにもいろいろあるようだが、どうも、これが私の思い描いていた複雑さの定義に近い。実際は面倒くさい数式が出てくる議論なのだが、ここでは数式をほとんど使わない紹介を試みよう。

情報科学の中で、複雑さ（complexity）という言葉を使った概念としてよく知られているのは、アルゴリズムの実行の手間を測るための計算複雑性（computational complexity）だ。例えば、よく知られているのが（えっ、知られていない？）二分探索で目的のデータを見つけるまでの比較回数は n 個のデータが大小順とか辞書順とかできちんと並べられている場合、2を底とする対数 log を使ってほぼ log n ということが分かっている。つまり、n = 1000 だったら平均で約10回ということだ。情報科学を勉強した人なら、ああ、あれかという奴だ。

これは計算に必要な時間の見積りなので、時間複雑性という。アルゴリズムが使うメモリ量を測るのは空間複雑性だ。プログラムを書いたことのある人は直観的に分かると思うが、計算時間を短くしようとしたら、メモリをたくさん使い、逆にメモリを節約しようとしたら、計算時間がかかる。要するに、こちらを立てればあちらが立たず、が成り立つ。

アルゴリズム論と直接の関係はないが、シャノンによって作られた情報理論には「情報量」という概念が出てくる。情報を例えば2進数で表現して伝えるときに、短い2進数になるように符号化できれば、同じ時間で通信回線に、より多くの情報が流せる。

英語の文章を送りたいとき、いわゆるASCII符号で送れば1文字あたり8ビット（8桁の2進数、実際には7ビットしか要らないが1バイト単位）で情報を送ることになるが、ご存知のように英語では、空白、e、tの出現頻度が高く、xやzはかなり出現頻度が低い。それならば出現頻度の高い文字は短い2進符号にして、出現頻度の低い文字は長い2進符号にすると、通常の英語の文章の場合は、符号ビット数が全体として減りそうだ。実際、ハフマン符号という符号化方式を使うと、英語の文章だと40％以上ビット数が減る。この減ったほうの文章、つまり冗長性を削ったほうの符号を「本質的な情報量」と呼ぶことができよう。

「君の報告は情報量が少ないねぇ」というのは、長々と報告しても、大部分がすでに知っていることだったり、そこから簡単に推測できることだったりして、新しく得られる情報が少ないということを意味している。これは情報理論の「相互情報量」という概念を使って説明できる。

この情報理論に触発されて考案されたのが、「コルモゴロフの複雑さ」（Kolmogorov complexity）である。コルモゴロフはロシア（旧ソ連）の偉大な数学者で、特に確率論では偉大な足跡を残した。

コルモゴロフの複雑さは、直観的な言い方をすると、対象としているものが、どれくらい短く記述できるかを表わす量である。短く記述できれば「単純」で、どうやっても長い記述になるものは「複雑」というわけである。

「えっ、上の符号化とどう違うの？」と思われたに違いない。符号化は対象となる文字列を別の種類の文字列（例えば、0、1からなる2進数、すなわち、2進数列）に直接変換することである。しかし、コルモゴロフの複雑さでいう「記述」とは対象となる文字列を生み出すプログラムのことである。例えば、0と1を交互に繰り返すような長い2進数列を記述するには、0と1を交互に出力する繰り返しのプログラムを書けばよい。列の長さが10でも10,000でも1,000,000,000でも、繰り返しの回数の記述の部分を除けば、同じ形である。要するに単純な繰り返しパターンなので、記述されたプログラムは十分に短くなる。

コルモゴロフの複雑さは、計算複雑性に対比して、記述複雑性と呼ぶことができる。上の例でも分かるように、規則性の高い数字列は短い記述ができるので、コルモゴロフの複雑さは低くなる。

では、円周率πはどうだろう？　ご存知のように無理数であるπの小数点以下には繰り返しがない。コルモゴロフの意味でπを記述するということは、πを計算するプログラムを書くことである。Wikipediaによれば、2016年には小数点以下22兆桁以上がすでに求まっているそうだ。これを計算するプログラムは簡単なプログラムではないだろうが、公開されている高速なCプログラムでも1,000行に満たない。つまり、22兆に対して10桁も少ない行数できていることになる（※1）。

では、でたらめな数、つまり乱数はどうだろう？　プログラムで計算できる乱数は「疑似乱数」と呼ばれ、本物の乱数ではない。プログラムで書けたら、カジノでは使えない。本物の乱数は短いプログラムでは書けないのだ。結局、10,000桁の（2進数列で表現された）乱数は、その乱数をプログラムの中にデータとして埋め込んで、それを順番に出力するしかない。結局、「記述」しようにも、元の2進数列よりも短く記述することは難しい。

ということは、コルモゴロフの複雑さでは、乱数が一番「複雑」ということになってしまう。つまり、πのようにコンピュータに猛烈な計算をさせないといけない数列より、サイコロを振って出てきた数の並びのほうが複雑というわけだ。

1994年秋に京大基礎物理研で行なわれた第3回複雑系研究会で、東工大の小林孝次郎先生がコルモゴロフの複雑さの紹介を行なったのだが、そのあとの雑談で、東大の金子邦彦先生が「乱数を一番複雑だと言われてもねえ」と、素朴な疑問を投げかけた。私もそれに同感だった。

もっとも、コルモゴロフの複雑さは「『複雑』とは何か？」という疑問に答えるためのものというより、「乱数とは何か？」の疑問に答えるために考案されたものといったほうが正しい。

実際、大きな n 、例えば1億桁の2進数を記述するプログラムを考えよう。簡単のためプログラムも2進数で表現されているとする（実際、コンピュータの中ではそうなっている）。すると1億桁引く10桁（つまり、99,999,990桁）の2進数プログラムの種類は、1億桁のすべての2進数に比べて（すべての2進数が動くプログラムになっているとは限らないので）高々2の10乗分の1、つまり1,024分の1しかない。つまり、残りの1,024分の1,023の1億桁の2進数列はほぼ1億ビット以上のプログラムでしか記述できないことになる。大半はデータをそのまま埋め込んだプログラムに相当する長さのプログラムということだ。

こういう論法から、コルモゴロフは長い2進数列の大半は「乱数」だと主張した。なんだか変な定義だと思われるかもしれないが、これはその後、統計学者流の、どんな検定をしても規則性を見出せないのが乱数であるという定義と合致することが証明された。

コルモゴロフの複雑さは、その後、チェイティンによって別の「応用」が見出された。その結果を彼自身の例え話で説明すると「10ポンドの公理系では、12ポンドの定理は証明できない」、もっと言えば、世界を単純な原理で記述し尽くせるという、理論物理学者の試みに対して、そうではない、我々の限界を超えたような記述しかあり得ないのだと反論し、それを証明しようとしても、それは最初から無謀な企てということを意味している。だからといって統一理論派を後押ししているわけでもないのだが……。

記述が短くならないものを複雑と呼ぶのは、直観的にはうなずける定義である。しかし、「乱数が一番複雑と言われてもねえ」という疑問が残る。例えば、カオスは複雑な振る舞いをすると言われているが、その基礎方程式、つまりカオスの記述自身は驚くほど単純である。むしろ、人々は「こんなに簡単に記述できるものが、どうしてこんな複雑な挙動を示すのだ？」という驚きによって、複雑さというか複雑系を捉えているように思われる。コルモゴロフの複雑さは、このような直観を裏づけてくれないのだろうか？

しかし、多くの研究者を引きつけたコルモゴロフの複雑さはそんなに底の浅いものではなかった。記述の量と、その記述に基づく実際の計算の量の関係に注目するような拡張が数多く行なわれた。

ソロモノフ・レビンの測度、あるいはアルゴリズム確率と呼ばれているものがその典型である。厳密で面倒な定義は飛ばして比喩的に説明すると、アルゴリズム確率は、養鶏場のニワトリにキーボードをつつかせて所望のプログラムが偶然打ち込まれるという確率に相当する（※2）。同じ結果を出すプログラムは何通りかあるかもしれないが、最も短いプログラムが確率に最も寄与する。長くなればそんな長いプログラムをニワトリがラッキーに打ち込める確率がぐんと減るからだ。この最も短いプログラムというところに、コルモゴロフの複雑さが登場する。幸運にもニワトリが打ち込んだ、所望の結果を出力するプログラムのことをチキンプログラムと呼ぼう。

IBM研究所の物理化学者であったベネットは、チキンプログラムに実行時間の制約を加えることを考えた。アルゴリズム確率をベースにして定義された「論理深度」の意味はとても掴みにくいので、これも厳密さを無視して比喩的に説明しよう。

大雑把に言うと、ベネットの「論理深度 d 」は、成功する中で確率の高いチキンプログラムが所望の結果を出力するのにかかる時間である。つまり、中には運良くそれより短い時間で所望の結果を出すチキンプログラムもあるかもしれないが、その確率は時間短縮の度合が高くとなると指数的に低くなってしまう。だから、d が大体必要な時間というわけだ。

上で、アルゴリズム確率には最も短いプログラムが確率に最も寄与すると書いたが、これは短く書かれたプログラムだと、ベネットの論理深度 d だけの時間がかかるということを意味する。このようにベネットの論理深度は、直観的には、コンパクトにした記述（プログラム）が所望の結果を出力するまでにどれくらい時間がかかるかを表している。これが大きい（深い）と、記述をコンパクトにできた代償を計算時間で払っていることになるのだ。実際、私たちが通常使っているプログラミング言語でも、同じアルゴリズムに基づいて書いたプログラムを短くすると、一般に計算時間は少し長くなる（※3）。

2進数列の桁数に比例した程度の論理深度しかもたないものを「浅い」と呼ぼう。規則正しい2進数列、例えば101を繰り返す2進数列は、桁数を与えると非常に短いループプログラムによって桁数に比例した時間で打ち出せるので、桁数に対して「相対的に」浅い（※4）。また、乱数は、もともとコピープログラムより短いものがなく、内部データ文に入れたその乱数を打ち出すのに乱数の桁数に比例した時間しかかからない。つまり十分に浅い。

しかし、πの計算は短いプログラムで書けても、時間はタップリかかるので浅くはない。なお、ついでだが、我々に思いつくようないくらでも大きい深さをもつ2進数列が存在することが証明されている（証明は10行程度）。つまり、それほど長くないのに、結果を出すのにものすごく時間のかかる2進数列が存在するのだ。

規則正しい数列や、乱数が浅く、その「中間」に深いものがあるという結果は、複雑系を複雑だと思う我々の直観を裏づけているように思われる。ベネットは次のように書いている。「一見ランダムに見えるが、微妙に冗長な構造が深い。つまりアルゴリズム確率が時間のかかるプログラムばかりの確率の和になっている場合が深い。……自然界に発生したDNAのような組織的情報は、単純な原理に基づいているけれども、とてつもなく長い生物学的プロセス（計算）の所産である」。

ベネットの論理深度の意味するところを敷衍すると、我々の世界が単純な原理で記述されていたとしても、それに基づいて実際的な予測を行なうことは計算量的に不可能だということだろう。もちろん世界が「深い」としての話だが……。

ちなみに、ベネットの論理深度を検索してみると、マーケッティングにおける情報の価値について言及したベネットのフレーズが引用されたものがトップに出てくる。例えば、

「情報」とは　⑤
http://yhpower.blog.fc2.com/blog-date-201203-3.html

要するに情報を生み出すのに本質的に要した時間が情報の価値というわけだ。

さて、これらの直観的な説明はますますカオスのもつ複雑性をうまく言い表わしているように思われる。実際、カオスにおける、見かけのランダム性に埋め込まれた冗長性、カオスの基礎方程式、すなわち記述の驚くべき簡潔性、初期値過敏性などによる予測不能性などと見事な符合がある。ただし，離散数学と連続数学の間のギャップがあるので、厳密な意味で両者の間に関連をつけるのは自明ではない。ベネットが引用していた、ウォルフラムが一次元セルオートマトンの研究で見出した「計算非可約性」、すなわち実際に計算してみるほかに有効な予測手段がないという概念との関連も興味深い。

ベネットが論理深度という概念を定義しようとした動機は、生物のような、世の中の複雑な組織は一朝一夕にできたものではなく、長い長いプロセスを必要としたという彼の信念であった。彼はそれを「ゆっくりとした成長の原理」と呼んだ。この原理を裏返すと、ゆっくりと成長してきた複雑系は安定であるといえるだろう。

コルモゴロフの複雑さにしろ、ベネットの論理深度にしろ、限りなく大きい有限の世界での理論だから、我々が日常的に扱っているものの複雑さに具体的な指針を与えてくれるわけではない。しかし、このような枠組みの存在自身が我々に安心感を与えてくれる。なお、論理深度を具体的に計算することは、計算可能性の理論によって、不可能であることが分かっている。ああ、さもありなん。

このあたりは、第5回の遺言状「つぶ餡と漉し餡」の最後のほうにも簡潔にまとめてあったので、ああ、あのことかと思われた方がいらっしゃると思う。小豆（単純で規則正しい）とコシ餡（ほとんどランダム）の中間領域にあるツブ餡（ランダムさに埋め込まれた微妙な冗長性）こそ味わい深いというのが、そのときの結論だった。

やや無理矢理だが、ベネットの論理深度は両極端の「中間」に複雑さがあると喝破している。中間が複雑という例は枚挙にいとまがない。数式処理のプログラムでは、数式を変形して、別の数式にするのが主な仕事だが、途中で出てくる式の大きさが半端ではない。よくぞ、これで最後の簡単な式が出てくるものだと思う。コンパイラの処理でも、ソースプログラムとコンパイル結果に比べて、コンパイル途中のデータのほうがだいぶ大きい。

中間管理職の悲哀も、この中間の複雑さに起因していると言えないことはない。囲碁でも将棋でも中盤が一番難しい。

話を元に戻そう。最初のほうで述べた「工学のパラダイムシフト」とは何か？　還元論に対する概念が「全体論」だが、これを「構成的全体論」にできないかというのが、1990年ごろ、付和雷同の私が考えたことだった。でも、構成的全体論とはそれ自身が矛盾した言葉である。本当にそんなことできるの？　これについては機会を改めよう。（つづく）

※1：πもプログラムもすべて2進数で表現して比較しても大して結果は違わない。
※2：かなり無茶な比喩であることはご容赦していただきたい。
※3：例えば、プログラムの似た部分を共有するために、いろいろフラグを入れ、フラグチェックを入れたりするとプログラムは短くなるかもしれないが、その分時間がかかるし、ループを展開してしまうとプログラムは長くなるが、プログラムは少し速くなる。
※4：泥縄的な補足になるが、桁数 n に対して相対的にしないと、n 自身が「深い」ことがあり得るので本当はもっと厳密に議論しないといけない。

竹内先生への質問や相談を広く受け付けますので、編集部、または担当編集の風穴まで、お気軽にお寄せください。（編集部）

この記事を、以下のライセンスで提供します：CC BY-SA
これ以外のライセンスをご希望の場合は、お問い合わせください。