2.3 計算を見極める研究

ここまで情報を扱う科学技術の二つの重要な基本原理―デジタル化と計算化―について述べてきた。

この基本原理の創出には「計算」を見つめる研究が重要であった。一方、コンピュータが登場してからは、アルゴリズムの設計やプログラミング技術の開発、さらにはスーパーコンピュータの実践的活用まで、幅広く深い研究が「計算とは何か」を明らかにしてきた。本節では、そうした研究の一端を紹介していく。

 

2.3.1 計算可能性の研究:「計算」という概念の明確化

デジタル化と計算化の基本原理のうち、とくに計算化の確立に必要な重要な概念の数々は、20世紀の初頭から始まった「計算とは何か」という問いに対する研究の中から生まれてきた。

「計算」を厳密に規定する研究は1930年代に現われ急速に深まった。この研究は、その30年前に出されたヒルベルトの第10問題(用語解説参照)の影響も少なくなかっただろう。ヒルベルトの言う「有限的な方法」が何かを規定しなければ、そのような方法がないという否定的な結果が導けないからである。

1933年~1936年にかけて「計算」に関する重要な三つの概念が相次いで示された。A. チャーチが発表したラムダ計算、それとは独立に、A. チューリングが提案したチューリング機械という計算モデル、そしてその直後に、K. ゲーデルとS. クリ―ニにより定式化された帰納的関数。

これら見た目のまったく違う概念が、すべて同じ「計算可能性」を定義していたのである。

こうした同値性の結果などから、「計算可能である」という概念を「チューリング機械で計算できる」と定義しよう、という提案がなされた。この提案は現在では、チャーチ-チューリングの提唱またはチャーチの提唱と呼ばれている。我々の計算化の原理も本質的にはこれと同等の考え方である。

この提唱はあくまで考え方であり、数学的に証明することはできない。しかし、現在までに原理的にこの提唱の範囲を超えた「計算」という概念は見つかっておらず、定義としてほぼ定着している。

この計算可能性の研究の最も重要な結果は、計算不可能な問題の発見である。正確に定義できる(ある意味で単純な)関数の中に、計算できないものがある、ということが証明されたのである。その証明のために、チューリングは万能チューリング機械という概念を用いた。これは現代でいうインタプリタである。インタプリタという強力な道具が使えることが、実は計算不可能な問題がある、という計算の限界にもつながっていたのである。

このインタプリタの発見に代表されるように、これまでに紹介した情報科学技術の基本的な考え方の元が、この初期の「計算を定義しよう」という研究の中から生み出されてきたのである。

用語解説4:ヒルベルトの第10問題

D. ヒルベルト(1862~1943)は、1900の国際数学者会議において20世紀の数学において重要となる問題として23題の問題を指示した。そのうちの10番目の問題「ディオファントス方程式の可解性の決定問題」がヒルベルトの第10問題である。

これは簡単にいえば、不定方程式が整数解を持つか否かを判定する一般的で「有限的な方法」を示せ、という課題である。ただし、この時点では「有限的な方法」とは何かは明確にされていなかった。これは「計算」とは何かを追求するその後の一連の研究で明確になってきたのである。

なお、この第10問題は、1970年にロシアの数学者J.V. マチャーセビッチによって否定的に解決された。つまり、ヒルベルトが求めた方法は存在しないことが証明されたのである。

2.3.2 真の計算可能性の研究:アルゴリズムとプログラミング

計算とは何かという追求は、コンピュータが登場してから数学の研究から大きく踏み出し、本格的に、そして多様な広がりを持つようになっていった。その中でもとくに、計算の設計(アルゴリズム)と計算の表現(プログラミング)に関する研究に焦点をあててみよう。

情報を扱う科学技術の基本は、様々な仕事をコンピュータで行うこと、そのために仕事を、その対象も含め、コンピュータ上に載せること、つまりデジタル化と計算化である。そこには現実の(場合によっては未来の)コンピュータがあり、情報科学技術は、その上での実現をつねに意識したものになっている。

このように実現を意識したときに直面する最大の問題は「量と複雑さ」である。大げさかもしれないが、コンピュータが登場してはじめて「量と複雑さ」が人類にとって身近なものになったといってもよいだろう。情報を扱う科学技術の研究は、この「量と複雑さ」にいかに付き合っていくかの研究なのである。ここではそうして研究の中で「計算」にとくに関わりの深いアルゴリズムとプログラミングに関する研究の一端を紹介する。

アルゴリズム(algorithm)とは、計算を行う手順のことである。計算化の原理でも述べたように、あらゆる計算は単純な演算を組み合わせることで構成できる。構成要素が単純なだけに、その組み合わせ方は様々で、非常に自由度がある。同じ仕事を処理させるのでも、そのやり方は千差万別である。その「やり方」すなわち処理の手順がアルゴリズムである。

解説4:チューリング機械

A. チューリングが計算の抽象モデルとして提案した仮想機械。最も基本的なものは、右図のように、マス目に区切られた無限に長いテープの上を、テープヘッドが走査するもの。ヘッドが動き、ヘッドの位置するマス上の記号を読みとったり、マス上に記号を書き込んだりする。一回の動きで、この読み書きを行い、テープヘッド中の有限種類の状態も変化させる。これを有限状態が停止状態になるまで続ける。

計算と見る場合には、テープに最初に与えられた0、1の2進列が入力であり、それに対して停止状態時にテープ上に得られる2進列が計算結果の出力である。

チューリング機械は、我々が議論してきた計算の基本要素を単純化し抽象化したものになっている。計算の過程を表わす「状態」は、テープの内容、テープヘッドの位置、そしてテープヘッド内の状態であり、それらを変えることが「基本動作」である。その基本動作を停止状態になるまで「繰り返す」ことで計算を行なっているのである。この三要素から、我々の計算化の原理と同様、すべての計算はチューリング機械で実現できるのである。

このチューリング機械の提案とともに、チューリングが発見した重要な事実は、すべてのチューリング機械を模倣する汎用のチューリング機械(万能チューリング機械)が作れることであった。現代の言葉でいえばインタプリタの存在性を証明したのである。

 チューリング機械

計算の実現を意識したとき、まず重要になってくるのが「資源」である。どのくらいの計算時間が使えるのか、どのくらいのメモリ領域(記憶領域)が計算に使えるのか、といった点である。同じ仕事や計算をするのでも、アルゴリズムの良し悪しで、この資源の使われ方(コスト)に天と地の差が出てくる。適切なアルゴリズムを使っていれば数分ですむ仕事が、効率の悪いアルゴリズムを使ったために数日かかってしまう場合もある。あるいは、単純には数年かかるといわれた計算も、非常に巧妙なアルゴリズムが発見されたことで数時間ですむ場合もある。

アルゴリズムの効率の良し悪しを議論する場合、計算量(computational complexity)という尺度を用いることが多い。これは問題の規模の増加に対して、そのアルゴリズムの実行に必要な計算資源(たとえば計算時間)が、データ量nの増加に伴って、どのように増えるかを表わす関数である。

計算量を表わす場合には通常、「時間計算量がO(n²)のアルゴリズム」という言い方のように、比例定数の部分は省略した漸近的表現が用いられている。これは比例定数まで細かく評価するのが難しい、あるいは、そこまで細かい理論的な評価の必要性が低い、という理由からである。

用語解説5:漸近的表現、オーダー記法

関数の値の増減の速さの程度を大づかみに表現する方法。一つか二つのパラメータに対する変化を記述し、比例定数などは省略する方法である。一般的に用いられているのはO(n²) (nの2乗のオーダー)という言い方である。現在考えている関数がnの2乗に比例して増加する、という意味である。

もちろん、実用上は比例定数の部分も重要である。一般的には計算量が小さいアルゴリズムの方が効率的だが、実際のデータ量では必ずしもそうならない場合がある。たとえば時間計算量がO(n2)のアルゴリズムAと、O(n4)のBがあったとする。オーダーではBの方が速いが、実際にはAの方がはるかに早い場合もある。Aの方が単純で比例定数が小さく、実際の問題の規模ではBより速い場合などである。

6増加率の違いA:O(n2)B:O(n4)

このように定数係数については注意が必要だが、それでも漸近的計算量の低いアルゴリズムの方が有利であることが多い。実際の数値例で考えてみよう。

たとえば、アルゴリズムBの実際の計算時間が4n4秒だったのに対し、もう一方のアルゴリズムAが900n2秒かかったとしよう。このとき、もし問題のデータ量がn=10だったとすると、Aは90000秒(25時間)、Bは40000秒(11時間)である。しかし、データ量がn= 20になると、Aの方が圧倒的に有利である。

さらに、1時間で処理できるデータ量を比べてみる。Aでは900n2≦3600秒という式からn= 2以下となるが、Bでは4n4≦3600秒から、n= 5以下である。Bの方が少し大きなデータ量まで扱える。しかし、たとえばコンピュータの速度が1万倍になったら、どうだろう。Aは900n2÷10000 ≦3600秒から、n≦200となるが、一方、Bは4n4÷10000 ≦3600秒から、n≦55程度である。Aが100倍大きなデータを扱えるようになるのに対し、Bは10倍強である。

つまり、Bは、データ量が大きくなると早く手に負えなくなるだけでなく、コンピュータの性能向上の効果が小さくしか現れないのである。

一般に漸近的計算量の低いアルゴリズムは、コンピュータの速度の向上の恩恵を受けやすく、問題の規模の増加にも安定的である。「アルゴリズムの改良などより、コンピュータを速くした方が手っ取り早い」と豪語する人もいるが、実は、その逆で、コンピュータの性能が上がれば上がるほど、よいアルゴリズムが重要になってくるのである。

大ざっぱにいえば次のような考え方が重要だろう。

解説5:実際の計算の時間は?

実際の計算時間はコンピュータの性能によって大きくことなる。その性能の測り方は一通りではないが、たとえば、小数演算を1秒間に何回行なえるかを測るFLOPSという単位がある。たとえば、1ギガFLOPSは、1秒間に10億回の計算である。

下の表は、様々な計算装置の最適な環境の下でのFLOPS値の概算を示したものである。最近のゲーム器は、特に小数演算に特化して良い性能を出すように設計されているのでこの数値が高い。ただし、これはあくまで一つの指標にすぎず、この数値が高い=実際の計算性能がよい、とは限らない。

効率の良いアルゴリズム開発の研究は、いまやそれ自身が数理科学の重要な分野になるまでに発展した。しかし、残念ながら、どんな問題にも効率のよいアルゴリズムが作れるとは限らない。計算不可能な問題があるのと同様、たとえばO(n2)時間では絶対解けない問題、O(n10) 時間でも無理な問題等々が存在することが証明されている。

その一方で、効率よく解けるか否かがよくわかっていない問題も多い。その代表例がNP問題(正確にはNP完全問題)と呼ばれる一群の問題である。NP問題は、実に様々な分野で見つかっており、コンピュータの応用上重要な問題も多い。多くの研究者は「NP完全問題を一般的に効率よく解く方法はない」と信じている。これをP≠NP予想という。

NP完全問題を一般的に効率よく解く方法はない、と予想されているからといって手をこまねいているわけにはいかない。実際には解かなければならない問題も多い。一般的とまではいかなくても部分的に解けてもよいし、よい近似解が得られてもよい。あるいは、時間計算量が漸近的には大きくても、定数係数が非常に小さくて、ある程度の規模の問題までならば実用に耐えうるアルゴリズムでもよいかもしれない。様々なアルゴリズム的な試みがなされているのである。

解説6:NP 問題とNP 完全問題

世の中には、答えを言われれば「なるほど」とすぐ納得できる問題が少なくない。大ざっぱにいえば、NP問題は、そうした性質を持つ計算の問題の総称である。

例をあげよう。「この数を同じ桁数の積で表わせ」という問題がその一例である。たとえば221が問題例で、その解は13 ×17である。この答えが正しいかを確かめるのは簡単だろう。実際に積が221になることを確かめればよい。

あるいは、与えられた100都市を、150日間で訪問して回るような旅程が組めるか?という問題もその一例である(これは巡回セールスマン問題と呼ばれている)。都市の巡り方を言われれば、それが目標の旅程であるかをチェックするのは難しくない。

パズルのような問題も多い。たとえば、三彩色問題である。これは、与えられたグラフに対し、その各頂点に色を塗りたい、ただし、辺で結ばれた頂点同士が同じ色にならないように、しかも三色で塗り分ける方法を求めよ。という問題である。これも答えを言われれば確かめるのは簡単である。

答えを言われれば簡単に確かめられるとしても、それを探すのは容易とは限らない。たとえば、6頂点のグラフを3色で塗り分ける方法を全部試してみると、36 = 729通りもある。もし頂点数が50になったら大変だ。

もちろん、うまく解を見つける方法があるかもしれない。けれどもNP問題の中には、うまく解を見つける効率のよい一般的な方法が見つかっていないものも沢山ある。その中でも最も難しいということが示されている問題群をNP完全問題という。実は、巡回セールスマン問題、三彩色問題はNP完全問題の一つである。

次に、まったく異なる「量と複雑さ」に対処する話に目を向けよう。アルゴリズムは計算の設計に関する話だったが、計算の表現に関わる話題である。

計算化の原理でも述べているように、すべての計算は単純な演算から組み立てられる。しかし、このように原理的に可能であってもその大きさ、複雑さは膨大なものになる。基本演算の機能を大幅に強化したとしても、現在の少々大きなシステムとなると、プログラムで数万行になることも少なくない。

このように大規模になってくると、「原理的には表わせる」と言っても意味がなく、実際にどのように計算を表わすか、という方法論が重要になってくる。その方法論の提案とその直接の影響・成果が、今日のプログラミング言語である。

コンピュータの出現直後から、より書きやすい、よりわかりやすい計算の表し方を目指して、様々なプログラミング言語が提案されてきた。そこには、サブルーチン、スタック、再帰、ポインタなど、計算をうまく表現するために重要な工夫が取り入れられていった。

ただし、これらの工夫だけでは、プログラムの急速な大規模化・複雑化に対処しきれない。新たな方法論が必要になってきたのである。人間が考えやすく、間違いをしにくく、また修正や改訂なども容易に行えるようなプログラミングの方法論として、関数型プログラミングやオブジェクト指向プログラミングという考え方が出てきた。とくにオブジェクト指向は、その考え方に沿ってプログラムを作成するためのプログラミング言語C++やJavaなどが提供され、今や大規模なプログラミングには欠かせない方法論になっている。

いくら方法論がよくても人間ができることには限りがある。そこで人間のプログラム作成を支援するための様々なプログラミングツール(プログラムを作成する道具としてのソフト)が開発されている。プログラムのタイプ入力を助けるために登場したエディタであったが、それが発展し、今やプログラミング方法論を取り入れ、それに自然に従ってプログラムを作成できるようなプログラム統合開発環境を提供しているシステムもある。それにともなって、最初からアルゴリズムを設計して作るのではなく、既存のプログラム部品を組み合わせてプログラムを作成する場合も多くなってきた。

一方、できあがったプログラムの正しさを保証する手法についても多くの研究がなされてきた。プログラムが所望の動作をしないというのは、単にプログラム作成上のミスだけでなく、そもそも設計段階で、システム作成を依頼した側と作り手との間に誤解がある場合も多い。このような齟齬が生じないためのプログラムやシステム設計手法、そしてシステム作成の各段階での動作検証手法などの研究が行われている。

さらにはテストによる検証だけでなく、システムが正しく動くことを検証(証明)したい、という場合もある。医療や交通、あるいは原発などの非常に重要なシステムや多数のパラメータが介在する複雑な情報セキュリティシステムなどでは、正しく動くことが「証明」できれば、より安心である。これまでは、計算量の問題などで、機械的な証明を実際に行うことは考えられていなかった。しかし、アルゴリズムの進歩、そして適用範囲の適切な選択により、一部の応用では証明も十分可能な段階になりつつある。

 

2.3.3 計算世界観:計算を中心とした新たな観点

コンピュータに載せるためのデジタル化・計算化の研究の進展により、情報を扱う様々な科学技術が発見され、また開発されてきたが、それらはコンピュータのためだけでなく、一般的な科学分析の手法として、他の分野での研究でも使われ、その分野の研究に影響を与えている場合もある。

コンピュータの道具としての影響は当然のことながら、コンピュータを利用して情報を扱うために研究されてきた科学技術自身が「科学の手法」として他分野へ影響するようになるにつれ、情報科学技術をコンピュータのためだけでなく、科学分析の手法として用いるという考え方も生まれてきている。単にコンピュータを道具として使うためのデジタル化・計算化だけでなく、様々な現象や事柄を「計算」を通してみよう、という新たな考え方の芽生えである。こうしたアプローチを計算世界観(computational view、computational thinking)と呼ぶことにしよう。

「すべては計算で表わせる」というのは偏った考え方だろう。危険ですらある。けれども、人類が記号や式、あるいは科学的な文で議論できる多くの事柄は、計算で表わせると考えてもよいだろう。そこで逆に、計算を通して物事を分析するのが計算世界観である。

計算を中心に見ることで、計算に適した判断ができる場合がある。様々な現象をモデル化する場合、通常は完璧なモデルを作ることは期待できない。何らかの妥協をしなければならないのである。計算を中心に見ることで、計算に有利な妥協点を見出せる可能性がある。新たな切り口を見出せるのである。

計算という見方で見ることで新しい発見が得られる場合も少なくない。たとえば、NP完全問題の一つである三彩色問題の高速解決法が見つかれば、素因数分解も高速にできる。ということが証明されている。一見して何の関連もない二つの問題が、計算を通して見ると密接に関係しているのである。これはかなり専門的な事例ではあるが、一般にも、計算という見方で新しい発想や概念を得られる場合があり、計算という切り口は、これからの科学のアプローチとして重要になってくるであろう。

例7:情報を扱う科学技術が他分野へも影響している例

プログラミング言語の解析手法の言語研究への影響

人が理解しやすいプログラミング言語が数々と開発されたが、そのようなプログラミング言語で書かれたプログラムを、機械にもわかる命令列に変換する(つまり翻訳する)必要がある。プログラムを正確かつ高速に(機械語に)翻訳するため、文(プログラム)の構文解析技術の研究が非常に進展した。

チョムスキーらは文法を数理科学的に議論する枠組みを提案した。そもそも言語学の体系化の試みのために提案されたものだが、それがプログラムの構文構造の体系化に適用され、チョムスキーの枠組みのもとで、構文解析技術が大きく進展した。

その応用として、今度は、我々が通常使う言語(これをプログラミング言語と対比させて自然言語という)の解析へも用いられるようになったのである。こうした研究の展開は自然言語処理という新たな分野を生み出した。その中では、たとえば日本語から英語への機械翻訳や、辞書の検索技術、そして、様々な検索を容易にする辞書の構成法などの研究が進んだ。

こうした研究の中で見出された様々な科学技術は、本来の言語理論にも大きな影響を与えるようになってきた。それらは単にコンピュータを利用するための技術にとどまらず、言葉の意味や用法について、新たな知見を得るための「科学の手法」として注目を集めるようになったのである。

例8:計算を通して見ることが新たな観点を導き出した例

ランダムの明確な定義

確率論の基礎に貢献したA.コルモゴロフは、ランダムという概念を明確に定義しようと試みた。その頃ちょうど明確になりつつある「計算」という概念を用いることを考えたのである。彼のこのアプローチは、コルモゴロフとその関係者により達成され、ランダムという概念は計算という見方のもとではじめて明確な定義を得たのである。

公開鍵暗号系

公開鍵暗号系は、通信理論で研究されてきた暗号の分野に、「計算」という見方を持ち込んだために生まれてきた。

暗号通信を盗聴する者も、結局は限られた計算資源の元に暗号解読しなければならない。逆に言えば、限られた計算資源の元では解読できない暗号を考えればよいのである。この考え方が公開鍵暗号を生み出したのである(公開鍵暗号についての説明は第3章参照)。

コラム No. 2

情報学リテラシーの学び方

私たちはユーザーとしての様々な体験から、専門家の知の体系とは異なる「便利さの体系」(ユーザーの視点から情報技術によって可能になったことを体系化したもの)を学んでいる。情報学リテラシーとして求められているのは、そのような便利さと情報学とのかかわりを知り、より豊かな生活を送ることができるようになることであろう。本部会では、情報学リテラシーを、原理、仕組み、意義、影響の四層で捉える観点で検討を進めてきた。情報学リテラシーの学び方をこの観点から見たとき、原理・仕組みと私たちの体験とをいかにつなげるか、という論点は重要である。

 何かを学ぶときに、題材が学習者にとって身近であることは、重要な条件の一つである。ところが、専門家が考える身近さと、学習者が考える身近さとは、往々にして一致していない場合が多い。以前、中学校の理科教師から、中学生が慣性の法則を実感できるのは、スペースシャトルや人工衛星の映像を見た時であり、目の前のだるま落としでは十分ではない、と指摘を受けたことがある。また、身近ではない題材で法則の学習を続けていると、生徒たちは、自分たちの身近な世界でその法則が成立しているという感覚を抱けずに、「知っているが信用しない」知識として理科学習用の引き出しに入れ、鍵をかけてしまうという。先に述べた「便利さの体系」は、私たちの生活に十分に身近であるが、それは、情報学の成果が応用され、実現された結果であって、情報学が追究してきた仕組みや原理とのギャップは大きい。便利さの体系と「つなげる」ことなく、原理・仕組みを学ぶのだとしたら、学習者は、それを情報学リテラシー用の引き出しに入れ、鍵をかけてしまうだろう。

 便利さの体系と原理・仕組みを「つなぐ」ものは、たとえば、次のようなものではないだろうか。

・情報学研究者の努力:研究者や技術者の実際の活動を知ることにより、便利さは人間の知恵と努力の成果であることがわかる。

・情報技術開発の基本的な方法であるプログラミングの存在:身近な情報技術の産物が、「作られた」ものであることがわかる。

 情報学は、単純な原理から様々な仕組みを実現、発展させてきたが、私たちの便利さを享受する体験は、その過程と切り離されている。そのため、情報学に携わる人々の智恵や努力、方法そのものが原理・仕組みと体験を「つなぎ」、信用できる情報学リテラシーを学ぶために必要と考えるのである。