Rule 110について（前編）
1次元セルオートマトンのRule 110がTuring完全と聞いて。
Tag system
そもそも，tag systemとは，文字列書き換え規則であって，「先頭P文字を消し，そのうちの1文字目にのみ依存して末尾に何文字か加える」ようなもの。これを繰り返して特別な文字が先頭に来たら停止。
さて，2-symbol Turing機械をP=2のtag systemで模倣するのだが，今回は計算可能性しか考えていないため指数爆発しても良い。具体的には，ヘッドの左右を2進法で読み（ヘッドに近い方が下の桁，十分遠くでは0が並んでいるので良い），その回数の文字列の繰り返しとして符号化する。
例：… 0 0 0 0 1 1 0 q 1 1 0 1 0 0 0 0 … ↦ Ax(ax)6Bx(bx)11 = AxaxaxaxaxaxaxBxbxbxbxbxbxbxbxbxbxbxbx *1
Turing機械がヘッドを左右に動かすことは文字列の繰り返し回数を2倍や1/2倍にすることに対応するので，「2文字消して4文字書く」とか「2文字消して1文字書く」とかいった方針でtag systemでも頑張れる。
Turing機械がテープを読み取るのは文字列の繰り返し回数を2で割った余りに対応するが，それによる条件分岐も実はtag systemで書ける。だいたい，
- a2n → … → (bc)n → … → (hoge)n
- a2n+1 → … → a(bc)n → (cb)nc → … → (fuga)nc
みたいにすれば良い。
Cyclic tag system
ここからtag systemをcyclic tag systemで帰着して，さらにgliderの何かに帰着し，Rule 110がそういう適切な性質を満たすgliderを持つことを示す流れのようだ。
セルオートマトンで最終的に模倣したいのだから，まず問題になりそうなのはtag systemで何種類の文字が使われるかに制約がないこと。Turing機械についてテープ文字集合が {0, 1} の2文字である場合に帰着するのは簡単だが，tag systemについて文字集合の大きさを2に帰着するのは上手くいかないように思える。
それが理由でかどうかは知らないが，文字列の書き換え規則を固定周期で変化させるようにすると，2-symbolな"tag system"に帰着できる。おまけにP=1にできて*2，しかも文字0の変換先を常に空文字列としても十分で，これをcyclic tag systemとよぶ。
実際，k-symbolのtag systemに使われる文字それぞれをcyclic tag systemでは「1箇所だけ1で残りk-1箇所が0の長さkの文字列」で模倣する。ただし，tag systemの停止文字をcyclic tag systemの停止文字としては模倣できていないことには注意が必要そう。
*1:正確には，状態 qi ごとに別の文字 Ai, xi, ai, … を用いる。
*2:もとのtag systemはP=1では文字列中の文字の出現順序にまったく意味がないため，「文字間の（非決定的）遷移規則」とみなしたときの到達可能性を調べる程度の計算能力しかない。
