見出し画像

2色ライフゲーム=3状態セル・オートマトンのチューリング完全性

HAL



作る過程のサンプル

★経緯と用語紹介

Q．機械について調べてたらチューリングマシンとライフゲームにたどり着きました．こんな単純なもので計算ができるとか面白いですよね．
Ａ．はい．


Ｑ．なぜ単なる四角たちが計算できてるんですか？

Ａ．チューリング完全だからです．

Ｑ．何それ？
Ａ．大半の計算ができる機械の条件です．
計算機械を定義するチャーチ・チューリングのテーゼという"仮定"（証明なし）から，
チューリング完全=大半の計算ができる
=大半の計算ができるチューリングマシンを作れる（模倣できる）マシンと定義されています．

Ｑ．例えば？
Ａ．帰納的関数とか，ラムダ計算とか，プログラミング言語全般とか，マインクラフトとか，マリオメーカーとか．

Ｑ．どうやって証明するの？

Ａ．証明には，他のチューリング完全なマシンを模倣すれば良いです．

Ｑ．例えば？
Ａ．世界最小と言われる「ウルフラムの2記号3状態チューリングマシン」は，
1964年にcocke&Minskyがある特定のチューリングマシンを2-タグシステムで模倣し
1996年にRogozhinが万能チューリングマシンまで2-タグシステムで模倣し
2007年にAlexSmithが3状態2記号チューリングマシンが2-タグシステムを模倣
することで証明されています．

他にも
C言語→brainf*ck→万能チューリングマシン
MTG→あらゆるチューリングマシン
などなど

Ｑ．ふーん．まあせっかくなら新しいことをやりたいです．（逆張り魂）
　　2色（＝無と赤と青の3状態）なら誰もやったことないんじゃね？
Ａ．あります．
Ｑ．ぐぬぬ．
Ａ．はい．
Ｑ．はいじゃないが．

https://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=108427&item_no=1&attribute_id=1&file_no=1

Ｑ．じゃあ，互いに共存し合う2色のライフゲームは？そう！まるで姉妹百合共依存琴葉姉妹のように！
Ａ．なさそう．
Ｑ．俺が世界初だ！！
Ａ．はい．

Ｑ．作りました．単独では生き残れないのが新規性です．

Ｑ．せっかくだからこれに計算させたい！どうすればいい？

Ａ．チューリング完全ならできます．
Ｑ．じゃあ確認方法は？
Ａ．チューリング完全なマシンを作ればよいです．
Ｑ．それほんとに作れる？
Ａ．チューリング完全ならできます．
Ｑ．いや，だからその確認方法は…

以上より，執筆するに至る．
今回の私のように，独りよがり逆張りの極みで生まれるモノは大体実用性皆無です．ご注意ください．

★2色ライフゲーム

いわゆる，3状態セル・オートマトン．
無・茜・葵赤・青で3状態，つまり2色です．

ルールは

  1. ある点を考えたとき，

  2. その点の周り8点の赤・青の数を数えたとき，

  3. 赤数=青数なら，そのまま（生存）

  4. 赤数+1or2=青数なら，多い赤から姉妹百合パワーをもらうイメージで，青が出現．（誕生）

  5. 赤数=青数+1or2なら，多い青から姉妹百合パワーをもらうイメージで，赤が出現．（誕生）

  6. それ以外，つまりどちらかしかない，多すぎるなどすると死ぬ（過疎）

サンプルコードはこちら

お試しサイトはこちら


★チューリング完全の確認ログ

チューリングマシンを模倣するのが王道なので，それを考えてみる

チューリングマシンは，以下のように，テープ・ヘッド・内部状態（と，推移関数＝計算ルール）があればいいらしい．

チューリングマシンの簡易的な説明

  • テープ：ライフゲーム空間上のセルを置くマス

  • ヘッド：情報を読むセルの場所を自分で決めておく

  • 内部状態：周辺のセルの状態

以上で表現できるから．
という証明でいいのかもしれないけど，これだと抽象的すぎて，
具体例が作れない．

論理回路を模倣する

既存のチューリング完全ライフゲームを参考にしたら，
論理回路が使われていると分かりました．

論理回路のいい点は，NANDゲートさえあればあらゆる論理回路が作成可能だと分かっている点です．
その証明はまあ総当たりじゃないかな．NOT, AND, ORを作るだけなので．

じゃあNANDゲートは何があれば作れるのか？
動画では，グライダーという移動物体が使われていましたが，
新しく作ったライフゲームには，安定したグライダーすらあるか分かりません．
しかし，

  • グライダー　　＝信号を送る部分

  • グライダー銃　＝1の信号を送り続ける部分

  • グライダー同士の衝突で消える＝NOTの部分

この3つだけあればいい，という情報は目標になるのでとてもありがたい．
また，後から分かったのですが，計算できるだけの半無限空間も必要．
ここからは，具体的に何をしてきたか試行錯誤を順番に書いてみようと思います．

1.ランダム生成に頼る

最初は何もわからんのでとにかくランダム．
ランダム生成でグライダーがまれる確率はChatGPT-4曰く1兆分の1らしいと知って，やめた．

ランダム生成：最後これしか残らん

ランダム生成から少しでも生き残る物体を見つける

作ったライフゲームに慣れる．
ここでグライダーを見つけられれば御の字．
途中で死ぬグライダーはあったが，生きるグライダーは見つからなかった．
以下のように伸びるやつは見つかった．

伸びるやつら（伸びるだけで，途中ぶつかったら消える）


3. 小さなものを試して安定したグライダーを一つ見つける

4x4くらいで人力で探す．試行錯誤．
グライダーが見つかったら，これが信号を送る部分になる．

今日のグライダー

4. 生成物体を見つける

運悪くグライダーは生成してくれんかった
しかし，組み合わせればグライダー銃になるかもしれない

こんにちは．私は生成物体．


5. 生成物体同士をランダムにぶつけてグライダーを生成させてみる（失敗）

適当では，いつまでたっても生成される気がしない．
ちゃんと調べよう．

6. 生成物体の挙動をひたすら調べる

以下，調べる過程の図．あんまり資料としての意味はないので注意！

グライダーの挙動を全部調べる
生成物体の挙動を全部調べる
上手いことぶつける距離を確認する


7. 生成物体同士を理論的にぶつけてグライダーを生成させる（成功）

前段階で色々調べたので，後は手動で1マス，1世代ずつづらして調整したりしていくと，たまたま今回は上手くいった！
分かりづらいが，これで右方向へ無限に進むグライダーを生成できた．
（余談だが，一回見つけてからどのマスに置いたか忘れてしまったので，追加で1時間ほど失った．）

作る過程のサンプル

あとは，論理回路を組めばいい．
NANDゲートは，NORゲートでもいいらしいので，そっちの方向で考える．
なぜなら，NORは何もないときだけ信号を通す＝信号を妨害さえすればいいので作るのが楽だからである．

NOR回路の概要


やってみたら素通りしちゃったけど，周期合わせたら大丈夫なんで許してください．

あとは，
NOT(A)=NOR(A,A)
NOR(A,B)=NOT(NOR(A,B))=NOR(NOR(A,B),NOR(A,B))
AND(A,B)=NOT(NOR(A,A),NOR(B,B))
とすれば，晴れてすべての論理回路が完成する．
論理回路はチューリング完全である（というか今使ってるパソコン自体，電子部品で作った論理回路なので）ため，あらゆる計算が可能である！

よって，新しく作った2色のライフゲームは，チューリング完全である．
証明おわり．

拙い記事でしたが，読んでいただきありがとうございました．
あなたの調べているライフゲームが，チューリング完全であることを願います．


いいなと思ったら応援しよう！