Mathematics for Programmer

プログラマに必要な数学

一般的なプログラマに必要な数学は, 離散数学と呼ばれる数学です. もちろん, メディア (動画, オーディオ, 画像など) をあつかうエンジニアになると, 微分積分や線形代数, 確率・統計といったこと (つまり, 情報理論や信号処理) も必要になりますが, そうでないプログラマが知っておきたいのは離散数学です.

離散数学をまったく学んだことがなくても, プログラムを書いているのであれば, 無意識のうちに離散数学を使っています, なぜなら, プログラムという技術が, 離散数学によって支えられているからです.

離散数学の定義となると, わたしもよくわかっていないのですが, あつかうトピックスとしては, 以下のようなことがあげられます.

  • 集合
  • 論理
  • 順列・組み合わせ
  • 数学的帰納法・漸化式
  • 背理法
  • オートマトンと形式言語
  • グラフ理論

集合

数学の集合の概念をプログラムの世界にもちこんだのが Set という型.

論理

ブール型, つまり, true / false という値や, 半加算器・全加算器のようなデジタル回路にも利用される.

順列・組み合わせ

数え上げを一般化する. 例えば, 配列のインデックスの算出など.

数学的帰納法・漸化式

ループ処理 (再帰) が, 目的を果たすこと, 終了することを保証する.

背理法

停止判定問題の証明などに利用される.

オートマトンと形式言語

コンパイラ (プログラミング言語の開発) や, 正規表現などに利用される.

グラフ理論

ダイクストラ法などのアルゴリズムや, コンピュータグラフィックス (CG) にも利用される.

分割統治

上記にあげた離散数学のトピックスのほとんどで共通することがあります. それが, 分割統治という考え方です. 分割統治とは, 「複雑な問題を, 単純な問題に分割する」, あるいは, 「大きな問題を, 小さな問題に分割する」という考え方です.

例えば, 集合によって, 整数を偶数と奇数という集合に分割します, 論理によって, 真の場合と偽の場合を分割します. 組み合わせは, ある事象が発生する場合と発生しない場合に分割して問題を解決します. また, 数学的帰納法 (漸化式) は, 2 ステップ (あるいは, n - 1 のステップ) に分割することで大きな問題を解決します.

計算不可能な問題

離散数学のなかで, 比較的プログラムに近いトピックスの 1 つが, 計算不可能な問題 (計算可能性理論 : Computability Theory) ではないでしょうか.

計算不可能な問題とは ?

計算不可能な問題とは, 「解を求めるのに莫大な時間を要する問題」でもなければ, 「解が存在しない問題」でもありませんし, 「未解決問題」のことでもありません.

計算不可能な問題とは, プログラムで解くことが原理的に不可能な問題のことです. 言い換えると, プログラムで解くことができる問題の集合に含まれない問題ということです.

計算不可能な問題の代表例が, 停止判定問題 (Halting Problem) です.

停止判定問題

まず, プログラムの定義を「データを入力すると結果を出力する」ものとします. しかし, なかには, 永遠に停止せずに, 結果を出力しないケースもあります. つまり, プログラムのふるまいは, 必ず以下のどちらかになります (有限時間内というのは, 現実的な時間内でなくてもかまいません).

  • 有限時間内に動作を停止する (エラーの場合も含む)
  • 有限時間内に動作を停止しない (永遠に動作を停止しない)

後者は, いわゆる, 無限ループ がその最たる例でしょう.

while (true) {
    // ...
}

プログラムを調べるプログラム

プログラムを調べるプログラムというものが存在します. 代表例は, 「コンパイラ」です. 高級言語を機械語に変換するプログラムです. 「ソースコードチェッカー」もそうです (フロントエンドエンジニアであれば, ESLint や TSLint がおなじみですね). さらには, 「デバッガ」も人がプログラムを調べるためのプログラムです.

ここで, 「プログラムの停止判定を実行するプログラム」が実装できると仮定します (便宜上, HaltChecker という関数を実装できると仮定します). ここで, 停止判定とは, 「プログラムにデータを入力して実行したときに, 有限時間内に動作を停止するかどうか ?」を判定するということです.

/**
 * @return p に d を入力したとき, p が有限時間内で停止する場合, true を返す. p に d を入力したとき, p が有限時間内で停止しない場合, false を返す
 */
bool HaltChecker(p, d);

1 つ注意点があります. HaltChecker対象となるプログラムを実際に動作させて判定するという方法は使ってはいけません. なぜなら, 対象となるプログラムが永遠に停止しない場合, HaltChecker も永遠に停止しないからです.

次に, SelfLoop という関数を実装します.

void SelfLoop(void (*p)()) {
    bool halts = HaltChecker(p, p);  // 入力が 2 つとも p であることに注意

    if (halts) {
        while (true) {
        }
    }
}

SelfLoop は, 与えられたプログラム p を HaltChecker の入力に渡して, その結果, true であれば, 無限ループに入るという実装になっています.

ここで,

  • Program A 自身をデータとして, Program A に入力としてあたえると, 停止する
  • Program B 自身をデータとして, Program B に入力としてあたえると, 永遠に停止しない

という 2 つのプログラムの存在を定義します.

SelfLoop のふるまいとあわせて考えると, 以下のようになります.

  • Program A を SelfLoop に入力としてあたえると, 停止しない (無限ループ)
  • Program B を SelfLoop に入力としてあたえると, 終了して停止する

そして, 最後のステップです. SelfLoop の入力として, SelfLoop そのものをあたえます.

SelfLoop(SelfLoop);
有限時間内に停止する場合
この場合, HaltChecker(SelfLoop, SelfLoop)false になります. これは, SelfLoopSelfLoop を入力としてあたえると, SelfLoop は停止しないという意味になります. これは, 矛盾です.
有限時間内に停止しない場合
この場合, HaltChecker(SelfLoop, SelfLoop)true になります. これは, SelfLoopSelfLoop を入力としてあたえると, SelfLoop は停止するという意味になります. これも, 矛盾です.

もれなく, ダブりなくのケースで矛盾が発生してしまいました.

これは, HaltChecker が実装可能, すなわち, 「プログラムの停止判定を実行するプログラム」が実装できると仮定したことが問題というわけです.

背理法により, プログラムの停止判定を実行するプログラムは実装できないことが証明できました. ちなみに, 停止判定問題が計算不可能な問題であることは, チューリングによって証明されました.

停止判定問題の例

プログラムのふるまいを調べる問題の多くは, 計算不可能な問題です.

  • 入力としてあたえた 2 つのプログラムが, 「任意の入力に対しても同じ動作をするかどうか」を判定するプログラム
  • 入力としてあたえたプログラムが, 「入力した整数が素数であることを判定できるか」を判定するプログラム
  • 入力としてあたえたプログラムが, 「任意の入力に対しても 1 を出力するかどうか」を判定するプログラム
  • 入力としてあたえたプログラムが, 「ある一定時間 T 内に終了するかどうか」を T よりも短い時間で判定するプログラム

学び

離散数学は, 大学の講義ですら必修でないことも多く, 特に, 高校数学ではあつかわれない, オートマトンと形式言語や, グラフ理論などは, よほど興味をもつか, 必要に迫られない限り学ぶ機会が少ないと思います.

1 つ 1 つの詳細は, 今後こちらのブログでもまとめて投稿したいと思います. この投稿では, 離散数学とプログラムってこんな関係があったのか ! と思っていただければと思います.

最後に, プログラマが (離散) 数学をザクっと学ぶのによさそうな参考書を記載しておきます (計算不可能な問題は, 下記を参考にしました).

Share Comments
comments powered by Disqus