計算とは何か(試論)

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

続きを読む

東大後期数学 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で実装してみた

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 を触っているうちにそんなことを思って、「実体のある型レベル自然数」を実装しました。実体のある型レベル自然数というアイデア自体ほかで見たことが無いので、この実装は完全にオリジナルのものだと思います(似たことを考えている人がいたら教えてください)。

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

続きを読む

メソ体、そして少しの数学

少し詳しく化学を勉強した人ならば、立体異性体の話に関連して「メソ体」あるいは「メソ化合物」という言葉は聞いたことがあると思います。

  • キラル中心(特に不斉炭素)をいくつか持つが、鏡像がそれ自身と異性体にならない分子

というのが普通の定義でしょう。メソ体になる自明なものとしては、分子内対称面を持つ分子があります。これは広く知られた話でしょう。

さて、ここからが問題です。

続きを読む