20/01/20 20:29:12.21 rHEqf9mL.net
カーネル内でチューリングマシンを実行するとき GPGPUでの実行なので、
テープを大きな配列で表わしてヘッドの位置を添え字で指定する方法は( *コアレスアクセス* にならないので)使えないので
長さ256ビットの2記号のテープを32ビット整数8つで表わし、
8回の短いループだけで1ビットを読み出し (こうすればGPUの演算機のグループは揃ったメモリアクセスをしてくれる)
状態遷移後も同様のループで1ビットを書き出す
Wikipediaのビジービーバー関数の記事にはこの答えとなるルール表が載っているが、
このプログラムの実行結果で最初に表示されるものが正しいかどうかの記事との比較のときは
状態とルールの並び順をそのままに比較しても一致しているとは限らない
記事でのルール表の状態の番号が違うだけの同型の結果を最初に表示している可能性があることに注意
自分のPCでこのプログラムを実行した結果
25600000000通り ( 256億通り ) のルール表が存在するが、
10～20分程度で実行完了して正解のルール表に一致していた
ビジービーバー関数は本来、プログラム等で指定した状態数記号数のものの 最大シフト数を求めたりはできないが、
( 全てのルール表について、そのルールだと無限ループする場合、そうなることの証明が必要 、
有限ステップをシミュレートしただけでは その先残りの有限ステップ実行すれば停止するのか、
それともそのまま無限ループするかの判定はできない )
今回は最大シフト数から逆にルール表をみつける問題なのでコンピュータで探索することができた
GPGPUではなく、CPUでマルチコアを利用して解いた場合、上記のスペックだとどれくらいの時間がかかるかの確認が必要
そのためにはCPUでの実行に特化したコードを新たに書く必要がある