Cyclic cellular automaton

A cyclic cellular automaton is a kind of cellular automaton rule developed by David Griffeath and studied by several other cellular automaton researchers. In this system, each cell remains unchanged until some neighboring cell has a modular value exactly one unit larger than that of the cell itself, at which point it copies its neighbor's value. One-dimensional cyclic cellular automata can be interpreted as systems of interacting particles, while cyclic cellular automata in higher dimensions exhibit complex spiraling behavior.

As with any cellular automaton, the cyclic cellular automaton consists of a regular grid of cells in one or more dimensions. The cells can take on any of ${\displaystyle n}$ states, ranging from ${\displaystyle 0}$ to ${\displaystyle n-1}$. The first generation starts out with random states in each of the cells. In each subsequent generation, if a cell has a neighboring cell whose value is the successor of the cell's value, the cell is "consumed" and takes on the succeeding value. (Note that ${\displaystyle 0}$ is the successor of ${\displaystyle n-1}$; see also modular arithmetic.) More general forms of this type of rule also include a threshold parameter, and only allow a cell to be consumed when the number of neighbors with the successor value exceeds this threshold.

The one-dimensional cyclic cellular automaton has been extensively studied by Robert Fisch, a student of Griffeath.^[1] Starting from a random configuration with n = 3 or n = 4, this type of rule can produce a pattern which, when presented as a time-space diagram, shows growing triangles of values competing for larger regions of the grid.

يمكن اعتبار الحدود بين هذه المناطق بمثابة جسيمات متحركة تتصادم وتتفاعل مع بعضها البعض. في الأوتوماتا الخلوية الدورية ثلاثية الحالات، يمكن اعتبار الحد الفاصل بين المناطق ذات القيمتين i و i + 1 (mod n ) بمثابة جسيم يتحرك إما إلى اليسار أو إلى اليمين اعتمادًا على ترتيب المناطق؛ فعندما يصطدم جسيم يتحرك إلى اليسار بآخر يتحرك إلى اليمين، فإنهما يفنيان بعضهما البعض، مما يؤدي إلى نقص جسيمين في النظام. يحدث هذا النوع من عملية الإفناء الباليستي في العديد من الأوتوماتا الخلوية الأخرى والأنظمة ذات الصلة، بما في ذلك القاعدة 184 ، وهي أوتوماتا خلوية تُستخدم لنمذجة تدفق حركة المرور . ^{[ 2 ]} يمكن حل السلوك طويل المدى لهذه القاعدة بدقة . إذا كانت قيمتان من القيم الثلاث لهما كثافة ابتدائية 0 ≤ p ≤ 1/2، فإن متوسط ​​حجم المجموعة عند الزمن t يساوي تقريبًا${\displaystyle {\sqrt {\pi t/2p}}}$[ ^{3 ]​}

في الأوتوماتون ذي n = 4، يحدث النوعان نفسا الجسيمات ونفس تفاعل الإفناء. بالإضافة إلى ذلك، يمكن اعتبار الحد الفاصل بين المناطق ذات القيمتين i و i + 2 (mod n ) نوعًا ثالثًا من الجسيمات، يبقى ثابتًا. ينتج عن تصادم جسيم متحرك بآخر ثابت جسيم متحرك واحد يتحرك في الاتجاه المعاكس. بدءًا من حالة ابتدائية ذات كثافات متساوية لجميع القيم، يخضع متوسط ​​حجم المجموعة لقانون القوة بمعامل أسي يقارب 0.3467. ^{[ 4 ]}

مع ذلك، بالنسبة لـ n ≥ 5، تميل التكوينات الأولية العشوائية إلى الاستقرار بسرعة بدلاً من تشكيل أي ديناميكيات طويلة المدى غير تافهة. وقد أطلق غريفيث على هذا التناقض بين ديناميكيات الجسيمات طويلة المدى للأوتوماتا n = 3 و n = 4 من جهة، والسلوك الساكن للأوتوماتا n ≥ 5 من جهة أخرى، اسم "معضلة بوب"، نسبةً إلى بوب فيش. ^{[ 5 ]}

في بُعدين، وبدون عتبة، وباستخدام جوار فون نيومان أو جوار مور ، يُولّد هذا الأوتومات الخلوي ثلاثة أنواع عامة من الأنماط بالتتابع، انطلاقًا من شروط ابتدائية عشوائية على شبكات كبيرة بما يكفي، بغض النظر عن قيمة n . ^{[ 6 ]} في البداية، يكون الحقل عشوائيًا تمامًا. عندما تستهلك الخلايا جيرانها وتصبح ضمن نطاق استهلاك الخلايا ذات الرتبة الأعلى، ينتقل الأوتومات إلى مرحلة الاستهلاك، حيث تتقدم كتل ملونة في مواجهة الكتل المتبقية من العشوائية. من المهم في المراحل اللاحقة وجود كائنات تُسمى "الشياطين"، وهي عبارة عن دورات من الخلايا المتجاورة تحتوي على خلية واحدة من كل حالة، بترتيب دوري؛ تدور هذه الدورات باستمرار وتُولّد موجات تنتشر في نمط حلزوني متمركز حول خلايا الشيطان. المرحلة الثالثة، وهي مرحلة الشيطان، تهيمن عليها هذه الدورات. تستهلك الشياطين ذات الدورات الأقصر الشياطين ذات الدورات الأطول حتى تدخل كل خلية من خلايا الآلة، بشكل شبه مؤكد ، في دورة متكررة من الحالات، حيث تكون فترة التكرار إما n أو (بالنسبة للآلات ذات n فردي وجوار فون نيومان) n + 1. ويحدث السلوك الدوري نفسه في الأبعاد الأعلى. كما يمكن إنشاء هياكل صغيرة بأي فترة زوجية بين n و 3n / 2. وبدمج هذه الهياكل، يمكن بناء تكوينات ذات فترة فائقة متعددة الحدود. ^{[ 7 ]}

في المناطق المجاورة الأكبر، يظهر سلوك حلزوني مماثل عند العتبات المنخفضة، ولكن عند العتبات العالية بما يكفي، يستقر الأوتوماتون في مرحلة كتلة اللون دون تشكيل حلزونات. عند القيم المتوسطة للعتبة، يمكن أن يتشكل مزيج معقد من كتل الألوان والحلزونات الجزئية، يُسمى الاضطراب. ^{[ 8 ]} باختيار مناسب لعدد الحالات وحجم المنطقة المجاورة، يمكن جعل الأنماط الحلزونية التي يشكلها هذا الأوتوماتون تُشابه تلك الخاصة بتفاعل بيلوسوف-جابوتينسكي في الكيمياء، أو أنظمة الموجات الذاتية الأخرى ، على الرغم من أن الأوتوماتا الخلوية الأخرى تُحاكي بدقة أكبر الوسط القابل للاستثارة الذي يؤدي إلى هذا التفاعل.

• بيليتزكي، فلاديمير؛ فيراري، بابلو أ. (1995). "الإبادة الباليستية والنمو السطحي الحتمي". مجلة الفيزياء الإحصائية . 80 ( 3-4 ): 517-543 . Bibcode : 1995JSP....80..517B . doi : 10.1007/BF02178546 .
• بونيموفيتش، ل. أ.؛ تروبيتسكوي، س. إ. (1994). "المُدوِّرات، والدورية، وانعدام الانتشار في الأوتوماتا الخلوية الدورية". مجلة الفيزياء الإحصائية . 74 ( 1-2 ): 1-10 . Bibcode : 1994JSP....74....1B . doi : 10.1007/BF02186804 .
• ديودني، أ.ك. (1989). "التسلية الحاسوبية: عالم خلوي من الحطام والقطرات والعيوب والشياطين" . مجلة ساينتفك أمريكان (أغسطس): 102-105 .
• فيش، ر. (1990أ). "الآلة الخلوية الدورية أحادية البعد: نظام ذو ديناميكيات حتمية يحاكي نظام جسيمات متفاعلة ذو ديناميكيات عشوائية". مجلة الاحتمالات النظرية . 3 (2): 311-338 . doi : 10.1007/BF01045164 .
• فيش، ر. (1990ب). "الأتمتة الخلوية الدورية والعمليات ذات الصلة". فيزيكا د . 45 ( 1-3 ): 19-25 . رمز Bibcode : 1990PhyD...45...19F . doi : 10.1016/0167-2789(90)90170-T .أُعيد طبعه في: غوتويتز، هوارد أ.، محرر (1991). الأوتوماتا الخلوية: النظرية والتجربة . مطبعة معهد ماساتشوستس للتكنولوجيا/نورث هولاند. الصفحات 19-25 . ISBN  0-262-57086-6.
• فيش، ر. (1992). "التجميع في الأوتومات الخلوي الدوري أحادي البعد ثلاثي الألوان" . حوليات الاحتمالات . 20 (3): 1528-1548 . doi : 10.1214/aop/1176989705 .
• فيش، ر.؛ غرافنر، ج.؛ غريفيث، د. (1991). "توسيع نطاق العتبة للأوتوماتا الخلوية القابلة للاستثارة". الإحصاء والحوسبة . 1 : 23-39 . arXiv : patt-sol/9304001 . doi : 10.1007/BF01890834 .
• ماتامالا، مارتن؛ مورينو، إدواردو (2004). "ديناميكيات الأوتوماتا الدورية على Z^2". علوم الحاسوب النظرية . 322 (2): 369-381 . doi : 10.1016/j.tcs.2004.03.018 . hdl : 10533/175114 .
• شاليزي، كوزما روهيلا ؛ شاليزي، كريستينا ليزا (2003). "قياس التنظيم الذاتي في الأوتوماتا الخلوية الدورية". في: لوتز شيمانسكي-جير؛ ديريك أبوت ؛ ألكسندر نيمان؛ كريستيان فان دن بروك (محررون). الضوضاء في الأنظمة المعقدة والديناميكيات العشوائية . بيلينجهام، واشنطن: SPIE. الصفحات 108-117 . arXiv : nlin/0507067 . Bibcode : 2005nlin......7067R . 
• ستيف، جيفري إي. (1995). "تطبيقان للترشيح على الأوتوماتا الخلوية". مجلة الفيزياء الإحصائية . 78 ( 5-6 ): 1325-1335 . Bibcode : 1995JSP....78.1325S . doi : 10.1007/BF02180134 .