読者です 読者をやめる 読者になる 読者になる

非現実的非日常的非常識的、非日記。

言葉, 数学, 音楽, IT, etc.

計算とは何か(試論)

東京大学の今井浩教授の講義で「計算の理論」というものがあって、そのレポート課題で「計算とは何かというテーマについて考えたことをA4で1-2ページにまとめよ。」という問題が出されました。正確には「計算の理論前半を通してアルゴリズム・計算量の観点から」という但し書きが付いていました。いろいろと忙しくてレポートのために割く時間も余力も小さかったのですが、締切直前になって必死に文章を書くうちに個人的にいろいろな気づきがあり、せっかくなので公開することにしました。論理が十分に練られていない部分も多々あり、いろいろと未熟な文章ですが、何かの足しになれば幸いです。



計算とは何か。われわれの身の回りには電卓もあるしPCもあるしスマートフォンもあるし、普通の洗濯機や炊飯器にすらマイクロコンピューターが入っている。量子計算やDNA計算といった摩訶不思議な計算方法もある。しかし、計算について深く論じるにあたって、それらの計算機はあまりにも複雑すぎるし、よく分からない部分も多い。まずはなるべく原始的な、かつ現実的な計算について考えてみよう。


自然数の足し算を考えてみる。筆算や算盤を思い浮かべるかもしれないが、位取り記数法などという高度なものも使わない。足し算をするにはこうすればいい。

棒をn本(数えながら)書く。そのすぐ隣に棒をm本(数えながら)書く。全体の棒の数を数える。このときに得られる数がn+mである。

この計算の正しさは明らかだろう。n+mの定義をこの計算方法によって与えてしまっても構わないくらいだ。

ただし、数を数えるというのは、本当に簡単だろうか?まずどの棒まで数えたかを覚えていなければならないが、それはまだいい。日本語で普通に数えるとき、九の次は十だし、九十九の次は百である。ここに位取り記数法が隠れていて、数を覚える子供を見ればわかるように実は難しいことをしている。これすらも解消するには、五を「一一一一一(いちいちいちいちいち)」と呼ぶようないわゆる一進法を採用すれば、棒ごとにただ一と言えば、数えたことになる。まったく馬鹿げているが、一般にこの方法で足し算を行うことができる。


一般に、と言ってしまったが、nやmは本当になんでもいいのだろうか?おそらく、現実世界で遂行するには宇宙の総原子数よりは小さくなければならないだろう。こういう厄介事を避けるには、棒を書くスペースが十分に広いとか、「一」と唱えるための時間が十分あるとか、何かしらの理想化が必要である。

チューリングマシンの定義でも同じようなことがあった。無限に大きい記憶領域があって、計算時間の上限はなくて、入出力の大きさは宇宙に収まりきらないくらい大きくても構わない、という理想化である。無論、人間の認識能力や処理能力を遥かに超えている。

この理想化は便利であるが、あくまで理想化であることを忘れてはならないと思う。


さらに、チューリングマシンの定義ではほかにも、操作の正確性も理想化している。このことは忘れられがちなのではないだろうか?人間はしばしば計算ミスをする。ここでの計算は、外界の絡む筆算であることもあるし、脳内で完結している暗算であることもある。また、コンピューターであっても、外部から物理的な影響を受けるなどして、ビットが逆転し計算ミスをすることが、非常に小さい確率である。道具を使った人力の計算としては算盤による計算が考えられるが、これも珠の操作に失敗する可能性はあるし、珠の位置を見間違える可能性もあるし、算盤が壊れる可能性もある。おそらく、完全に正確な操作というのは実現できない。

とはいえ、世界が制御できないことだらけであることを踏まえると、計算における操作は実用上十分に正確である。逆に言えば、何かしらの動的な流れが計算として成立するには、操作の十分な正確性が重要である。

このことを僕は量子計算で特に強く感じた。量子計算はまずもってミクロの、観察者効果によって容易に損なわれる繊細な世界を取り扱う。量子ビットを捉えるには何回も観測実験を行いビットの確率分布を調べねばならず、そのためには状態の重ね合わせを何回もできるだけ正確に行わねばならない。

道具を使った計算は、制御の行き届いた実験の一種であると言えるだろう。


暗算の操作は脳の内部で起こっている。しかし、暗算は普通の思考とは何かが違う。暗算において、仮想的な操作対象として数字や算盤などがイメージされている。操作する主体が脳内に操作する客体を抱えているように感じられる。

ところで、人間は自身の思考自体を制御することも難しい。自由に道具を操作しているつもりでも、実は操作主体が道具に影響されている、ということすら珍しくない。PCやスマートフォンはわれわれの思考をすっかり変えてしまったと言える。

こうして考えてみると、道具を使った計算は、人間と道具のなす系全体が思考の主体としての役割を果たしていると考えるべきではないだろうか?割り算の筆算でよく分かるように、筆算にもたいてい何らかの暗算が関与しているが、こうした暗算と筆算の間の連続性も自然に理解できる。計算機を思考の主体とみなしてしまう立場を取れば、複数の計算機が並列計算などで協働するときその系全体が思考の主体であるといえる。操作の主体と客体の区別は曖昧であり、両者は有機的につながっている。

計算は、入力を与えて、少し時間が経って出力が得られる、という動きである。しかし、適当に薬品を混ぜると化学反応が起こって色が変わる、というような実験は、動きではあるが、そのままでは計算とは言えない。しかしそれが思考と強く結び付くと計算と呼べるようになる。DNA計算が好例で、これは基本的には生化学反応だが、入出力にきちんとした意味がある。計算は思考における意味を必要としているのだ。先ほどの馬鹿げた足し算でもギリギリ計算であるように感じられるのは、足し算という明確な意味があるからである。

カリー=ハワード対応は型と命題、プログラムと証明の同一視を示唆するが、それを認めるならば計算と推論も同一視していいと思う。どうも計算というとビット列が、推論というと木構造が想像されるが、いわゆるゲーデル化からもわかるように、ビット列も木構造も本性は同じである。どちらも計算と推論の、より根源的には思考の、再帰的な本性を反映したものであると言えるだろう。計算も推論も、思考に沿った動的な流れに付けられた名前であり、両者は根本では同じものだと言えると思う。

人工知能で巷が騒いでいる今こそ、無機質な数の処理としてではなく、思考の一部としての計算を強く意識せねばならないと思う。そして、人工知能を操作しているつもりでも、われわれが人工知能に操作されているかもしれない。思考が外部化できるのは便利だが、外部化が進めば進むほど、操作の主従関係自体が曖昧になる。計算機とどう付き合うか、われわれは踏みとどまって考えるべきであろう。


計算では速度やメモリの効率も重要である。足し算の筆算も先ほどの一進法でなく位取り記数法を使うと、遥かに速く計算できるし、使う紙の大きさも少なくて済む。思考の資源の節約になるからこそ、われわれはふだん位取り記数法を用いているのである。暗算であってもそうである。

ここでアルゴリズムの改善があるわけだが、アルゴリズムははっきり意識できる、という点が重要である。われわれの脳内では作業を効率化するためにさまざまな機構が無意識下で常に働いている。しかしその機構には人間の生物としての限界があるだろう。アルゴリズムを考えることは、思考を意識的に、理性的に見つめて効率化するために、非常に役立つ。

そもそも、PCは人間と比べて単純作業の処理速度が遥かに速いし、正確に記憶できる量も遥かに大きい。アルゴリズムを無視しても、PCのような道具を使うこと自体、思考の効率化や限界の拡大となっている。そして道具としては、普通のPCも選べるし、スーパーコンピューターも選べるし、量子計算機も選べる。

計算は思考の一部であるが、アルゴリズムや処理方法を外部化できる。だからこそ、意識的に、人間的限界を超えて、改善することができるのである。


とりとめのない試論となってしまったが、ここでまとめよう。

計算とは、思考のうち、外部化可能で、意識的に制御・改善することのできる部分である。このことをふまえて、人間や世界の限界を忘れずに、柔軟な発想を持って、計算の未来を考えてゆかねばならない。

東大後期数学 1998-3(2) の必要性の証明

数学

1998年度の東大後期試験数学第3問(2)は、大学入試としては最も難しい問題だと言われています。問題文が冗長であるので、説明の都合もあり、自明な範囲で以下のように問題を書き換えます。

最初、白丸が1個ある。操作は以下の3つのいずれかを行う。(操作を繰り返すたびに、白丸と黒丸が一列に並んでいる状態が生じる。)

  • ア―隣り合う2つの丸の間に白丸を入れ、その2つの丸の色をそれぞれ別の色に変える。
  • イ―列の左端に白丸を追加し、元々左端にあった丸の色を別の色に変える。
  • ウ―列の右端に白丸を追加し、元々右端にあった丸の色を別の色に変える。

この操作を (n-1) 回繰り返して n 個の白丸が並んだ状態を作ることができるために n の満たすべき必要十分条件を求めよ。

答えは「nを3で割った余りが 0 か 1 であること」です。十分性は容易に示せるのですが、必要性の証明が問題となります。

数日前この問題を見て考えた時は必要性がまるで証明できず、しばらく考えた後に諦めました。昨夜はコーヒーを飲んだせいかなかなか寝付けず、この問題が解けていなかったことを思い出して考え込んでしまってさらに寝付けず、解けてしまってテンションが上がってさらに寝付けず、気づけば寝ていて今朝目覚めました。一応他の人の解き方も調べてみると楽しい証明がいくつもありましたが、自分の思い付いた証明は分かりやすさの点では優れていると思うので紹介しておきます。

続きを読む

頂点をランダムに選んだ時の三角形の面積の期待値

数学 代数 確率

「一辺1の正方形領域から3点をランダムに選んだ時に3点を結んでできる三角形の面積の期待値」を初等的な方法で求めました。

続きを読む

ポリアの壺問題の帰納法も計算も要らない証明

数学 確率

ポリアの壺問題 (Polya's urn problem) というのは確率に関する有名問題で、次のようなものです。

壺の中に赤玉がa個、白玉がb個入っている。ある正の整数kを決めておく。これから次の試行を繰り返す。

  • 壺の中から1個玉を取り出し戻す。その玉が赤玉ならば赤玉をk個、白玉ならば白玉をk個、壺に新たに加える。(全体の個数はk個増える。)

このとき、n回目に取り出す玉の色が赤玉である確率を求めよ。

実は n によらずに確率は a/(a+b) となります。

続きを読む

実体のある型レベル自然数をHaskellで実装してみた

Haskell IT

GHC では型システムが急速に進化していて、ついに型レベル自然数 (type-level natural number) も組み込まれました。

この型レベル自然数は、0, 1, 2, ... というリテラルによって型レベル自然数を得られ、足し算・掛け算・冪乗・引き算・比較が可能です。考えられる使い道としては、配列の要素外アクセスを制限したり、バージョン管理をしたりといったことを、コンパイル時に静的に行うことでしょう。

しかしこの型レベル自然数の類 (kind) は Nat であり、真の型(proper type, 実際に値を持つ類 * の型)ではありません。これはもったいない気がします。型に属する値が何種類あるか、という観点から、ヴォイド型 Void0、ユニット型 ()1、ブール型 Bool2、直和 Either a b は足し算 a + b、直積 (a, b) は掛け算 a * b、関数 b -> a は冪乗 a ^ b と対応していますから、有限の種類の値しか持たない型を型レベル自然数として使えれば嬉しいと思いました。

GHC 7.8.3 を搭載した新しいバージョンの Haskell Platform が出たこともあり、久しぶりに Haskell を触っているうちにそんなことを思って、「実体のある型レベル自然数」を実装しました。実体のある型レベル自然数というアイデア自体ほかで見たことが無いので、この実装は完全にオリジナルのものだと思います(似たことを考えている人がいたら教えてください)。

速度の面でどうしても限界があることもあり、実用性があるかどうかは分かりませんが、この実装のテクニックを応用することで便利な道具がいろいろ作れる気がするので、「実体のある型レベル自然数」の実装を、詳しく紹介していくことにします。

続きを読む