4状態2記号のビジービーバーマシンの最大シフト数 N が与えられたとき
( シフト数と状態数と記号数のみで、ルール表は教えてもらっていないとき )
4状態2記号のチューリングマシンを全て N ステップまで実行し
Nを越えたものは無限ループするチューリングマシンと確定するので
ちょうどNで停止するもののルール表をみつけるプログラム
 
4状態2記号での N は 107 なので2記号のテープを32ビット整数8つの256ビットで表わして
GPU上で全て試行する
( 256ビットの真ん中を初期位置にすることでどんなマシンを実行したとしても
107ステップ以内では範囲外に出ることが無い )
 
 
GPGPUにはOpenCLを使う
 
 
4状態2記号のルール表は
4つの各状態で0か1を読み取った場合の 4x2 の表に
次の状態が(停止状態を含めて)5通り
書き込む記号が2通り
ヘッドの移動する方向が2通り
 
なので (5x2x2) の 8乗 通りある
 
ルール表を表す変数の名前の規則は
aの後の1-8の数字が状態と読み取った記号の8通りの場合で
そのあとに n とつく ( a1n 等 ) ものは 次の状態を表し、
wd とつく ( a1wd 等 ) ものは 2ビットで書き込む記号と ヘッドの移動方向を表す
 
 
OpenCLのカーネルでは
CPUからGPUへのワークの発行1回で
ルール表の 4x2 の 3つの部分は ワーク内の全てのスレッドで固定して ( この3つは発行1回ごとにCPUで順に切り替える )
残りのうち3つは 1度に発行した 20の3乗 = 8000 個のスレッドのIDを
あらかじめ作っておいた 8000要素の配列の添え字で切り替えて
残りの2つの部分は 各スレッドで 20の2乗 回のループで切り替える
 
8000要素の配列はその前のワーク内全てで固定した部分をCPUでのループで書き換えてもそのまま使えるようになっている
 
 
カーネル内でチューリングマシンを実行するとき GPGPUでの実行なので、
テープを大きな配列で表わしてヘッドの位置を添え字で指定する方法は( *コアレスアクセス* にならないので)使えないので
長さ256ビットの2記号のテープを32ビット整数8つで表わし、
8回の短いループだけで1ビットを読み出し (こうすればGPUの演算機のグループは揃ったメモリアクセスをしてくれる)
状態遷移後も同様のループで1ビットを書き出す
 
 
Wikipediaのビジービーバー関数の記事にはこの答えとなるルール表が載っているが、
このプログラムの実行結果で最初に表示されるものが正しいかどうかの記事との比較のときは
状態とルールの並び順をそのままに比較しても一致しているとは限らない
記事でのルール表の状態の番号が違うだけの同型の結果を最初に表示している可能性があることに注意
 
 
自分のPCでこのプログラムを実行した結果
 
25600000000通り ( 256億通り ) のルール表が存在するが、
10～20分程度で実行完了して正解のルール表に一致していた
 
 
ビジービーバー関数は本来、プログラム等で指定した状態数記号数のものの 最大シフト数を求めたりはできないが、
( 全てのルール表について、そのルールだと無限ループする場合、そうなることの証明が必要 、
有限ステップをシミュレートしただけでは その先残りの有限ステップ実行すれば停止するのか、
それともそのまま無限ループするかの判定はできない )
今回は最大シフト数から逆にルール表をみつける問題なのでコンピュータで探索することができた
 
 
GPGPUではなく、CPUでマルチコアを利用して解いた場合、上記のスペックだとどれくらいの時間がかかるかの確認が必要
そのためにはCPUでの実行に特化したコードを新たに書く必要がある
 
 
P.S.
 
遅れてました

NOeKtuaFizLoqJjlj7fjga7jg5Pjgrjjg7zjg5Pjg7zjg5Djg7zjg57jgrfjg7Pjga7mnIDlpKfjgrfjg5Xjg4jmlbAgTiDjgYzkuI7jgYjjgonjgozjgZ/jgajjgY0KKCDjgrfjg5Xjg4jmlbDjgajnirbmhYvmlbDjgajoqJjlj7fmlbDjga7jgb/jgafjgIHjg6vjg7zjg6vooajjga/mlZnjgYjjgabjgoLjgonjgaPjgabjgYTjgarjgYTjgajjgY0gKQo054q25oWLMuiomOWPt+OBruODgeODpeODvOODquODs+OCsOODnuOCt+ODs+OCkuWFqOOBpiBOIOOCueODhuODg+ODl+OBvuOBp+Wun+ihjOOBlwpO44KS6LaK44GI44Gf44KC44Gu44Gv54Sh6ZmQ44Or44O844OX44GZ44KL44OB44Ol44O844Oq44Oz44Kw44Oe44K344Oz44Go56K65a6a44GZ44KL44Gu44GnCuOBoeOCh+OBhuOBqU7jgaflgZzmraLjgZnjgovjgoLjga7jga7jg6vjg7zjg6vooajjgpLjgb/jgaTjgZHjgovjg5fjg63jgrDjg6njg6AKCjTnirbmhYsy6KiY5Y+344Gn44GuIE4g44GvIDEwNyDjgarjga7jgacy6KiY5Y+344Gu44OG44O844OX44KSMzLjg5Pjg4Pjg4jmlbTmlbA444Gk44GuMjU244OT44OD44OI44Gn6KGo44KP44GX44GmCkdQVeS4iuOBp+WFqOOBpuippuihjOOBmeOCiwooIDI1NuODk+ODg+ODiOOBruecn+OCk+S4reOCkuWIneacn+S9jee9ruOBq+OBmeOCi+OBk+OBqOOBp+OBqeOCk+OBquODnuOCt+ODs+OCkuWun+ihjOOBl+OBn+OBqOOBl+OBpuOCggoxMDfjgrnjg4bjg4Pjg5fku6XlhoXjgafjga/nr4Tlm7LlpJbjgavlh7rjgovjgZPjgajjgYznhKHjgYQgKQoKCkdQR1BV44Gr44GvT3BlbkNM44KS5L2/44GGCgoKNOeKtuaFizLoqJjlj7fjga7jg6vjg7zjg6vooajjga8KNOOBpOOBruWQhOeKtuaFi+OBpzDjgYsx44KS6Kqt44G/5Y+W44Gj44Gf5aC05ZCI44GuIDR4MiDjga7ooajjgasK5qyh44Gu54q25oWL44GMKOWBnOatoueKtuaFi+OCkuWQq+OCgeOBpik16YCa44KKCuabuOOBjei+vOOCgOiomOWPt+OBjDLpgJrjgooK44OY44OD44OJ44Gu56e75YuV44GZ44KL5pa55ZCR44GMMumAmuOCigoK44Gq44Gu44GnICg1eDJ4Mikg44GuIDjkuZcg6YCa44KK44GC44KLCgrjg6vjg7zjg6vooajjgpLooajjgZnlpInmlbDjga7lkI3liY3jga7opo/liYfjga8KYeOBruW+jOOBrjEtOOOBruaVsOWtl+OBjOeKtuaFi+OBqOiqreOBv+WPluOBo+OBn+iomOWPt+OBrjjpgJrjgorjga7loLTlkIjjgacK44Gd44Gu44GC44Go44GrIG4g44Go44Gk44GPICggYTFuIOetiSApIOOCguOBruOBryDmrKHjga7nirbmhYvjgpLooajjgZfjgIEKd2Qg44Go44Gk44GPICggYTF3ZCDnrYkgKSDjgoLjga7jga8gMuODk+ODg+ODiOOBp+abuOOBjei+vOOCgOiomOWPt+OBqCDjg5jjg4Pjg4njga7np7vli5XmlrnlkJHjgpLooajjgZkKCgpPcGVuQ0zjga7jgqvjg7zjg43jg6vjgafjga8KQ1BV44GL44KJR1BV44G444Gu44Ov44O844Kv44Gu55m66KGMMeWbnuOBpwrjg6vjg7zjg6vooajjga4gNHgyIOOBriAz44Gk44Gu6YOo5YiG44GvIOODr+ODvOOCr+WGheOBruWFqOOBpuOBruOCueODrOODg+ODieOBp+WbuuWumuOBl+OBpiAoIOOBk+OBrjPjgaTjga/nmbrooYwx5Zue44GU44Go44GrQ1BV44Gn6aCG44Gr5YiH44KK5pu/44GI44KLICkK5q6L44KK44Gu44GG44GhM+OBpOOBryAx5bqm44Gr55m66KGM44GX44GfIDIw44GuM+S5lyA9IDgwMDAg5YCL44Gu44K544Os44OD44OJ44GuSUTjgpIK44GC44KJ44GL44GY44KB5L2c44Gj44Gm44GK44GE44GfIDgwMDDopoHntKDjga7phY3liJfjga7mt7vjgYjlrZfjgafliIfjgormm7/jgYjjgaYK5q6L44KK44GuMuOBpOOBrumDqOWIhuOBryDlkITjgrnjg6zjg4Pjg4njgacgMjDjga4y5LmXIOWbnuOBruODq+ODvOODl+OBp+WIh+OCiuabv+OBiOOCiwoKODAwMOimgee0oOOBrumFjeWIl+OBr+OBneOBruWJjeOBruODr+ODvOOCr+WGheWFqOOBpuOBp+WbuuWumuOBl+OBn+mDqOWIhuOCkkNQVeOBp+OBruODq+ODvOODl+OBp+abuOOBjeaPm+OBiOOBpuOCguOBneOBruOBvuOBvuS9v+OBiOOCi+OCiOOBhuOBq+OBquOBo+OBpuOBhOOCiwoKCuOCq+ODvOODjeODq+WGheOBp+ODgeODpeODvOODquODs+OCsOODnuOCt+ODs+OCkuWun+ihjOOBmeOCi+OBqOOBjSBHUEdQVeOBp+OBruWun+ihjOOBquOBruOBp+OAgQrjg4bjg7zjg5fjgpLlpKfjgY3jgarphY3liJfjgafooajjgo/jgZfjgabjg5jjg4Pjg4njga7kvY3nva7jgpLmt7vjgYjlrZfjgafmjIflrprjgZnjgovmlrnms5Xjga8oICrjgrPjgqLjg6zjgrnjgqLjgq/jgrvjgrkqIOOBq+OBquOCieOBquOBhOOBruOBpynkvb/jgYjjgarjgYTjga7jgacK6ZW344GVMjU244OT44OD44OI44GuMuiomOWPt+OBruODhuODvOODl+OCkjMy44OT44OD44OI5pW05pWwOOOBpOOBp+ihqOOCj+OBl+OAgQo45Zue44Gu55+t44GE44Or44O844OX44Gg44GR44GnMeODk+ODg+ODiOOCkuiqreOBv+WHuuOBlyAo44GT44GG44GZ44KM44GwR1BV44Gu5ryU566X5qmf44Gu44Kw44Or44O844OX44Gv5o+D44Gj44Gf44Oh44Oi44Oq44Ki44Kv44K744K544KS44GX44Gm44GP44KM44KLKQrnirbmhYvpgbfnp7vlvozjgoLlkIzmp5jjga7jg6vjg7zjg5fjgacx44OT44OD44OI44KS5pu444GN5Ye644GZCgoKV2lraXBlZGlh44Gu44OT44K444O844OT44O844OQ44O86Zai5pWw44Gu6KiY5LqL44Gr44Gv44GT44Gu562U44GI44Go44Gq44KL44Or44O844Or6KGo44GM6LyJ44Gj44Gm44GE44KL44GM44CBCuOBk+OBruODl+ODreOCsOODqeODoOOBruWun+ihjOe1kOaenOOBp+acgOWIneOBq+ihqOekuuOBleOCjOOCi+OCguOBruOBjOato+OBl+OBhOOBi+OBqeOBhuOBi+OBruiomOS6i+OBqOOBruavlOi8g+OBruOBqOOBjeOBrwrnirbmhYvjgajjg6vjg7zjg6vjga7kuKbjgbPpoIbjgpLjgZ3jga7jgb7jgb7jgavmr5TovIPjgZfjgabjgoLkuIDoh7TjgZfjgabjgYTjgovjgajjga/pmZDjgonjgarjgYQK6KiY5LqL44Gn44Gu44Or44O844Or6KGo44Gu54q25oWL44Gu55Wq5Y+344GM6YGV44GG44Gg44GR44Gu5ZCM5Z6L44Gu57WQ5p6c44KS5pyA5Yid44Gr6KGo56S644GX44Gm44GE44KL5Y+v6IO95oCn44GM44GC44KL44GT44Go44Gr5rOo5oSPCgoK6Ieq5YiG44GuUEPjgafjgZPjga7jg5fjg63jgrDjg6njg6DjgpLlrp/ooYzjgZfjgZ/ntZDmnpwKCjI1NjAwMDAwMDAw6YCa44KKICggMjU25YSE6YCa44KKICkg44Gu44Or44O844Or6KGo44GM5a2Y5Zyo44GZ44KL44GM44CBCjEw772eMjDliIbnqIvluqbjgaflrp/ooYzlrozkuobjgZfjgabmraPop6Pjga7jg6vjg7zjg6vooajjgavkuIDoh7TjgZfjgabjgYTjgZ8KCgrjg5Pjgrjjg7zjg5Pjg7zjg5Djg7zplqLmlbDjga/mnKzmnaXjgIHjg5fjg63jgrDjg6njg6DnrYnjgafmjIflrprjgZfjgZ/nirbmhYvmlbDoqJjlj7fmlbDjga7jgoLjga7jga4g5pyA5aSn44K344OV44OI5pWw44KS5rGC44KB44Gf44KK44Gv44Gn44GN44Gq44GE44GM44CBCigg5YWo44Gm44Gu44Or44O844Or6KGo44Gr44Gk44GE44Gm44CB44Gd44Gu44Or44O844Or44Gg44Go54Sh6ZmQ44Or44O844OX44GZ44KL5aC05ZCI44CB44Gd44GG44Gq44KL44GT44Go44Gu6Ki85piO44GM5b+F6KaBIOOAgQrmnInpmZDjgrnjg4bjg4Pjg5fjgpLjgrfjg5/jg6Xjg6zjg7zjg4jjgZfjgZ/jgaDjgZHjgafjga8g44Gd44Gu5YWI5q6L44KK44Gu5pyJ6ZmQ44K544OG44OD44OX5a6f6KGM44GZ44KM44Gw5YGc5q2i44GZ44KL44Gu44GL44CBCuOBneOCjOOBqOOCguOBneOBruOBvuOBvueEoemZkOODq+ODvOODl+OBmeOCi+OBi+OBruWIpOWumuOBr+OBp+OBjeOBquOBhCApCuS7iuWbnuOBr+acgOWkp+OCt+ODleODiOaVsOOBi+OCiemAhuOBq+ODq+ODvOODq+ihqOOCkuOBv+OBpOOBkeOCi+WVj+mhjOOBquOBruOBp+OCs+ODs+ODlOODpeODvOOCv+OBp+aOoue0ouOBmeOCi+OBk+OBqOOBjOOBp+OBjeOBnwoKCkdQR1BV44Gn44Gv44Gq44GP44CBQ1BV44Gn44Oe44Or44OB44Kz44Ki44KS5Yip55So44GX44Gm6Kej44GE44Gf5aC05ZCI44CB5LiK6KiY44Gu44K544Oa44OD44Kv44Gg44Go44Gp44KM44GP44KJ44GE44Gu5pmC6ZaT44GM44GL44GL44KL44GL44Gu56K66KqN44GM5b+F6KaBCuOBneOBruOBn+OCgeOBq+OBr0NQVeOBp+OBruWun+ihjOOBq+eJueWMluOBl+OBn+OCs+ODvOODieOCkuaWsOOBn+OBq+abuOOBj+W/heimgeOBjOOBguOCiwoKClAuUy4KCumBheOCjOOBpuOBvuOBl+OBnw==