ミンスキー『計算機の数学的理論』


4000059416私が初めて計算機科学を学んだ『ファインマン計算機科学』では,ミンスキーの本に掲載されているチューリングマシンを使って計算の理論を解説していました。ファインマンは何でも自分で再発明してみるタイプだったそうなので(ファインマンさんの流儀),万能チューリングマシンも自分で構成したかもしれません。しかし,解説に使ったのはミンスキーのものでした。

われわれの議論は,ミンスキー[1967]の議論を念入りにたどっている。(p.56)

このミンスキー[1967]は Computation: Finite and Infinite Machines のことで,Amazonでは見つけにくいのですが『計算機の数学的理論』という翻訳があります。

4782800541ミンスキーと言えば『心の社会』が有名で,たとえば石田晴久先生は,『コンピュータの名著・古典100冊』新版あり)の中で次のように書かれています。

節の数は全部で262もある。(中略)この262節の中には修士論文や博士論文のタネがごろごろしているような感じがする。(p.81)

『計算機の数学的理論』にも,実は博士論文のタネが埋まっていて,私はかつて,それを拾って博士論文を書きました。(タネから芽が出たとは言いませんが。)

追悼:マーヴィン・ミンスキー。MIT人工知能研を設立したAI研究の先駆者

(インテルとAMDのCPUの)三角関数は不要


インテルとAMDのCPUには,三角関数を数値的に計算するための命令が備えられていますが,その結果は正しくありません。たとえば,CPUの命令FCOSの結果とstd::cosでソフトウェア的に計算した結果を比べると,後者の方が真の値に近くなります。

再現のためのコード(FCOSを使う部分だけインラインアセンブラを使っています。)

Core i5 6600とg++ 4.8.4で試した結果はこんな感じです。

x = 0.98233490762409514385
c1 = fcos(x)     = 0.55508189550073283591
c2 = std::cos(x) = 0.55508189550073294694
c  = mp::cos(x)  = 0.555081895500732891425063460345544265145531916268
abs(c - c1) = 5.5512e-17
abs(c - c2) = 5.551e-17

c1 is better: 0
c2 is better: 25
total: 100000

(その正しさをどうやって確かめるのかという問題はありますが)Boost.Multiprecisionで計算した結果と比較すると,命令`FCOS`より`std::cos`の方が正確なようです(Visual Studioの場合はまた違った結果になるようです)。

Pentiumが割り算を間違うといって大騒ぎになったことがありましたが(Pentium FDIV バグ),数値計算はどうせ近似値だからでしょうか,この問題は,ドキュメントに注意書きが追記されただけで,根本的な解決はされないままのようです。

おまけ:

結論:CUDAのcos,FCOS,gccのstd::cos(double)の順に正確になります。もちろん,gccのcos(long double), gccのcos(__float128), boost/multiprecisionは,さらに正確です。

JavaではMath.cosとStrictMath.cosがどっちもどっちだったり,数値計算は難しいです。

参考:サイン、コサインをインテルの CPU で計算すると少しバグっているらしい

HTMLとCSSだけで作るマルバツ


マルバツを題材にしたプログラミング入門書を紹介したときに,「自分ならどうするか」を考えると楽しいと書きました。

私の場合,HTML+CSS+JavaScriptで作ることを最初に考えますが,HTMLとCSSだけ,つまりJavaScriptなしというのも面白いですね。根性があれば,プログラミングは不要です。(CSSも本質的には不要ですが,見た目があまり貧弱だとイヤなので・・・)

COMは負けないマルバツ+αのつもりです。勝つ場合の手数は考慮していません。

Manifold JSで別のプラットフォーム用に変換できます。

1594746877Tic Tac Tome は,この記事でやっているのとと同じことを紙で試みているすごい本です(1ページ1局面,一部両面印刷で約700枚!)。残念なことに,先手が人で後手が最善の場合は網羅されているようですが,後手が人の場合は,先手が真ん中を選ぶケースしか扱っていないようです。つまり,上述の「COMが先手」のパターン1と2は扱われていません(上の実装なら,1ページ1局面,一部両面印刷で約230枚程度で足りるはずです)。

この本がマルバツを理解しているかというと,そういうわけではないと思いますが,そういうことを考えるのも楽しいものです。

参考:1人で「三目並べ」を遊ぶことができるゲームブック「Tic Tac Tome: The Autonomous Tic Tac Toe Playing Book」

フェルマーの最終定理の反「反例」(MPFR対応Gawk)


4904807154かつて、awk用のフェルマーの最終定理の「反例」を紹介したことがありましたが、最近のGawkでは「反例」にならないようです。

Ubuntu 16.04のGawkで試せます。

$ echo '5999856 99992800 100000000' | gawk '{print $1**3+$2**3-$3**3}'
0

$ echo '5999856 99992800 100000000' | gawk -M '{print $1**3+$2**3-$3**3}'
-2985984

Ubuntu 14.04の場合は準備が必要です。

下の方法では、管理者権限を使ってふつうにインストールしています。アンインストールする場合は、作業ディレクトリで「make uninstall」としてください。

sudo apt-get -y install texinfo libmpfr-dev libgmp-dev

git clone git://git.savannah.gnu.org/automake.git
cd automake-1.15
./configure && make && sudo make install
cd ..

git clone git://git.savannah.gnu.org/gawk.git
cd gawk
./configure && make && sudo make install
cd ..

参考:GNU AWKはまだまだ成長中! ユーザーの声をもとに作成された拡張機能を組み込んでみよう

白と黒のとびら


4130633570川添愛『白と黒のとびら: オートマトンと形式言語をめぐる冒険』(東京大学出版会, 2013)(参考文献リストあり・索引なし)

チョムスキー階層のすべてに対応するオートマトンを「扉を持った遺跡」に例えて組み込んだファンタジー。計算理論の基礎を学ぶのにはふつうの教科書の方がいいだろうが、ひと通り学んだ後なら楽しめるだろう。計算複雑性の理論など、進んだ話題を扱う続編に期待。

線形拘束オートマトン(ゼウ山の塔)への入力が、○と●という2つのボタンなのだが、塔はどうやって入力の終わりを認識しているのだろう。