HAKMEM

/hak´mem/, 名詞

MIT AI Memo 239(1972年2月)。MITやその他の多くの人々が寄稿した、洗練された数学的・プログラミング的ハックの伝説的なコレクション。(このメモのタイトルは本当に「HAKMEM」であり、これは‘hacks memo’を6文字に縮めたものである。)その中には非常に有用な技法、強力な定理、興味深い未解決問題もあるが、大半は数学とコンピュータの雑学に分類される。以下は項目のサンプル(著者付き)で、少し意訳してある。

項目41(Gene Salamin):\(2^{18}\)未満の素数はちょうど23,000個存在する。

項目46(Rich Schroeppel):ブリッジの手札で最もありそうなスート分布は4-4-3-2であり、最も均等に分布した4-3-3-3とは対照的である。これは世界が不均等な数を好むからである。すなわち、物事は最低エネルギーの状態にはならず、最低の無秩序エネルギーの状態になるという熱力学的効果である。

項目81(Rich Schroeppel):5次の魔方陣(つまり、1から25までの数を5×5に並べ、すべての行・列・対角線の和が同じになるもの)を数えよ。回転や鏡映によってのみ異なるものを数えなければ、約3億2000万個ある。

項目154(Bill Gosper):任意のプログラミング言語が機械独立であるという神話は、2のべき乗の和を計算すれば簡単に打ち砕かれる。もし結果が符号+で周期= 1でループするなら、あなたは符号絶対値方式の機械を使っている。もし結果が-1で周期= 1でループするなら、2の補数方式の機械である。もし結果が最初を含めて1より大きい周期でループするなら、1の補数方式の機械である。もし結果が最初を含めず1より大きい周期でループするなら、あなたの機械は2進ではない。パターンが基数を教えてくれるはずだ。もしメモリが尽きるなら、文字列または多倍長数システムである。もし算術オーバーフローが致命的エラーなら、読み取り専用の頭を持つファシストの豚が機械独立性を強制しようとしているのだ。だがそもそもオーバーフローを捕捉できる能力自体が機械依存である。この戦略によって、宇宙、より正確には代数を考えてみよう。X =2の多くのべき乗の和 = ...111111(2進)とする。さてXをそれ自身に加える。X + X =...111110。したがって2X = X - 1なのでX = -1となる。ゆえに代数は2の補数方式の機械(宇宙)の上で動いているのである。

項目174(Bill GosperとStuart Nelson):21963283741は、PDP-10上で整数としても浮動小数点数としても表現したときに、2つの表現のビットパターンが同一になる唯一の数である。

項目176(Gosper):「バナナ現象」は、文字列を処理する際に遭遇した。すなわち、最後にタイプされた3文字を取り、そのシーケンスがテキスト中にランダムに出現する箇所を探し、その出現の次の文字を取り、それをタイプして反復する、という処理である。これによって出力される4文字の文字列はすべて元のテキスト中に出現することが保証される。このプログラムはBANANANANANANANA...とタイプした。ここで「N番目の出現」という言い回しに曖昧さがあることに注意したい。ある意味では0000000000の中に00は5個あり、別の意味では9個ある。エディタプログラムTECOは5個を見つける。したがってBANANAの中の最初のANAしか見つけず、次にNをタイプせざるを得ない。マーフィーの法則により、NANはただ1つしかないので、Aが強制され、ループになる。重なり合う出現を見つけるオプションは有用であろうが、次のN文字の文字列を探す前にN− 1文字戻る必要があるだろう。

注:この最後の項目はDissociated Pressの実装を指している。banana problemも参照。

HAKMEMにはもっと複雑な数学的・技術的項目も含まれているが、これらの例はその楽しい風味の一端を示している。

文書全体のHTML版がhttp://www.inwap.com/pdp10/hbaker/hakmem/hakmem.htmlで入手できる。