🛠️
チューリングマシンを作ったはなし
(2020年8月ころのはなし) チューリングマシンのテープ部分を、ESP32と24ビットカラーLED WS2812Bのテープで作ったはなし。
※ 写真や動画はそのうち掲載します。
光るテープ
計算機屋さんなら誰でも一度は、チューリングマシンの実物をみてみたい、できれば作ってみたい、と思うに決まっている (いや決まってない)。
計算機科学のテキストを飛び出した、リアルワールドの、つまり実物のチューリングマシンは、Youtubeを検索してみると、みなさん実にいろいろな方法で作っている。
わしのお気に入りは https://youtu.be/E3keLeMwfHY だ。35mmフィルム様のシートに、X-Yプロッタのごとく (X軸方向はフィルムの駆動だからYプロッタだ) ペンで『0』『1』を描いたりホワイトボードクリーナみたいなもので消して、読み取りはカメラで認識している。バカだ(笑)。
あとLEGOで作ってみているもの https://youtu.be/cYw2ewoO6c4 とか、いま探し出せないが巨大なメカを壁一面に組んでいるのもみた覚えがある。
まあここまでネタとして確立してしまっているので、やっぱり何らかの新しい、バエる方式で作ってみたい。
で、いろいろ考えたのだが、テープに状態を書き込んだら光る、というのはどうだろう。
さいわい、WS2812Bという24ビットカラーLEDを以前、工作で使ってみたことがある。こいつは、2本の電源線と1本のシリアル信号線のみ （つまりLED間は3本の線だけの直列つなぎ、いわゆるデイジーチェーン接続) で、1000個くらいまでのLEDをRGB24ビットカラーで光らせることができる、というものである。
1LEDあたり24ビットのRGB輝度を次々送り、そのまま次の24ビットを送るとデイジーチェーンされた下流のLEDに流れる。一定時間信号をホールドするといわゆるストップビットとなり、いまシフトレジスタにある24ビットが自分の色・輝度として使われる。LEDの明るさ制御は各々のLEDに内蔵されたマイコン(?)でPWMで行なわれているので、送る側は気にしなくて良い、という優れものである。
1000個くらい、というのに別に根拠はなく、シリアル信号が800KHzなので、24ビットを送ると1LEDあたり約 (1/30K) 秒、30fpsくらいで各LEDをコントロールするには1000個くらいが限界、ということだろう。またLEDそのものも高輝度でmax 50mAくらいは平気で喰ってしまうので、1000個も接続したら5V 50Aの電源が必要ということになる。
WS2812Bの電源と信号レベル
すべてのLEDを最大輝度
ただし、ESP32の5V DC出力はやめたほうがいい。
あと電源は要5Vだが、信号は3.3VでもOK (つまりESP32などでもレベルコンバータ不要) だ。
製品としては、WS2812Bが50個くらいクリスマス電球状にワイヤでつながったもの、テープ状につながったものや、フレキシブルな2次元パネルにXY方向に16 x 16個とか並んだもの (ただしジグザグに配置されているので、Y偶数列と奇数列ではXの方向が逆転する) とかがある。
今回目をつけたのはこのうち、フレキシブルなテープで144個デイジーチェーン接続され、防水のため (IP67防水) 外側にシリコンチューブがかかっている1mくらいのテープである (つまりLEDのピッチは7mm程度)。
さいしょは真面目に、チューリングマシンで書き込んだ位置を検出して、その位置のLEDを適切な色・明るさで光らせれば……と思っていたが、考えてみれば逆でも構わない。つまりマイコン制御のこのテープ自体をチューリングマシンとして光らせ、ヘッド位置が定位置に来るようにテープを左右に駆動する簡単な機構に司令を出せば、実に簡単にできる。
というわけで、まずはテープ部分、『チューリングテープ』から作ってみることにした。
デモ発光
制御にはESP32を使う。こいつはWiFi・BlueToothなど備えているので、BlueToothからのシリアルターミナルで受信すれば、チューリングマシン本体へ・からの命令でテープを動かすことができるはずだ。
ハードウェアはめっちゃ簡単なので省略 （いっとくがこの項終わりまで同じハードウェアで、GPIOの一本の出力をWS2812Bテープの最初の入力に1本接続しただけなので、はんだ付けしても10分で終わる)。
デバッグというかデモとしてまず、Bluetooth terminalでコマンドを送れば、任意の位置のLEDをある色 (#553311 とかね) で光るようにしてみた。まあこれはほとんど、WS2812Bのライブラリそのものの『Lチカ』みたいなものである。ESP32はArduinoでプログラミングするので、WS2812BのライブラリはFastLEDというライブラリを使った。
次に行なったのが、Wolframの1次元ライフゲームと、ソリトンの実装である。
Wolframの1次元ライフゲームは、あるセルとその両側の3個のセルの現在状態によって次のセルの状態が決定する。
1次元ライフゲーム
有名な2次元のConwayのライフゲームでは、8近傍のセルの生の個数によって『0〜1は過疎で死滅、2・3は維持か生成、4〜8は過密で死滅』などと定義されているが、1次元ライフゲームではルールが0から255の整数で与えられる。つまり左・そのセル・右の３個のセルの 00000000〜11111111の255のルールができる。
ルール90なんてのは結構面白くて、いや面白いというのはやっぱり1次元といいながら、時点ごとに縦にならべて2時限としてみると、なんかフラクタル模様みたいなのを描くから面白い。
これをWS2812Bのテープで1次元のまま、時間変化として表示してみたい。
どうせなら生成するときは青点滅、生きているセルは白、死滅するときは赤点滅、などとアニメーション化してみる。
ソリトンは単純に、ランダムな速度のランダムな長さのランダムな色のミミズみたいなのが、テープを動き終端で反射する、というものだが、これもミミズみたいなものが重なったら色と輝度の合成としてみると、なかなかきれいなものである。
LEDの駆動はダブルバッファリングとして、タイマ割り込みによるアニメーションが可能なようにした。(後のチューリングテープで使うこともあり) あるポジションの最終的なRGBカラーと遷移に要する時間を指定すると、現在のRGBカラーからクロスフェードして変化するようにする (時間0で遷移させた場合は単純な書き込みとなる)。
Bluetooth terminalのコマンドでは、単純なオンオフだけではなく、これら (後に完成するチューリングテープも含め) のデモを指定して実行したり、ランダムに一定時間実行して次のデモを実行する、などの機能も追加した。
いざチューリングテープへ
チューリングテープをWS2812Bでつくると、セルが取りうる状態によっていろいろな色を割り当てることができるので、表現が楽である。
さて、チューリングマシンをエミュレートするプログラム (turing tapeと呼ぶ) は、BT terminalから指定して複数のものを汎用で実行できるようにしたい。それ自体は簡単だ。だが、チューリングマシンそのもののプログラミング (ってか状態遷移を考える) が結構、問題である。
busy beaver
すなわち最小限のルールで最大ステップを稼ぎ停止する、みたいなのは割と、表を書けば簡単にできる。
だけど、計算機科学の教科書にあるような、1進数の足し引き掛け割り算も書いてみたい。ついでにユークリッドの互除法ができれば (algorithmという言葉はユークリッドの互除法を指したそうである)、「ああこれ計算機なんだなあ(笑)」と実感できるだろう (バカ)。
turing tapeは、C言語のヘッダとして配列の要素として状態遷移を与える。配列の要素は『現在の状態(番号)・現在のヘッド位置のシンボル→次に書き込むヘッド位置のシンボル・動く方向・次の状態 (番号)』という5つ組の整数で与えている。割り算くらい状態数が多くなると、状態遷移図を描いてみて→turing tapeの配列に値として落とし込み→実行してみてデバッグする、というのが結構、面倒くさい。
そこでまず、Pythonでチューリングマシンのエミュレータ、兼コンパイラを書いた。Pythonの配列として状態名←→シンボル・左右・次の状態名を書いてやれば、エミュレートしてくれる。ついでにturing tapeに与えるデータ配列として、C言語のヘッダファイルの形に翻訳するようにした。
動く、動くぞw
Pythonエミュレータによる、8と6の最大公約数の例 （超長いよ）
% python3 tm.py eucrid 8 6
step 0:
_11111111_111111____________________________________________
^iniskipb=>_/R/iniskipb
step 1:
_11111111_111111____________________________________________
^iniskipb=>1/R/skipm
step 2:
_11111111_111111____________________________________________
^skipm=>1/R/skipm
step 3:
_11111111_111111____________________________________________
^skipm=>1/R/skipm
step 4:
_11111111_111111____________________________________________
^skipm=>1/R/skipm
step 5:
_11111111_111111____________________________________________
^skipm=>1/R/skipm
step 6:
_11111111_111111____________________________________________
^skipm=>1/R/skipm
step 7:
_11111111_111111____________________________________________
^skipm=>1/R/skipm
step 8:
_11111111_111111____________________________________________
^skipm=>1/R/skipm
step 9:
_11111111_111111____________________________________________
^skipm=>_/R/findn
step 10:
_11111111_111111____________________________________________
^findn=>2/R/chknend
step 11:
_11111111_211111____________________________________________
^chknend=>1/L/noebackn
step 12:
_11111111_211111____________________________________________
^noebackn=>2/L/noebackn
step 13:
_11111111_211111____________________________________________
^noebackn=>_/L/noebackm
step 14:
_11111111_211111____________________________________________
^noebackm=>1/L/noebackm
step 15:
_11111111_211111____________________________________________
^noebackm=>1/L/noebackm
step 16:
_11111111_211111____________________________________________
^noebackm=>1/L/noebackm
step 17:
_11111111_211111____________________________________________
^noebackm=>1/L/noebackm
step 18:
_11111111_211111____________________________________________
^noebackm=>1/L/noebackm
step 19:
_11111111_211111____________________________________________
^noebackm=>1/L/noebackm
step 20:
_11111111_211111____________________________________________
^noebackm=>1/L/noebackm
step 21:
_11111111_211111____________________________________________
^noebackm=>1/L/noebackm
step 22:
_11111111_211111____________________________________________
^noebackm=>_/R/wrmak
step 23:
_11111111_211111____________________________________________
^wrmak=>2/R/skipm
step 24:
_21111111_211111____________________________________________
^skipm=>1/R/skipm
step 25:
_21111111_211111____________________________________________
^skipm=>1/R/skipm
step 26:
_21111111_211111____________________________________________
^skipm=>1/R/skipm
step 27:
_21111111_211111____________________________________________
^skipm=>1/R/skipm
step 28:
_21111111_211111____________________________________________
^skipm=>1/R/skipm
step 29:
_21111111_211111____________________________________________
^skipm=>1/R/skipm
step 30:
_21111111_211111____________________________________________
^skipm=>1/R/skipm
step 31:
_21111111_211111____________________________________________
^skipm=>_/R/findn
step 32:
_21111111_211111____________________________________________
^findn=>2/R/findn
step 33:
_21111111_211111____________________________________________
^findn=>2/R/chknend
step 34:
_21111111_221111____________________________________________
^chknend=>1/L/noebackn
step 35:
_21111111_221111____________________________________________
^noebackn=>2/L/noebackn
step 36:
_21111111_221111____________________________________________
^noebackn=>2/L/noebackn
step 37:
_21111111_221111____________________________________________
^noebackn=>_/L/noebackm
step 38:
_21111111_221111____________________________________________
^noebackm=>1/L/noebackm
step 39:
_21111111_221111____________________________________________
^noebackm=>1/L/noebackm
step 40:
_21111111_221111____________________________________________
^noebackm=>1/L/noebackm
step 41:
_21111111_221111____________________________________________
^noebackm=>1/L/noebackm
step 42:
_21111111_221111____________________________________________
^noebackm=>1/L/noebackm
step 43:
_21111111_221111____________________________________________
^noebackm=>1/L/noebackm
step 44:
_21111111_221111____________________________________________
^noebackm=>1/L/noebackm
step 45:
_21111111_221111____________________________________________
^noebackm=>2/R/wrmak
step 46:
_21111111_221111____________________________________________
^wrmak=>2/R/skipm
step 47:
_22111111_221111____________________________________________
^skipm=>1/R/skipm
step 48:
_22111111_221111____________________________________________
^skipm=>1/R/skipm
step 49:
_22111111_221111____________________________________________
^skipm=>1/R/skipm
step 50:
_22111111_221111____________________________________________
^skipm=>1/R/skipm
step 51:
_22111111_221111____________________________________________
^skipm=>1/R/skipm
step 52:
_22111111_221111____________________________________________
^skipm=>1/R/skipm
step 53:
_22111111_221111____________________________________________
^skipm=>_/R/findn
step 54:
_22111111_221111____________________________________________
^findn=>2/R/findn
step 55:
_22111111_221111____________________________________________
^findn=>2/R/findn
step 56:
_22111111_221111____________________________________________
^findn=>2/R/chknend
step 57:
_22111111_222111____________________________________________
^chknend=>1/L/noebackn
step 58:
_22111111_222111____________________________________________
^noebackn=>2/L/noebackn
step 59:
_22111111_222111____________________________________________
^noebackn=>2/L/noebackn
step 60:
_22111111_222111____________________________________________
^noebackn=>2/L/noebackn
step 61:
_22111111_222111____________________________________________
^noebackn=>_/L/noebackm
step 62:
_22111111_222111____________________________________________
^noebackm=>1/L/noebackm
step 63:
_22111111_222111____________________________________________
^noebackm=>1/L/noebackm
step 64:
_22111111_222111____________________________________________
^noebackm=>1/L/noebackm
step 65:
_22111111_222111____________________________________________
^noebackm=>1/L/noebackm
step 66:
_22111111_222111____________________________________________
^noebackm=>1/L/noebackm
step 67:
_22111111_222111____________________________________________
^noebackm=>1/L/noebackm
step 68:
_22111111_222111____________________________________________
^noebackm=>2/R/wrmak
step 69:
_22111111_222111____________________________________________
^wrmak=>2/R/skipm
step 70:
_22211111_222111____________________________________________
^skipm=>1/R/skipm
step 71:
_22211111_222111____________________________________________
^skipm=>1/R/skipm
step 72:
_22211111_222111____________________________________________
^skipm=>1/R/skipm
step 73:
_22211111_222111____________________________________________
^skipm=>1/R/skipm
step 74:
_22211111_222111____________________________________________
^skipm=>1/R/skipm
step 75:
_22211111_222111____________________________________________
^skipm=>_/R/findn
step 76:
_22211111_222111____________________________________________
^findn=>2/R/findn
step 77:
_22211111_222111____________________________________________
^findn=>2/R/findn
step 78:
_22211111_222111____________________________________________
^findn=>2/R/findn
step 79:
_22211111_222111____________________________________________
^findn=>2/R/chknend
step 80:
_22211111_222211____________________________________________
^chknend=>1/L/noebackn
step 81:
_22211111_222211____________________________________________
^noebackn=>2/L/noebackn
step 82:
_22211111_222211____________________________________________
^noebackn=>2/L/noebackn
step 83:
_22211111_222211____________________________________________
^noebackn=>2/L/noebackn
step 84:
_22211111_222211____________________________________________
^noebackn=>2/L/noebackn
step 85:
_22211111_222211____________________________________________
^noebackn=>_/L/noebackm
step 86:
_22211111_222211____________________________________________
^noebackm=>1/L/noebackm
step 87:
_22211111_222211____________________________________________
^noebackm=>1/L/noebackm
step 88:
_22211111_222211____________________________________________
^noebackm=>1/L/noebackm
step 89:
_22211111_222211____________________________________________
^noebackm=>1/L/noebackm
step 90:
_22211111_222211____________________________________________
^noebackm=>1/L/noebackm
step 91:
_22211111_222211____________________________________________
^noebackm=>2/R/wrmak
step 92:
_22211111_222211____________________________________________
^wrmak=>2/R/skipm
step 93:
_22221111_222211____________________________________________
^skipm=>1/R/skipm
step 94:
_22221111_222211____________________________________________
^skipm=>1/R/skipm
step 95:
_22221111_222211____________________________________________
^skipm=>1/R/skipm
step 96:
_22221111_222211____________________________________________
^skipm=>1/R/skipm
step 97:
_22221111_222211____________________________________________
^skipm=>_/R/findn
step 98:
_22221111_222211____________________________________________
^findn=>2/R/findn
step 99:
_22221111_222211____________________________________________
^findn=>2/R/findn
step 100:
_22221111_222211____________________________________________
^findn=>2/R/findn
step 101:
_22221111_222211____________________________________________
^findn=>2/R/findn
step 102:
_22221111_222211____________________________________________
^findn=>2/R/chknend
step 103:
_22221111_222221____________________________________________
^chknend=>1/L/noebackn
step 104:
_22221111_222221____________________________________________
^noebackn=>2/L/noebackn
step 105:
_22221111_222221____________________________________________
^noebackn=>2/L/noebackn
step 106:
_22221111_222221____________________________________________
^noebackn=>2/L/noebackn
step 107:
_22221111_222221____________________________________________
^noebackn=>2/L/noebackn
step 108:
_22221111_222221____________________________________________
^noebackn=>2/L/noebackn
step 109:
_22221111_222221____________________________________________
^noebackn=>_/L/noebackm
step 110:
_22221111_222221____________________________________________
^noebackm=>1/L/noebackm
step 111:
_22221111_222221____________________________________________
^noebackm=>1/L/noebackm
step 112:
_22221111_222221____________________________________________
^noebackm=>1/L/noebackm
step 113:
_22221111_222221____________________________________________
^noebackm=>1/L/noebackm
step 114:
_22221111_222221____________________________________________
^noebackm=>2/R/wrmak
step 115:
_22221111_222221____________________________________________
^wrmak=>2/R/skipm
step 116:
_22222111_222221____________________________________________
^skipm=>1/R/skipm
step 117:
_22222111_222221____________________________________________
^skipm=>1/R/skipm
step 118:
_22222111_222221____________________________________________
^skipm=>1/R/skipm
step 119:
_22222111_222221____________________________________________
^skipm=>_/R/findn
step 120:
_22222111_222221____________________________________________
^findn=>2/R/findn
step 121:
_22222111_222221____________________________________________
^findn=>2/R/findn
step 122:
_22222111_222221____________________________________________
^findn=>2/R/findn
step 123:
_22222111_222221____________________________________________
^findn=>2/R/findn
step 124:
_22222111_222221____________________________________________
^findn=>2/R/findn
step 125:
_22222111_222221____________________________________________
^findn=>2/R/chknend
step 126:
_22222111_222222____________________________________________
^chknend=>_/L/endbackn
step 127:
_22222111_222222____________________________________________
^endbackn=>1/L/endbackn
step 128:
_22222111_222221____________________________________________
^endbackn=>1/L/endbackn
step 129:
_22222111_222211____________________________________________
^endbackn=>1/L/endbackn
step 130:
_22222111_222111____________________________________________
^endbackn=>1/L/endbackn
step 131:
_22222111_221111____________________________________________
^endbackn=>1/L/endbackn
step 132:
_22222111_211111____________________________________________
^endbackn=>1/L/endbackn
step 133:
_22222111_111111____________________________________________
^endbackn=>_/L/endbackm
step 134:
_22222111_111111____________________________________________
^endbackm=>1/L/endbackm
step 135:
_22222111_111111____________________________________________
^endbackm=>1/L/endbackm
step 136:
_22222111_111111____________________________________________
^endbackm=>1/L/endbackm
step 137:
_22222111_111111____________________________________________
^endbackm=>2/R/wrsep
step 138:
_22222111_111111____________________________________________
^wrsep=>3/R/chkend
step 139:
_22222311_111111____________________________________________
^chkend=>1/R/skipm
step 140:
_22222311_111111____________________________________________
^skipm=>1/R/skipm
step 141:
_22222311_111111____________________________________________
^skipm=>_/R/findn
step 142:
_22222311_111111____________________________________________
^findn=>2/R/chknend
step 143:
_22222311_211111____________________________________________
^chknend=>1/L/noebackn
step 144:
_22222311_211111____________________________________________
^noebackn=>2/L/noebackn
step 145:
_22222311_211111____________________________________________
^noebackn=>_/L/noebackm
step 146:
_22222311_211111____________________________________________
^noebackm=>1/L/noebackm
step 147:
_22222311_211111____________________________________________
^noebackm=>1/L/noebackm
step 148:
_22222311_211111____________________________________________
^noebackm=>3/R/wrmak
step 149:
_22222311_211111____________________________________________
^wrmak=>2/R/skipm
step 150:
_22222321_211111____________________________________________
^skipm=>1/R/skipm
step 151:
_22222321_211111____________________________________________
^skipm=>_/R/findn
step 152:
_22222321_211111____________________________________________
^findn=>2/R/findn
step 153:
_22222321_211111____________________________________________
^findn=>2/R/chknend
step 154:
_22222321_221111____________________________________________
^chknend=>1/L/noebackn
step 155:
_22222321_221111____________________________________________
^noebackn=>2/L/noebackn
step 156:
_22222321_221111____________________________________________
^noebackn=>2/L/noebackn
step 157:
_22222321_221111____________________________________________
^noebackn=>_/L/noebackm
step 158:
_22222321_221111____________________________________________
^noebackm=>1/L/noebackm
step 159:
_22222321_221111____________________________________________
^noebackm=>2/R/wrmak
step 160:
_22222321_221111____________________________________________
^wrmak=>2/R/skipm
step 161:
_22222322_221111____________________________________________
^skipm=>_/R/findn
step 162:
_22222322_221111____________________________________________
^findn=>2/R/findn
step 163:
_22222322_221111____________________________________________
^findn=>2/R/findn
step 164:
_22222322_221111____________________________________________
^findn=>2/R/chknend
step 165:
_22222322_222111____________________________________________
^chknend=>1/L/noebackn
step 166:
_22222322_222111____________________________________________
^noebackn=>2/L/noebackn
step 167:
_22222322_222111____________________________________________
^noebackn=>2/L/noebackn
step 168:
_22222322_222111____________________________________________
^noebackn=>2/L/noebackn
step 169:
_22222322_222111____________________________________________
^noebackn=>_/L/noebackm
step 170:
_22222322_222111____________________________________________
^noebackm=>2/R/wrmak
step 171:
_22222322_222111____________________________________________
^wrmak=>_/L/copyrbfind
step 172:
_22222322_222111____________________________________________
^copyrbfind=>2/L/copyrbfind
step 173:
_22222322_222111____________________________________________
^copyrbfind=>2/L/copyrbfind
step 174:
_22222322_222111____________________________________________
^copyrbfind=>3/R/copyrcopy
step 175:
_22222322_222111____________________________________________
^copyrcopy=>4/R/copyrskipm
step 176:
_22222342_222111____________________________________________
^copyrskipm=>2/R/copyrskipm
step 177:
_22222342_222111____________________________________________
^copyrskipm=>_/R/copyrskipn
step 178:
_22222342_222111____________________________________________
^copyrskipn=>1/R/copyrskipn
step 179:
_22222342_122111____________________________________________
^copyrskipn=>1/R/copyrskipn
step 180:
_22222342_112111____________________________________________
^copyrskipn=>1/R/copyrskipn
step 181:
_22222342_111111____________________________________________
^copyrskipn=>1/R/copyrskipn
step 182:
_22222342_111111____________________________________________
^copyrskipn=>1/R/copyrskipn
step 183:
_22222342_111111____________________________________________
^copyrskipn=>1/R/copyrskipn
step 184:
_22222342_111111____________________________________________
^copyrskipn=>_/R/copyrskipr
step 185:
_22222342_111111____________________________________________
^copyrskipr=>1/L/copyrbskipr
step 186:
_22222342_111111_1__________________________________________
^copyrbskipr=>_/L/copyrbskipn
step 187:
_22222342_111111_1__________________________________________
^copyrbskipn=>1/L/copyrbskipn
step 188:
_22222342_111111_1__________________________________________
^copyrbskipn=>1/L/copyrbskipn
step 189:
_22222342_111111_1__________________________________________
^copyrbskipn=>1/L/copyrbskipn
step 190:
_22222342_111111_1__________________________________________
^copyrbskipn=>1/L/copyrbskipn
step 191:
_22222342_111111_1__________________________________________
^copyrbskipn=>1/L/copyrbskipn
step 192:
_22222342_111111_1__________________________________________
^copyrbskipn=>1/L/copyrbskipn
step 193:
_22222342_111111_1__________________________________________
^copyrbskipn=>_/L/copyrbfind
step 194:
_22222342_111111_1__________________________________________
^copyrbfind=>2/L/copyrbfind
step 195:
_22222342_111111_1__________________________________________
^copyrbfind=>4/R/copyrcopy
step 196:
_22222342_111111_1__________________________________________
^copyrcopy=>4/R/copyrskipm
step 197:
_22222344_111111_1__________________________________________
^copyrskipm=>_/R/copyrskipn
step 198:
_22222344_111111_1__________________________________________
^copyrskipn=>1/R/copyrskipn
step 199:
_22222344_111111_1__________________________________________
^copyrskipn=>1/R/copyrskipn
step 200:
_22222344_111111_1__________________________________________
^copyrskipn=>1/R/copyrskipn
step 201:
_22222344_111111_1__________________________________________
^copyrskipn=>1/R/copyrskipn
step 202:
_22222344_111111_1__________________________________________
^copyrskipn=>1/R/copyrskipn
step 203:
_22222344_111111_1__________________________________________
^copyrskipn=>1/R/copyrskipn
step 204:
_22222344_111111_1__________________________________________
^copyrskipn=>_/R/copyrskipr
step 205:
_22222344_111111_1__________________________________________
^copyrskipr=>1/R/copyrskipr
step 206:
_22222344_111111_1__________________________________________
^copyrskipr=>1/L/copyrbskipr
step 207:
_22222344_111111_11_________________________________________
^copyrbskipr=>1/L/copyrbskipr
step 208:
_22222344_111111_11_________________________________________
^copyrbskipr=>_/L/copyrbskipn
step 209:
_22222344_111111_11_________________________________________
^copyrbskipn=>1/L/copyrbskipn
step 210:
_22222344_111111_11_________________________________________
^copyrbskipn=>1/L/copyrbskipn
step 211:
_22222344_111111_11_________________________________________
^copyrbskipn=>1/L/copyrbskipn
step 212:
_22222344_111111_11_________________________________________
^copyrbskipn=>1/L/copyrbskipn
step 213:
_22222344_111111_11_________________________________________
^copyrbskipn=>1/L/copyrbskipn
step 214:
_22222344_111111_11_________________________________________
^copyrbskipn=>1/L/copyrbskipn
step 215:
_22222344_111111_11_________________________________________
^copyrbskipn=>_/L/copyrbfind
step 216:
_22222344_111111_11_________________________________________
^copyrbfind=>4/R/copyrcopy
step 217:
_22222344_111111_11_________________________________________
^copyrcopy=>_/R/skipm
step 218:
_22222344_111111_11_________________________________________
^skipm=>1/R/skipm
step 219:
_22222344_111111_11_________________________________________
^skipm=>1/R/skipm
step 220:
_22222344_111111_11_________________________________________
^skipm=>1/R/skipm
step 221:
_22222344_111111_11_________________________________________
^skipm=>1/R/skipm
step 222:
_22222344_111111_11_________________________________________
^skipm=>1/R/skipm
step 223:
_22222344_111111_11_________________________________________
^skipm=>1/R/skipm
step 224:
_22222344_111111_11_________________________________________
^skipm=>_/R/findn
step 225:
_22222344_111111_11_________________________________________
^findn=>2/R/chknend
step 226:
_22222344_111111_21_________________________________________
^chknend=>1/L/noebackn
step 227:
_22222344_111111_21_________________________________________
^noebackn=>2/L/noebackn
step 228:
_22222344_111111_21_________________________________________
^noebackn=>_/L/noebackm
step 229:
_22222344_111111_21_________________________________________
^noebackm=>1/L/noebackm
step 230:
_22222344_111111_21_________________________________________
^noebackm=>1/L/noebackm
step 231:
_22222344_111111_21_________________________________________
^noebackm=>1/L/noebackm
step 232:
_22222344_111111_21_________________________________________
^noebackm=>1/L/noebackm
step 233:
_22222344_111111_21_________________________________________
^noebackm=>1/L/noebackm
step 234:
_22222344_111111_21_________________________________________
^noebackm=>1/L/noebackm
step 235:
_22222344_111111_21_________________________________________
^noebackm=>_/R/wrmak
step 236:
_22222344_111111_21_________________________________________
^wrmak=>2/R/skipm
step 237:
_22222344_211111_21_________________________________________
^skipm=>1/R/skipm
step 238:
_22222344_211111_21_________________________________________
^skipm=>1/R/skipm
step 239:
_22222344_211111_21_________________________________________
^skipm=>1/R/skipm
step 240:
_22222344_211111_21_________________________________________
^skipm=>1/R/skipm
step 241:
_22222344_211111_21_________________________________________
^skipm=>1/R/skipm
step 242:
_22222344_211111_21_________________________________________
^skipm=>_/R/findn
step 243:
_22222344_211111_21_________________________________________
^findn=>2/R/findn
step 244:
_22222344_211111_21_________________________________________
^findn=>2/R/chknend
step 245:
_22222344_211111_22_________________________________________
^chknend=>_/L/endbackn
step 246:
_22222344_211111_22_________________________________________
^endbackn=>1/L/endbackn
step 247:
_22222344_211111_21_________________________________________
^endbackn=>1/L/endbackn
step 248:
_22222344_211111_11_________________________________________
^endbackn=>_/L/endbackm
step 249:
_22222344_211111_11_________________________________________
^endbackm=>1/L/endbackm
step 250:
_22222344_211111_11_________________________________________
^endbackm=>1/L/endbackm
step 251:
_22222344_211111_11_________________________________________
^endbackm=>1/L/endbackm
step 252:
_22222344_211111_11_________________________________________
^endbackm=>1/L/endbackm
step 253:
_22222344_211111_11_________________________________________
^endbackm=>1/L/endbackm
step 254:
_22222344_211111_11_________________________________________
^endbackm=>2/R/wrsep
step 255:
_22222344_211111_11_________________________________________
^wrsep=>3/R/chkend
step 256:
_22222344_231111_11_________________________________________
^chkend=>1/R/skipm
step 257:
_22222344_231111_11_________________________________________
^skipm=>1/R/skipm
step 258:
_22222344_231111_11_________________________________________
^skipm=>1/R/skipm
step 259:
_22222344_231111_11_________________________________________
^skipm=>1/R/skipm
step 260:
_22222344_231111_11_________________________________________
^skipm=>_/R/findn
step 261:
_22222344_231111_11_________________________________________
^findn=>2/R/chknend
step 262:
_22222344_231111_21_________________________________________
^chknend=>1/L/noebackn
step 263:
_22222344_231111_21_________________________________________
^noebackn=>2/L/noebackn
step 264:
_22222344_231111_21_________________________________________
^noebackn=>_/L/noebackm
step 265:
_22222344_231111_21_________________________________________
^noebackm=>1/L/noebackm
step 266:
_22222344_231111_21_________________________________________
^noebackm=>1/L/noebackm
step 267:
_22222344_231111_21_________________________________________
^noebackm=>1/L/noebackm
step 268:
_22222344_231111_21_________________________________________
^noebackm=>1/L/noebackm
step 269:
_22222344_231111_21_________________________________________
^noebackm=>3/R/wrmak
step 270:
_22222344_231111_21_________________________________________
^wrmak=>2/R/skipm
step 271:
_22222344_232111_21_________________________________________
^skipm=>1/R/skipm
step 272:
_22222344_232111_21_________________________________________
^skipm=>1/R/skipm
step 273:
_22222344_232111_21_________________________________________
^skipm=>1/R/skipm
step 274:
_22222344_232111_21_________________________________________
^skipm=>_/R/findn
step 275:
_22222344_232111_21_________________________________________
^findn=>2/R/findn
step 276:
_22222344_232111_21_________________________________________
^findn=>2/R/chknend
step 277:
_22222344_232111_22_________________________________________
^chknend=>_/L/endbackn
step 278:
_22222344_232111_22_________________________________________
^endbackn=>1/L/endbackn
step 279:
_22222344_232111_21_________________________________________
^endbackn=>1/L/endbackn
step 280:
_22222344_232111_11_________________________________________
^endbackn=>_/L/endbackm
step 281:
_22222344_232111_11_________________________________________
^endbackm=>1/L/endbackm
step 282:
_22222344_232111_11_________________________________________
^endbackm=>1/L/endbackm
step 283:
_22222344_232111_11_________________________________________
^endbackm=>1/L/endbackm
step 284:
_22222344_232111_11_________________________________________
^endbackm=>2/R/wrsep
step 285:
_22222344_232111_11_________________________________________
^wrsep=>3/R/chkend
step 286:
_22222344_232311_11_________________________________________
^chkend=>1/R/skipm
step 287:
_22222344_232311_11_________________________________________
^skipm=>1/R/skipm
step 288:
_22222344_232311_11_________________________________________
^skipm=>_/R/findn
step 289:
_22222344_232311_11_________________________________________
^findn=>2/R/chknend
step 290:
_22222344_232311_21_________________________________________
^chknend=>1/L/noebackn
step 291:
_22222344_232311_21_________________________________________
^noebackn=>2/L/noebackn
step 292:
_22222344_232311_21_________________________________________
^noebackn=>_/L/noebackm
step 293:
_22222344_232311_21_________________________________________
^noebackm=>1/L/noebackm
step 294:
_22222344_232311_21_________________________________________
^noebackm=>1/L/noebackm
step 295:
_22222344_232311_21_________________________________________
^noebackm=>3/R/wrmak
step 296:
_22222344_232311_21_________________________________________
^wrmak=>2/R/skipm
step 297:
_22222344_232321_21_________________________________________
^skipm=>1/R/skipm
step 298:
_22222344_232321_21_________________________________________
^skipm=>_/R/findn
step 299:
_22222344_232321_21_________________________________________
^findn=>2/R/findn
step 300:
_22222344_232321_21_________________________________________
^findn=>2/R/chknend
step 301:
_22222344_232321_22_________________________________________
^chknend=>_/L/endbackn
step 302:
_22222344_232321_22_________________________________________
^endbackn=>1/L/endbackn
step 303:
_22222344_232321_21_________________________________________
^endbackn=>1/L/endbackn
step 304:
_22222344_232321_11_________________________________________
^endbackn=>_/L/endbackm
step 305:
_22222344_232321_11_________________________________________
^endbackm=>1/L/endbackm
step 306:
_22222344_232321_11_________________________________________
^endbackm=>2/R/wrsep
step 307:
_22222344_232321_11_________________________________________
^wrsep=>3/R/chkend
step 308:
_22222344_232323_11_________________________________________
^chkend=>_/R/H
step 309:
_22222344_232323_11_________________________________________
^
end
(説明) シンボル1を2つの数だけ並べておく。step127まで割られる数『8』から割る数『6』で、引き算1回目を行なって、step139で割られる数の余りにあたる個数だけ (右から) 残して、シンボル3が立つ。step170で割られる数より余りが小さいことがわかるので、step217までで余り『2』を割る数の右にコピーする。
step218からは同様に、今度は先の割る数『6』を割られる数、先の余り『2』を割る数として動作開始。
step309まで3回の引き算を行なうが、いきなり余りが0であることがわかるので停止する。
一番右に並んだ1の個数『2』が、答である。
とまあ、出来上がったのがこれである:
ユークリッドの互除法は5シンボルで18状態、遷移パターンは40にも及んだ。とはいえ、割り算あたりを作っているうちにコツはだいたい掴めてきた。
(例) 3状態2記号のbusy beaver
turing tape上での実装 (これだけ読んでもなんのこっちゃ)
typedef struct {
int currstate;
byte currsym;
byte nextsym;
int dir;
int nextstate;
} turst_t;
turst_t tmbb32r[] = {
{0, 0, 1, 1, 1},
{0, 1, 1, 1, -1},
{1, 0, 1, -1, 1},
{1, 1, 0, 1, 2},
{2, 0, 1, -1, 2},
{2, 1, 1, -1, 0},
{-1, -1, -1, 0, -1}
};
この項続く
ここまでできちゃえばあと、メカ部分 （turing tapeを駆動するホイールと位置センサとか) は簡単だろう……と思って、パーツまで揃えたのだが、なんかそこで安心しちゃって製作がストップしている。
つか、こうやって光るturing tapeを眺めていると、それで満足しちゃったのだ(笑)。
なんといっても、繰り返しになるが、教科書に載っているような例題より難しめのユークリッドの互除法がプログラムできて、実際に最大公約数を求めることができると (加減乗除ユークリッドは、BT terminalからのコマンドの引数で数を指定できる)、「ああ計算機なんだな」と思う。バカ(笑)。
それにしてもこれ、本来本体であるはずの駆動メカに対して、本来書き込まれるメディアであるはずのturing tapeが命令を出す……という構造になったら、それはそれで面白い。
なんか、寄生虫が本体を操って寄生虫に有利な行動をするように仕向ける、というはなしをきいたことがあるが、それみたいだ。
まあいつの日か、ぜひ本体の駆動メカ部分も完成させたい。
Discussion