ルール110

ルール110セルオートマトン（単にルール110と呼ばれることが多い）^[a]は、安定性とカオスの境界で興味深い動作をする基本的なセルオートマトンです。この点で、コンウェイのライフゲームに似ています。ライフゲームと同様に、特定の繰り返し背景パターンを持つルール110はチューリング完全であることが知られています。^[2]これは、原理的には、このオートマトンを使用してあらゆる計算やコンピュータプログラムをシミュレートできることを意味します。

意味

基本的なセルオートマトンでは、0 と 1 の 1 次元パターンが一連の単純なルールに従って進化します。パターン内の点が新しい世代で 0 になるか 1 になるかは、その点の現在の値と、その 2 つの隣接する点の値によって決まります。

ルール 110 を使用して、1D セルオートマトンルールが次の世代を決定する方法のアニメーション。

ルール 110 オートマトンには次のルールセットがあります。

「ルール 110」という名前は、このルールが 2 進数シーケンス 01101110 で要約できることに由来しています。2進数として解釈すると、これは 10 進数値 110 に対応します。これはWolfram コードの命名スキームです。

歴史

2004年、マシュー・クックは、特定の繰り返し背景パターンを持つルール110がチューリング完全であること、つまり普遍的な計算が可能であることを証明しました。これは、スティーブン・ウルフラムが1985年に予想したことです。 ^{[2]クックは、ウルフラムの著書}「A New Kind of Science」の出版前に、サンタフェ研究所の会議CA98で証明を発表しました。これは、ウルフラムリサーチとの秘密保持契約に基づく法廷闘争につながりました。^[3]ウルフラムリサーチは、数年にわたってクックの証明の公開を阻止しました。^[4]

興味深い特性

88 個のユニークな基本セルオートマトンのうち、ルール 110 はチューリング完全性が直接証明された唯一のものですが、いくつかの同様のルールの証明は単純な系として続きます (たとえば、ルール 110 の水平反射であるルール 124)。ルール 110 は、おそらく最も単純な既知のチューリング完全なシステムです。^[2]^[5]

ルール110は、ライフゲームと同様に、ウルフラムが「クラス4の振る舞い」と呼ぶものを示します。これは完全に安定しているわけでも、完全に混沌としているわけでもありません。局所的な構造が現れ、複雑な方法で相互作用します。^[6]

マシュー・クックは、巡回タグシステム、2タグシステム、チューリングマシンを順にエミュレートすることで、ルール110が汎用計算をサポートできることを証明した。最終段階では、チューリングマシンのテープが単項数値システムでエンコードされているため、指数時間のオーバーヘッドが発生する。ニアリーとウッズ（2006）は、2タグシステムを時計回りのチューリングマシンに置き換え、多項式のオーバーヘッドが発生する別の構成を提示した。^[7]

普遍性の証明

マシュー・クックは、A New Kind of Scienceの出版前に開催されたサンタフェ研究所の会議で、ルール 110 の普遍性の証明を発表しました。ウルフラムリサーチは、この発表がクックと雇用主との秘密保持契約に違反していると主張し、出版された会議の議事録からクックの論文を除外する裁判所命令を取得しました。それでも、クックの証明の存在は知られるようになりました。彼の証明への関心は、その結果よりもその方法、特にその構築の技術的な詳細から生じました。^{[8]クックの証明の性質は、}A New Kind of Scienceでのルール 110 の議論とはかなり異なります。クックはその後、完全な証明を説明した論文を執筆しました。^[2]

クックは、ルール 110 が普遍的 (またはチューリング完全) であることを証明するために、このルールを使用して、普遍的であることが知られている別の計算モデルである巡回タグシステムをエミュレートすることが可能であることを示しました。彼はまず、ルール 110 の宇宙で無限に繰り返されるパターン上に構築できる、自己永続的な局所的パターンである多数の宇宙船を分離しました。次に、これらの構造の組み合わせが計算に利用できるような方法で相互作用する方法を考案しました。

ルール110の宇宙船

ルール 110 のユニバーサルマシンの機能では、無限に繰り返される背景パターン内に、有限の数のローカライズされたパターンを埋め込む必要があります。背景パターンは 14 個のセルの幅があり、7 回の反復ごとに正確に繰り返されます。パターンは00010011011111です。

ルール 110 ユニバーサルマシンでは、3 つの局所的なパターンが特に重要です。これらは、繰り返しの背景パターンに囲まれた状態で、下の画像に示されています。左端の構造は、右に 2 つのセルにシフトし、3 世代ごとに繰り返されます。これは、上記の背景パターンに囲まれたシーケンス0001110111と、このシーケンスの 2 つの異なる進化で構成されています。

図では、上から下に向かって時間が経過します。一番上の線は初期状態を表し、それに続く各線は次の時間における状態を表します。

中央の構造は 8 つのセルだけ左にシフトし、30 世代ごとに繰り返されます。これは、上記の背景パターンに囲まれたシーケンス1001111と、このシーケンスの 29 の異なる進化で構成されます。

右端の構造は固定されており、7 世代ごとに繰り返されます。これは、上記の背景パターンに囲まれたシーケンス111と、このシーケンスの 5 つの異なる進化で構成されます。

以下の画像は、最初の 2 つの構造が平行移動以外では相互作用せずに互いを通過し (左)、相互作用して 3 番目の構造を形成する (右) ことを示しています。

ルール 110 には他にも多数の宇宙船がありますが、それらは普遍性証明ではそれほど目立っていません。

循環タグシステムの構築

巡回タグシステムマシンには、次の 3 つの主要コンポーネントがあります。

定常的なデータ文字列。
右から始まり左に移動する、無限に繰り返される一連の有限生成規則。
左から始まり右に移動する、無限に繰り返される一連のクロックパルス。

これらのコンポーネント間の初期の間隔は非常に重要です。セルオートマトンが循環タグシステムを実装するには、オートマトンの初期条件を慎重に選択して、そこに含まれるさまざまな局所構造が高度に秩序立った方法で相互作用するようにする必要があります。

巡回タグシステムのデータ文字列は、上記のような一連の定常繰り返し構造で表されます。これらの構造間の水平方向のスペースの量を変えることで、1 シンボルと 0 シンボルを区別します。これらのシンボルは巡回タグシステムが動作している単語を表し、最初のシンボルはすべての生成ルールの検討時に破棄されます。この先頭のシンボルが 1 の場合、文字列の末尾に新しいシンボルが追加されます。先頭のシンボルが 0 の場合、新しいシンボルは追加されません。これを実現するメカニズムについては、以下で説明します。

右から入ってくるのは、上に示したタイプの一連の左に移動する構造で、さまざまな量の水平スペースで区切られています。これらの構造が多数、さまざまなスペースで組み合わされて、循環タグシステムの生成ルールの 0 と 1 を表します。タグシステムの生成ルールはプログラムの作成時にわかっており、無限に繰り返されるため、初期状態の 0 と 1 のパターンは、無限に繰り返される文字列で表すことができます。各生成ルールは、ルールセパレーター(またはブロックセパレーター) と呼ばれる別の構造によって次のルールから区切られており、ルールセパレーターは、生成ルールのエンコードと同じ速度で左に移動します。

左に移動するルールセパレータが循環タグシステムのデータ文字列内の固定シンボルに遭遇すると、最初に遭遇したシンボルが破壊されます。ただし、その後の動作は、文字列によってエンコードされたシンボルが 0 か 1 かによって異なります。0 の場合、ルールセパレータは、入力される生成ルールをブロックする新しい構造に変わります。この新しい構造は、次のルールセパレータに遭遇すると破壊されます。

一方、文字列内のシンボルが 1 だった場合、ルールセパレータは、入力される生成ルールを受け入れる新しい構造に変わります。新しい構造は、次のルールセパレータに遭遇すると再び破壊されますが、最初に一連の構造が左に向かって通過できるようにします。これらの構造は、次に循環タグシステムのデータ文字列の末尾に追加されます。この最終的な変換は、上記の右方向パターンで無限に繰り返される右方向 クロックパルスのシリーズによって行われます。クロックパルスは、生成ルールからの入力される左方向の 1 シンボルをデータ文字列の固定 1 シンボルに変換し、生成ルールからの入力される 0 シンボルをデータ文字列の固定 0 シンボルに変換します。

循環タグシステムが機能している

上の図は、ルール 110 の循環タグシステムの再構築の概略図です。

参照

注記

^ 110は、従来の10進法で書かれた数字110であり、通常の名目上の数字と同じように発音されます。たとえば、スティーブン・ウォルフラムは「ルール・ワン・テン」と発音します。^[1]

参考文献

^ Stephen Wolfram (2003). A New Kind of Science - Stephen Wolfram. カリフォルニア大学テレビジョン (UCTV). イベントは 9:51 に発生します。2023 年 6 月 19 日閲覧。
^ abcd クック（2004年）。
^ Wolfram Research Inc v. Cook (2:00-cv-09357) (「Wolfram Research Inc. v. Matthew Cook. 8/31 CV00-9357 CBM」と引用されることもある)
^ ジャイルズ（2002年）。
^ ウォルフラム（2002）、169ページ、675-691
^ ウルフラム（2002）、229ページ
^ ニアリー＆ウッズ（2006年）。
^ Martinez, Genaro J.; Seck Tuoh Mora, Juan; Chapa, Sergio; Lemaitre, Christian (2019 年 4 月)。「メキシコにおける 50 年間のコンピューティングに関する簡単なメモと歴史」。International Journal of Parallel , Emergent and Distributed Systems。35 (2): 185–192。arXiv : 1905.07527。doi : 10.1080 /17445760.2019.1608990。S2CID 150262966。2020年 4 月 15日に閲覧。

引用文献

クック、マシュー (2004)。「基本的なセルオートマトンにおける普遍性」( PDF)。複雑系。15 : 1–40。
ジャイルズ、ジム (2002)。「これはどのような科学か?」。ネイチャー。417 ( 6886 ) : 216–218。Bibcode : 2002Natur.417..216G。doi : 10.1038 / 417216a。PMID 12015565。S2CID 10636328 。
Neary, Turlough、Woods, Damien (2006)。「セルオートマトン規則 110 の P 完全性」。Bugliesi, Michele、Preneel, Bart、Sassone, Vladimiro、Wegener, Ingo (編)。オートマトン、言語、プログラミング: 第 33 回国際コロキウム、ICALP 2006、ヴェネチア、イタリア、2006 年 7 月 10 ～ 14 日、議事録、パート I。コンピュータサイエンスの講義ノート。第 4051 巻。Springer。pp. 132 ～ 143。doi :10.1007/11786986_13。
ウルフラム、スティーブン（2002）。『新しい科学』。ウルフラムメディア。ISBN 1-57955-008-8。

さらに読む

Cook, Matthew (2008)。「ルール 110 計算の具体的な見方」。Neary, T.、Woods, D.、Seda, AK、Murphy, N. (編)。単純なプログラムの複雑性。理論計算機科学の電子論文集。第 1 巻。pp. 31–55。arXiv : 0906.3248v1。doi : 10.4204 / EPTCS.1.4。S2CID 10266058。
Martínez, Genaro J.; Adamatzky, A.; Chen, Fangyue; Chua, Leon (2012). 「複雑な基本セルオートマトンにおける局所化間のソリトン衝突について: ルール 54 および 110 以降」. Complex Systems . 21 (2): 117–142. arXiv : 1301.6258 . doi :10.25088/ComplexSystems.21.2.117. S2CID 10165042.
Martínez, Genaro J.; Adamatzky, A.; Stephens, Christopher R.; Hoeflich, Alejandro F. (2011). 「セルラーオートマトンスーパーコライダー」. Int. J. Mod. Phys. C . 22 (4): 419–439. arXiv : 1105.4332 . Bibcode :2011IJMPC..22..419M. doi :10.1142/S0129183111016348. S2CID 7508070.
マルティネス、ヘナロ J.ハロルド・V・マッキントッシュ;モラ、フアン CST。ベルガラ、セルジオ VC (2003–2008)。「フェーズ fi_1 を使用したルール 110 による Matthew Cook によって開発された巡回タグシステムの再現」(PDF)。セルラーオートマトンのジャーナル。6 (2–3): 121–161。
Martínez, Genaro J.; McIntosh, Harold V .; Mora, Juan CST; Vergara, Sergio VC (2008). 「ルール 110 のフェーズ fi_1 と呼ばれるグライダーベースの構造による正規言語の決定」。Journal of Cellular Automata。3 (3): 231–270。arXiv : 0706.3348v1。Bibcode :2007arXiv0706.3348J 。
マルティネス、ヘナロ J.ハロルド・V・マッキントッシュ;モラ、フアン CST。ベルガラ、セルジオ VC (2007)。「ルール 110 オブジェクトおよびその他の構築物ベースの衝突」(PDF)。セルラーオートマトンのジャーナル。2 (3): 219–242。
Martínez, Genaro J.; McIntosh, Harold V .; Mora, Juan CST (2006). 「ルール 110 のグライダー」(PDF) . Int. J. Of Unconventional Computing . 2 : 1–49.
Martínez, Genaro J.; McIntosh, Harold V .; Mora, Juan CST (2003)。「ルール 110 での衝突によるグライダーの生成」(PDF)。人工生命の進歩。コンピュータサイエンスの講義ノート。第 2801 巻。pp. 175–182。doi : 10.1007/ 978-3-540-39432-7_19。ISBN 978-3-540-20057-4。
Martínez, Genaro J.; McIntosh, Harold V. (2001)。「ATLAS: ルール 110 におけるエーテルの位相としてのグライダーの衝突」。
McIntosh, Harold V. (1999) 「グライダーの存在に関する規則 110」(PDF)。
マッキントッシュ、ハロルド V. (2002) 「ルール 110 は普遍的である!」(PDF)。

外部リンク

ルール 110 — Wolfram MathWorld より
ウルフラムのセルオートマトンアトラスのルール110
ルール 110 リポジトリ
4 ビットルール 110 コンピューターのビー玉ベースの機械的実装

[2] 110は、従来の10進法で書かれた数字110であり、通常の名目上の数字と同じように発音されます。たとえば、スティーブン・ウォルフラムは「ルール・ワン・テン」と発音します。^[1]

[1] Stephen Wolfram (2003). A New Kind of Science - Stephen Wolfram. カリフォルニア大学テレビジョン (UCTV). イベントは 9:51 に発生します。2023 年 6 月 19 日閲覧。

[FOOTNOTECook2004-3] クック（2004年）。

[4] Wolfram Research Inc v. Cook (2:00-cv-09357) (「Wolfram Research Inc. v. Matthew Cook. 8/31 CV00-9357 CBM」と引用されることもある)

[FOOTNOTEGiles2002-5] ジャイルズ（2002年）。

[6] ウォルフラム（2002）、169ページ、675-691

[7] ウルフラム（2002）、229ページ

[FOOTNOTENearyWoods2006-8] ニアリー＆ウッズ（2006年）。

[9] Martinez, Genaro J.; Seck Tuoh Mora, Juan; Chapa, Sergio; Lemaitre, Christian (2019 年 4 月)。「メキシコにおける 50 年間のコンピューティングに関する簡単なメモと歴史」。International Journal of Parallel , Emergent and Distributed Systems。35 (2): 185–192。arXiv : 1905.07527。doi : 10.1080 /17445760.2019.1608990。S2CID 150262966。2020年 4 月 15日に閲覧。