本文へジャンプ

理論の授業とは?

「世界」をとらえる<モデル化の話>

今日は、情報科学科で学ぶ理論について、それから理論のおもしろさについて教えてください。
まず、情報科学のモデル化とはどういうことか、というあたりからどうでしょう。3年生は「情報論理」で論理学の基礎を学びますが、学部で論理学を勉強する例はあまりないですよね。

萩谷:僕が話すと固くなるなあ。僕自身は論理学がバックグラウンドとしてあるので、数学ではなくて、物事を形式化するという方向性なんです。それで、学部の授業では「情報論理」という論理学の基礎を教えています。

計算機が扱えるのは数や記号だけで、計算機が本質的にしていることは、記号に対する規則的な操作です。このため、論理学が情報科学の素養としてたいせつになってきます。


授業ではどんなことを学ぶのでしょうか?

萩谷:論理学には、構文的な側面と意味的な側面とがあります。
まず、「ものごと」を計算機で扱うためには、「ものごと」をなんらかの記号に対する操作として表現することになります。これが「形式化」で、情報論理の授業では「ものごと」を記号や論理式というかたちでとらえます(→「すべての人が誰かを愛している」参照)。論理学でいう、「構文論」ですね。

それとは逆に、形式化されたもの――記号や規則によって操作されたあとの計算結果が現実世界でどのような意味をもつか、計算機がやっていることが本当に意図したものかどうかを扱うのが「意味論」です。ちょっと難しいですね(笑)。

須田:抽象化された世界、しっかり形式化されて形の決まっている世界があり、それを現実の世界のいろんなモノや現象と結び付ける、区別する、ということをしていくんですね。


萩谷:そうです。授業では、「ものごと」を論理式という形でとらえる一方、論理式がどのような意味を持っているかを意味論としてとらえ、両者の関係がどうなっているかを学びます。

ものごとをどうとらえるかは、元来、系統的に勉強するのが難しいんです。けれども、記号の世界を扱い、その意味を考えることを通して、ものごとをとらえる――モデル化、抽象化を学んでほしい。
と、そんなことを思って教えているつもり(笑)。

すべての人が誰かを愛している:論理式

自然言語はあいまいです。普通に考えると前者になりそうですが、計算機は融通がきかないので、この2つをきちんと区別してあげる必要があります。これが形式化です。
ものごとが、いったん論理式で表されると、さまざまな推論規則を適応していくことができるようになります。

ばらばらの世界を扱う——計算機ができておもしろくなった離散数学

グラフ理論(「離散数学」)についても教えてください。今井先生は、実はこれとこれがつながっている、という意外な説明をよくつけられますよね。

今井:理論が好きで、いろいろなことに興味を持つと、多面的な見方ができるようになります。

「離散数学」というのは、「離散」つまり「ばらばらなもの」を対象として、その関係や組み合わせなど、問題が本質的に持つ構造をとらえるための数学です。

AさんBさんとCさんの3人がいるとき、AさんとBさんは仲が良いけど、Cさんが2人を嫌いだったら、Cさんは孤立しています。そういう関係性を表すのがグラフ理論。

これに対して、いまはここ、何かが来るか来ないかで次はそこかあそこ、その次にはさらに……と状態の遷移を表現するのがオートマトンです(「形式言語理論」で勉強します)。

現実の世界に目を向けると、Webページのリンクはグラフ構造を持っているし、ネットワーク通信の制御は状態遷移図で表せます。このような実世界のさまざまな現象や関係を、離散数学で扱うことができます。

プログラミングコンテストに行ってみても、みんなよく勉強しています。

今井:離散数学は、計算機ができるまではつまらないものだった。有限離散のものをしらみつぶしに調べあげれば終わり。机上の空論で解けてしまう。ところが、計算機ができて実際に計算することが可能になってみると、計算時間が天文学的に爆発してはダメなので、効率良いアルゴリズムが重要になってきます。そこで、この分野に広がりがでてきました。

2年生4学期では、情報科学のための数学を勉強して、群・環・体の情報科学としての入門を学んでいきます。具体的には、暗号のための代数、情報を符号化するための理論、そして情報の量(エントロピー)といった内容です。

計算量の話もいるかな。計算機で何かしようとしたとき、問題・データにいい構造があるということは、いい方式(アルゴリズム)があるということなんです。いい構造がないと計算は難しくなって、実用性がないほど時間がかかります。どの程度難しいかをランク付けし、筋の悪いものはどうしようもないとレッテルを貼るのが計算量理論です。その難しいとレッテルが貼られた問題は暗号理論の基礎になるんですよ。

「計算量理論」の授業では、チューリング機械という計算モデルに始まって、最先端の計算量理論までを解説しています。

科目の間の関係はどうなんでしょう。たとえば、「情報論理」と「計算量理論」がどこかでつながっていたりするんでしょうか?

萩谷:たとえば、情報論理の授業では、プレスバーガー算術が決定可能であるということについて触れますが、実は、決定可能性の先では計算量の話が出てきます。情報論理の題材も、もう少し進むと、ものすごくいろんなところで計算量に関連していくようになるんです。

基礎を教わっていると、あとから「あ、これとこれが関係している」と気づくようになるんですね。

計算をモデル化する——計算機の源に遡る

現実世界のものごとをモデル化する、というお話がありましたが、「計算」ということ自体にもモデルがあるのでしょうか?

萩谷:60年前にいまの形の計算機ができたとき、「モデル」という認識はなくて、誰かが形式化をしていたわけではありませんでした。けれども実際に作られた計算機には、「計算」とは何かということを、なんらかのかたちでとらえたモデルが内在しています。

いま私たちが日常使っている計算機は、メモリ上に並んでいる命令を順番に読み出して実行する、プログラム内蔵方式のモデル(手法)をとっているわけですね。

須田:歯車機構で加減乗算をしていたそれまでの手回し計算機からは、概念に格段の飛躍がありますね。

今井:手回し計算機、ね。日本ならそろばんもあるよ。

萩谷:プログラム内蔵方式の源は、計算機が生まれるしばらく前にチューリングという数学者が考えた、チューリング機械という仮想機械に遡ります。ああ、チューリング機械というと、僕はたくさん話したくなってしまうんですが。

ほかの計算のモデルもあるのですね?

萩谷:ええ、計算をするためにはいろんな手法があります。たとえば、関数の定義と実行を抽象化したラムダ計算機は、単純なモデルなんだけれども、数学的にすごくきれい。

ページトップへ戻る