モンキーはシェイクスピアになりうるか

無限の猿定理と言う言葉を知っているだろうか。

概念は確率論として知っていたが、そんな「原子も積もれば心(宇宙)になる」的な概念にこんな素敵な名前がついているとは知らなかった。

「無限のモンキー」素晴らしい。

概念としては、どれだけ微小な確率であっても、確率として0でない以上それは可能性として存在し、その可能性が有る以上、時間さえかければどのようなことも現実に起こりえる。というものだろうか。

これはマーフィーの法則として有名な「失敗する可能性のあるものは、失敗する。」と同じ考え方で「成功する可能性の有るものは、成功する。」と言えるだろう。

無限の猿 (ハヤカワポケットミステリ)

作者: レスロバーツ,安倍昭至
出版社/メーカー: 早川書房
発売日: 1990/06
メディア: 単行本
この商品を含むブログを見る

アインシュタインと猿 (サイエンス・アイ新書)

作者: 竹内薫,原田章夫
出版社/メーカー: SBクリエイティブ
発売日: 2010/07/16
メディア: 新書
購入: 2人クリック: 3回
この商品を含むブログ (3件) を見る

====
無限のモンキーの例としては「モンキーにタイプライターを渡せば、時間をかければシェイクスピアも生まれうる」と言う確率の例示のようだが、Wikipediaでも指摘が有るようにモンキーは実際にはランダムに文字を打たない。

例えばヒューマンにしても、ランダムに文字を撃つとすればキーボードの真ん中あたりの行をカタカタカタとして「skl;jf」辺の文字列が生まれやすいだろう。実際にこの文字列は非常によく目にする。

なので実際の確率としてはモンキーのような知的生命体では無く、完全にランダムに文字を入力することの出来る超超高次知的生命体を必要とする。そうしなければシェイクスピアどころか、QWERTYの存在しない文章しか入力され得ない。

それどころかコンピュータを使ったとしても完全にランダムな値というのは存在しえず、CPUノイズなんかを利用した乱数発生にしてもその種が再現可能であれば擬似乱数となってしまう。

だがそんなしょうもないことにこだわっていては先に薦めない。細かいことを気にしなかったことでモンキーはヒューマンに進化し、ヒューマンはスクイッドに進化する。

ということで、実際としてシェイクスピアはどれほどの時間がかかるのか考えてみた。

まずこの問題はシェイクスピアというのがミソだろう。これが日本語であれば特定の一文字が出現する確率だけでも数百倍に膨れ上がる。日本語を5000文字とすると、英語100文字としても50倍。二文字の"2千5百万分の1"対"1万分の1"という素晴らしき可能性爆発を起こす。しかも実際にはかな入力として漢字変換などを考えると、シェイクスピアは日本語数百文字の可能性にも満たないのではないだろうか(計算してない)。

そしてこれを漢字変換なんかも考えるとバックスペースの入力やカーソルキーの入力などかなり特殊な条件も出てくるので、「タイプライターを使ってシェイクスピア」としているのだろう。明瞭にするために条件は簡易化したほうが良い。

ということで考える。

文字は「ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789!@#$%^&*()_+|-=\{}[];:'"」この86文字とする。スペースやら改行やらが抜けているが、他の使われづらい記号をいろいろ入れているのでそれで同等とする(今気がつくとスラッシュやバッククォート、山カッコなど多く抜けている)。

唐突にシェイクスピアを総べても愚民どもにはついてこれまい。

そこで一節!

しかし息切れを回避するためにもう一声!

コレでもう安心

無理なく猿の惑星征服の第一歩

すなわち我々の目標とは

MONKEY

ということでまずは「MONKEY」と文字がどれくらいでマッチするか実験。

MONKEYにマッチしないのであればシェイクスピアも生まれないし、MONKEYがマッチすればシェイクスピアが生まれる可能性も存分に有るだろう。

そして実験したコードはこちら。

#!/usr/bin/python3

import random

text = "MONKEY"

chars = r'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789!@#$%^&*()_+|-=\\{}[];:\'\"'

count = 0
while True:
    count += 1
    make = ''.join([random.choice(chars) for i in range(len(text))])
    if text == make:
        print(count, make)

だがこれがまぁ予想通りというべきか全然終わらない。余りにも終わらなくて途中で何度もチューニングしてやり直したほどになる。だがまぁ終わらない。

tp9U(b

tMuI5A

m;jO\j

x#kqW2

chq]'A

M2'cdA

[oDS*S

'%7rRH

I#zPa(

H7BlNt

1N-|P1

^KC9g\

WV}=D4

p!tvuw

g}&bbr

"&9Z^m

01Y_Y)

)b_Xay

8q8]es

0P6zp

FY(\{h

{|^}!@

0r5k0\

XV@\n

2]qcL0

}P|brE

bPUy'x

ju^&}^

!I6\Ju

j\_{Nv

(=gVXu

iBM89E

([gJ@U

NGm#-p

pWesDO

P4+tO:

]jYcUt

p2l9qj

途中で出力してみてもこんなのがずっと出続けるだけだ。MONKEYどころかアニマルにすら程遠い。

そこで気がついたが確率を計算してみた。

特定一文字の出現確率は1/86になる。ということは二文字では1/7696だ。あまり増加していないように感じるかも知れないが、6文字だとこうなる。

$86^6 = 404,567,235,136$

四千億!!!

ざっと見たところ私のコンピュータでは1秒間に30万回ほど計算できているが、それでも1348557.45秒かかる。ざっと375時間だ。

私のコンピュータはi7-2600になるので4コアHTだ。マルチスレッドの8スレッドで動かせば単純には46時間。平均すると1日で終わることになる。

ということでコードを修正した。

#!/usr/bin/python

import sys
import random
import threading

text = "MONKEY"

chars = r'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789!@#$%^&*()_+|-=\\{}[];:\'\"'

class MonkeyThread(threading.Thread):
    def run(self):
        count = 0
        while True:
            count += 1
            make = ''.join([random.choice(chars) for i in range(len(text))])
            if count % 100000 == 0:
                print(make)
            if text == make:
                print(count, make)
                sys.exit()

if __name__ == '__main__':
    threads = []
    for i in range(8):
        threads.append(MonkeyThread())
        threads[-1].start()