帰ってきただらだら日記--

2009-08-06

ペタとかエクサとか最初に言い出したのは誰なのかしら

[Python-ml-jp 4803] アッカーマン関数を計算するからはじまるスレッドが面白かった。 A(4,3) を求めるにはどうしたらいいですか、という話。Weisstein, Eric W. "Ackermann Function." From MathWorld--A Wolfram Web Resource にあるように、この数はとてつもなく大きいのでいま地球にある計算機ではまずムリ。ペタとかエクサとかそんなチャチなもんじゃあ断じてねえもっと恐ろしいものの片鱗を味わったぜ的な

で、そこまでは id:nishiohirokazu さんたちも指摘していることなんだけど、おもしろいなあと思ったのは、そもそも Ackermann 関数が有名なのは、上記の MathWorld 記事の冒頭に書かれてる通りで原始帰納関数でない全帰納関数の具体例だから。そしてその標準的な証明はまさに A(n,n) の大きくなる速さがどんな原始帰納関数より速いということを使う。計算論の教科書にはたいてい載ってる(んじゃないかな)。

それとおもしろいのは、これくらい大きな数はそもそも書く方法がないってこと。A(4,3) あたりでもごにょごにょする。これは、むかしむかしから気になることのひとつで、もっとも気になるといっても、どうすれば気にならなくなるのかわからない話なんだけど、いまのところの突き進め方として私が知ってるのは次の二つ。

  • Ultrafinitism ... 書き下し方がわからんような馬鹿でかい数の存在を証明に使うのは禁止しちゃうよ派
  • 巨大数研究室 ... 悩まずにとにかく大きな数の書き方を考えちゃえ派

んー、たとえば A(4,2) と A(4,3) の間にはだいたい A(4,3) 個くらいの数があるんだけど、それらのほとんどには簡単な表記法がない。いちおう機械的な方法としては Rissanen の universal coding というのがあるにはあるけど、それもねえ。

ちょうど2ちゃん数学板の巨大数スレが熱かったころに生暖かく見守っていたのだけど、結局ふぃっしゅ数の定義を理解することが出来んかったのはいまでも悔しい。途中で数学屋っぽいのが出てきて整理してるのをみて方程式の解として定義してるっぽいことまではわかったんだが、だれか学部の2年生にわかる程度の丁寧さで書いてくれんか。

ということをむかしも書いた気がするけど、まあいいや。忘れっぽいのはステキなことです。そうじゃないですか?

tomonyatomonya 2009/08/06 13:04  だからなんだと言われると、どうしょうもないんですが、最近、中島みゆきの「雨がふ〜る〜」というのが反復していて(福岡県在住なので)、さらに自分のメルマガの後段でそれを使って想起が強化されていたので、最後の最後でシンクロニシティーを感じて、思わず書き込んでしまいました。
 なんでプログラマでもない人間がここを読んでいるかと申しますと、20年以上前に某所で行き会ったことがある通りすがりだからです。

tomonyatomonya 2009/08/06 13:05  あちゃー、ログイン状態で書くとブログがばれるんですね。あーあ。その節はいろいろご迷惑をおかけいたしました。

tomonyatomonya 2010/07/17 01:23 平田祥さんと再会しました。こちらです。http://twitter.com/maho_tukai2000
間接的にはツイッター経由での再会です。

スパム対策のためのダミーです。もし見えても何も入力しないでください
ゲスト


画像認証

トラックバック - http://d.hatena.ne.jp/g5n/20090806/1249522603
hits