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

亀岡的プログラマ日記

京都のベッドタウン、亀岡よりだらだらとお送りいたします。

いろふさんの一意性を証明する #irof_history

この記事はirof Advent Calendar 15日目の記事です。

多態性をもつirofさん

irofさんの多態性は色々なところで言及されています。

ふむ。だとすると、私達が今まで見てきたirofさんは一体何種類のirofさんだったんでしょうか・・・。不安でしょうがいないですね。

いろんなirofさんが一種類であることを証明しよう

それでは、そんなさまざまなirofさんを見てきたとしても、それは一種類のみしか見ていないことを数学的に証明してみましょう。

証明には、「数学的帰納法」を用います。

つまり、

  1. n-1 人のirofさんが同一インスタンスであった場合、irofさん一人を加えたn人もまた、同一インスタンスであること
  2. 1人 のirofさんは同一インスタンスであること

上記二点を示せば、数学的帰納法により、任意のn人のirofさんは同一インスタンスということになります。

証明

まず、2.は自明ですね。さすがにその場にいる1人のirofさんは、観察により確率収束し、単一のirofさんになっているはずです。

問題は1です。ちょっと図で書いてみましょう。

f:id:posaunehm:20131215234941p:plain

n - 1個が同一インスタンスの場合、n個目が同一インスタンスである保証は一見無いように思えます。

しかし、、、この”n - 1個”、べつに左端から取ることに限定されないのです。あくまで、「適当なn - 1個」をとればそれが全て同一インスタンスである、という前提条件なので。

f:id:posaunehm:20131215235303p:plain

上記の中括弧で示したn-1個のirofさんを含むグループは、そのグループ内においては、すべて同一のインスタンスのはずです。一方、上下のグループにおいて、破線部分のirofさんは共有されています。

共有されている以上、上下のグループが異なるインスタンスであるとすると、共有されている破線内のirofさんは複数の状態が共存してしまいます。これもまたありえませんので、2つのグループに属するirofさんは同一のインスタンスであることになります。

つまり、n個全てが同一のインスタンスです。これは1.の証明に他なりません。

1,2がともに証明されましたので、めでたく、任意のn個のirofさんは必ず同一インスタンスであることがわかりました。

これで安心して寝られますね!!

間違っています

上記証明は、ある致命的な欠陥があります。結城先生の名著、プログラマの数学に、類似の問題が記されています(というか、このネタは丸パクリです。)

種明かしには是非買って読んでみよう!

プログラマの数学

プログラマの数学