multiplus

気まぐれに書評とか。

『チューリングの計算理論入門』

私はコンサルタントとして今働いているわけだけど、そのうち専門分野が2つある。1つは金融、そしてもう1つはITだ。そのうち金融分野ではトレーディングが専門ということになる。要するにフロントオフィスが専門領域だ。

一方で、ITはといえばまだまだ勉強不足感が甚だしい。とくに、コンピューターがどのようにして動いているのかという基礎理論の知識の不足が甚だしいと感じる。そこで、すこし情報関係のお勉強をしてみようと思って読み始めた本がこれ。

チューリングの計算理論入門 (ブルーバックス)

チューリングの計算理論入門 (ブルーバックス)

個人的な感想だけれど、エンジニアでもとくに文系卒のエンジニアだったりすると、チューリングの名前を知らない人が多い。チューニングですか?と返ってくるという笑い話つきだ。そんな、チューリングを知らない方にはとくにオススメできる一冊。

チューリングが作ったものに有名なものがある。それは、チューリングマシンという機械だ。これは、ある文法に沿った命令を書くと、その通りに物事を処理してくれるという優れた機械で、今のコンピュータの原型となったものだ。

チューリングの研究でとりわけ大きな業績はチューリングマシンなわけだが、それ以上に重要な業績がある。それが、ヒルベルトの「決定問題」の限界の証明だ。ヒルベルトの決定問題とは、「機械的な手順によって、証明可能であるか証明不可能であるかをチェックすることは可能か?」という問題のことである。つまり、アルゴリズムによって証明はチェックできるか?という問題だ。

アルゴリズムとは、「計算手順」のことだ。これは初めて聞いた言葉だ、という方も多いだろうから少し説明を加えたい。たとえば、以下の様な問題を考えるとする。

「1〜100までの数のうち、素数をピックアップするプログラムを作成せよ」

この問題を解く手順として、いったいどのようなことが考えられるだろうか。そもそも、100までの数の素数全体像を知っていたとしたらそれを書き出すことも可能だろう。しかし多くの場合、それは面倒だし、なにより終了値がnだった場合、そのプログラムは非常に汎用性の低いプログラムだということになってしまう。

そこで、素数判定を行うために以下の様な手順を考えるとする。

  1. 1〜100の表を作る。このとき、1は削除する。
  2. 2の倍数を表から削除する。
  3. 3の倍数を表から削除する。
  4. 5の倍数を表から削除する。
  5. 7の倍数を表から削除する。
  6. 残った数をすべてリストアップする。

こうすることで、素数を効率的に判定することができる。そしてこの1〜6の「手順」こそがまさに「アルゴリズム」である。したがって、アルゴリズムとは手順のことだ。(なお、上記のアルゴリズムのことを「エラトステネスの篩(ふるい)」という)

ここで先ほどのチューリングの命題に戻ると、「証明できるか、できないかをチェックする手順を書き表すことは可能か?」と言い換えられる。ここまでくれば、多くの人にとってわかりやすいだろう。そしてこのことを証明するために、チューリングマシンというものを製作し、決定問題の証明を行った。

結果的には、チューリングは以下のことを発見している。

  • 解きたい問題が「有限の手段」で表せれば、それはチューリングマシンで記述可能=計算可能
  • 計算可能の問題の中で、実行するとチューリングマシンが止まらなくなるものがある
  • チューリングマシンが「止まるか」「止まらないか」を判定するマシンをつくろうと思う→結果的には作れなかった
  • 決定問題の否定的な結論が導かれることになった

要するに、一定の条件下では決定問題は機能するといえるけれど、ある一定の条件下では決定問題は適用不可能だということだ。これは、当時ゲーデル不完全性定理として発見していたことと酷似している。

チューリングの発見は、私はコンピュータの限界なんじゃないかと思う。コンピュータは自分で考えることができない。なぜなら、「考える」という動作は、有限の手段では表せないからだ。将棋の世界ではすでにコンピュータが勝ち始めているじゃないか!とおっしゃるかもしれない。だが、あのコンピュータは結局アルゴリズムに則って動いているに過ぎないし、相手の手・状況に受動的に対応して適用するアルゴリズムを変えているに過ぎない。自分でアルゴリズムを作り上げているわけではないのだ。こういう点から、コンピュータは自分で考えることができない存在だ。

コンピュータは圧倒的に「例外」に弱い。これは、上述の「自分で考えられない」ことととても強い関係を持つ。いい例がSiriなのではないだろうか。ちょっとでもSiriのわからない単語をいうと、すぐに「Googleで検索して下さい」みたいなことを言ってくる。また、わかりにくい発音をするとすぐに「わかりません」と答える。「推察」ということが、コンピュータにはできない。なぜなら、コンピュータは無数のアルゴリズムを内蔵してそれらを当てはめているにすぎず、アルゴリズムで処理しきれないことには一切対応できないからだ。

そしていつか、この問題を乗り越えるコンピュータが出てくるのかもしれないけれど、そうなってしまったら世の中はどうなってしまうのだろうかと考えさせられる。