القاعدة 90

القاعدة 90 هي نموذج أولي لآلة خلوية . أي أنها تتكون من مصفوفة أحادية البعد من الخلايا، تحمل كل منها قيمة ثنائية واحدة، إما 0 أو 1. يُطلق على تعيين القيم لجميع الخلايا اسم " التكوين" . تُعطى الآلة تكوينًا أوليًا، ثم تنتقل عبر تكوينات أخرى في سلسلة من الخطوات الزمنية المنفصلة. في كل خطوة، يتم تحديث جميع الخلايا في آن واحد. تحدد قاعدة مُحددة مسبقًا القيمة الجديدة لكل خلية كدالة لقيمتها السابقة وقيم الخليتين المجاورتين لها. تخضع جميع الخلايا لنفس القاعدة، والتي يمكن التعبير عنها إما كصيغة أو كجدول قواعد يحدد القيمة الجديدة لكل تركيبة ممكنة من القيم المجاورة. ^{[ 1 ]}

في حالة القاعدة 90، تكون القيمة الجديدة لكل خلية هي حاصل الضرب الحصري (أو) للقيمتين المجاورتين. وبالمثل، فإن الحالة التالية لهذه الآلة الآلية المحددة تخضع لجدول القواعد التالي: ^{[ 1 ]}

The name of Rule 90 comes from Stephen Wolfram's binary-decimal notation for one-dimensional cellular automaton rules. To calculate the notation for the rule, concatenate the new states in the rule table into a single binary number, and convert the number into decimal: 01011010₂ = 90₁₀.^[1] Rule 90 has also been called the Sierpiński automaton, due to the characteristic Sierpiński triangle shape it generates,^[4] and the Martin–Odlyzko–Wolfram cellular automaton after the early research of OlivierMartin,Andrew M. Odlyzko,andStephen Wolfram (1984) on this automaton.^[5]

A configuration in Rule 90 can be partitioned into two subsets of cells that do not interact with each other. One of these two subsets consists of the cells in even positions at even time steps and the cells in odd positions in odd time steps. The other subset consists of the cells in even positions at odd time steps and the cells in odd positions at even time steps. Each of these two subsets can be viewed as a cellular automaton with only its half of the cells.^[6] The rule for the automaton within each of these subsets is equivalent (except for a shift by half a cell per time step) to another elementary cellular automaton, Rule 102, in which the new state of each cell is the exclusive or of its old state and its right neighbor. That is, the behavior of Rule 90 is essentially the same as the behavior of two interleaved copies of Rule 102.^[7]

Rule 90 and Rule 102 are called additive cellular automata. This means that, if two initial states are combined by computing the exclusive or of each their states, then their subsequent configurations will be combined in the same way. More generally, one can partition any configuration of Rule 90 into two subsets with disjoint nonzero cells, evolve the two subsets separately, and compute each successive configuration of the original automaton as the exclusive or of the configurations on the same time steps of the two subsets.^[2]

Rule 90 is deterministically solvable, meaning that one can express the state of a given cell after ${\displaystyle n}$ iterations starting from initial configuration ${\displaystyle x\in \{0,1\}^{\mathbb {Z} }}$ by an explicit formula. Let ${\displaystyle [F^{n}(x)]_{j}}$ represent the state of cell ${\displaystyle j}$ after ${\displaystyle n}$ iterations or rule ${\displaystyle F}$وهو في حالتنا القاعدة 90. يتم تمثيل الشرط الأولي بواسطة${\displaystyle x}$، لهذا السبب ${\displaystyle x_{i}}$حالة الخلية ${\displaystyle i}$في التكوين الأولي،${\displaystyle x_{i}\in \{0,1\}}$بالنسبة للقاعدة 90، يمكن إثبات ^{[ 8 ] [ 9 ]} أن

${\displaystyle [F^{n}(x)]_{j}=\sum _{i=0}^{n}{\binom {n}{i}}x_{2\,i-n+j}\mod 2}$

لنفترض أن التكوين الأولي عبارة عن سلسلة ثنائية لا نهائية عشوائية${\displaystyle x\in \{0,1\}^{\mathbb {Z} }}$مستمدة من توزيع برنولي، بحيث يكون احتمال ${\displaystyle x_{i}=1}$يساوي${\displaystyle p\in [0,1]}$واحتمالية${\displaystyle x_{i}=0}$يكون${\displaystyle 1-p}$ثم يمكن للمرء أن يثبت ^{[ 10 ]} أنه بعد${\displaystyle n}$تكرارات القاعدة 90، احتمالات حدوث الكتل${\displaystyle 0,00,000}$، و${\displaystyle 010}$، ويرمز إليه بـ${\displaystyle P_{n}(0),P_{n}(00),P_{n}(000)}$و${\displaystyle P_{n}(010)}$يتم تقديمها بواسطة

${\displaystyle {\begin{aligned}P_{n}(0)&={\frac {1}{2}}+{\frac {1}{2}}\,\left(1-2\,p\right)^{G\left(n\right)},\\P_{n}(00)&=\left({\frac {1}{2}}+{\frac {1}{2}}\,\left(1-2\,p\right)^{G\left(n\right)}\right)^{2},\\P_{n}(000)&=\left({\frac {1}{4}}+{\frac {1}{2}}\,\left(1-2\,p\right)^{G\left(n\right)}+{\frac {1}{4}}\,\left(1-2\,p\right)^{G\left(n+1\right)}\right)\left({\frac {1}{2}}+{\frac {1}{2}}\,\left(1-2\,p\right)^{G\left(n\right)}\right),\\P_{n}(010)&={\frac {1}{8}}+{\frac {1}{8}}\,\left(1-2\,p\right)^{G\left(n\right)}+{\frac {1}{8}}\,\left(1-2\,p\right)^{G\left(n+1\right)}-{\frac {1}{4}}\,\left(1-2\,p\right)^{2\,G\left(n\right)}\\&-{\frac {1}{8}}\,\left(1-2\,p\right)^{G\left(n+1\right)+G\left(n\right)}.\end{aligned}}}$

أين${\displaystyle G(n)}$هي متتالية غولد ،

${\displaystyle G(n)=\sum _{k=0}^{n}\left({n \choose k}\mod 2\right).}$

يمكن الحصول على الاحتمالات المتبقية للكتل ذات الطول 1 و 2 و 3 باستخدام شروط اتساق كولموغوروف، ^{[ 11 ]}

${\displaystyle {\begin{aligned}P(1)&=1-P(0),\\P(01)&=P(0)-P(00),\\P(10)&=P(0)-P(00),\\P(11)&=1-2P(0)+P(00),\\P(001)&=P(00)-P(000),\\P(011)&=P(0)-P(00)-P(010),\\P(100)&=P(00)-P(000),\\P(101)&=P(0)-2P(00)+P(000),\\P(110)&=P(0)-P(00)-P(010),\\P(111)&=1-3P(0)+2P(00)+P(010).\end{aligned}}}$

تمت دراسة آلة القاعدة 90 (بصيغتها المكافئة على إحدى المجموعتين الفرعيتين المستقلتين من الخلايا المتناوبة) في أوائل سبعينيات القرن العشرين، في محاولة لفهم فرضية جيلبريث حول فروق الأعداد الأولية المتتالية . في مثلث الأعداد المُولّد من الأعداد الأولية بتطبيق عامل الفرق الأمامي بشكل متكرر ، يبدو أن معظم القيم إما 0 أو 2. على وجه الخصوص، تنص فرضية جيلبريث على أن القيم الموجودة في أقصى اليسار في كل صف من هذا المثلث هي جميعها 0 أو 2. عندما تكون سلسلة فرعية متجاورة من القيم في أحد صفوف المثلث جميعها 0 أو 2، فإنه يمكن استخدام القاعدة 90 لتحديد السلسلة الفرعية المقابلة في الصف التالي. شرح ميلر (1970) القاعدة باستخدام استعارة نمو الأشجار في الغابة، وعنون بحثه حول هذا الموضوع بـ "غابات دورية من الأشجار المتقزمة". في هذا التشبيه، تبدأ شجرة بالنمو في كل موضع من المواضع الأولية التي قيمتها 1، ثم تنمو غابة الأشجار هذه في آنٍ واحد، لتصل إلى ارتفاع جديد فوق سطح الأرض في كل خطوة زمنية. تمثل كل خلية غير صفرية في كل خطوة زمنية موضعًا يشغله فرع شجرة نامٍ. في كل خطوة زمنية لاحقة، يمكن للفرع أن ينمو إلى إحدى الخليتين الموجودتين فوقه على يساره أو يمينه فقط عندما لا يكون هناك فرع آخر ينافسه على نفس الخلية. غابة الأشجار التي تنمو وفقًا لهذه القواعد لها نفس سلوك القاعدة 90 تمامًا. ^{[ 12 ]}

انطلاقًا من أي تكوين أولي للقاعدة 90، يمكن تشكيل غابة رياضية ، وهي رسم بياني موجه غير دوري ، حيث يمتلك كل رأس حافة خارجية واحدة على الأكثر، وتكون أشجارها مماثلة للأشجار في استعارة ميلر. تحتوي الغابة على رأس لكل زوج ( x , i ) بحيث تكون الخلية x غير صفرية عند الزمن i . لا تمتلك الرؤوس عند الزمن 0 أي حواف خارجية؛ يشكل كل منها جذر شجرة في الغابة. لكل رأس ( x , i ) حيث i غير صفري، تمتد حافته الخارجية إلى ( x ± 1, i − 1) ، وهو الجار الوحيد غير الصفري لـ x في الخطوة الزمنية i − 1. لاحظ ميلر أن هذه الغابات تُكوّن "فسحات" مثلثة، وهي مناطق في مخطط الزمان والمكان لا تحتوي على خلايا غير صفرية، ومحددة بحافة سفلية مسطحة وجوانب قطرية. تتشكل هذه المساحة المفتوحة عندما تصبح سلسلة متتالية من الخلايا صفرًا في خطوة زمنية واحدة، ثم (في استعارة الشجرة) تنمو الفروع إلى الداخل، لتغطي في النهاية خلايا السلسلة مرة أخرى. ^{[ 12 ]}

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

مخطط الزمان والمكان للقاعدة 90 هو رسم بياني يُسجل فيه الصف i تكوين الآلة في الخطوة i . عندما تحتوي الحالة الابتدائية على خلية واحدة غير صفرية، يتخذ هذا المخطط شكل مثلث سيربينسكي ، وهو شكل كسري يتكون من دمج مثلثات لتكوين مثلثات أكبر. تُولّد القواعد 18 و22 و26 و82 و146 و154 و210 و218 أيضًا مثلثات سيربينسكي من خلية واحدة، ولكن ليس جميعها متطابقة تمامًا. إحدى طرق تفسير هذا التركيب هي أن كل خلية في القاعدة 90 هي عملية " أو" الحصرية بين جارتيها. ولأن هذا يُكافئ الجمع بتردد 2، فإنه يُولّد نسخة بتردد 2 من مثلث باسكال . يحتوي المخطط على القيمة 1 حيثما يكون عدد عناصر مثلث باسكال فرديًا ، والقيمة 0 حيثما يكون عدد عناصره زوجيًا . هذا شكل منفصل من مثلث سيربينسكي. ^{[ 1 ] [ 14 ]}

عدد الخلايا الحية في كل صف من هذا النمط هو قوة للعدد اثنين . في الصف رقم i ، يساوي 2^ ^k ، حيث k هو عدد الأرقام غير الصفرية في التمثيل الثنائي للعدد i . تسلسل أعداد هذه الخلايا الحية، 

1، 2، 2، 4، 2، 4، 4، 8، 2، 4، 4، 8، 4، 8، 8، 16، 2، 4، 4، 8، 4، 8، 8، 16، 4، 8، 8، 16، 8، 16، 16، 32، ... (التسلسل A001316 في OEIS )

تُعرف هذه العملية باسم متتالية غولد . الخلية الحية الوحيدة في التكوين الابتدائي تتخذ نمطًا سنّيًا . هذا يعني أنه في بعض الخطوات الزمنية، يزداد عدد الخلايا الحية بشكل كبير، بينما في خطوات أخرى، يعود إلى خليتين حيتين فقط، بشكل متكرر لا نهائي. يتميز معدل نمو هذا النمط بشكل موجة سنّية متنامية ، يمكن استخدامه للتعرف على العمليات الفيزيائية التي تتصرف بشكل مشابه للقاعدة 90. ^{[ 4 ]}

يظهر مثلث سيربينسكي أيضًا بطريقة أكثر دقة في تطور أي تكوين في القاعدة 90. في أي خطوة زمنية i في تطور القاعدة، يمكن حساب حالة أي خلية كعملية "أو الحصرية" لمجموعة فرعية من الخلايا في التكوين الأولي. هذه المجموعة الفرعية لها نفس شكل الصف i من مثلث سيربينسكي. ^{[ 15 ]}

في مثلث سيربينسكي، لأي عدد صحيح i ، تحتوي الصفوف المرقمة بمضاعفات 2i ^على خلايا غير صفرية متباعدة بمسافة لا تقل عن 2i وحدة. لذلك، وبسبب خاصية الجمع في القاعدة 90، إذا كان التكوين الأولي يتكون من نمط محدود P من خلايا غير صفرية بعرض أقل من 2i ^، فإن التكوين، في الخطوات التي هي من مضاعفات 2i، سيتكون من نسخ من ^P متباعدة بمسافة ^لا تقل عن 2i وحدة من البداية إلى البداية. هذه المسافة واسعة بما يكفي لمنع النسخ من التداخل مع بعضها البعض. عدد النسخ هو نفسه عدد الخلايا غير الصفرية في الصف المقابل من مثلث سيربينسكي. وبالتالي، في هذه القاعدة، كل نمط هو مُكرِّر ^: فهو يُولِّد نسخًا متعددة من نفسه تنتشر عبر التكوين، لتملأ المصفوفة بأكملها في النهاية. تتضمن قواعد أخرى، مثل مُنشئ فون نيومان الشامل ، وآلة كود الخلوية ، وحلقات لانغتون، مُستنسخات تعمل عن طريق نقل ونسخ سلسلة من التعليمات لبناء نفسها. في المقابل، فإن عملية النسخ في القاعدة 90 بسيطة وتلقائية. ^{[ 16 ]}

في القاعدة 90، على شبكة أحادية البعد لانهائية، لكل تكوين أربعة تكوينات سابقة بالضبط. والسبب في ذلك هو أنه في التكوين السابق، يمكن لأي خليتين متتاليتين أن تمتلكا أي توليفة من الحالات، ولكن بمجرد اختيار حالات هاتين الخليتين، لا يوجد سوى خيار واحد متسق لحالات الخلايا المتبقية. لذلك، لا يوجد ما يُسمى بـ" جنة عدن" في القاعدة 90، أي تكوين ليس له تكوينات سابقة. إن تكوين القاعدة 90 الذي يتكون من خلية واحدة غير صفرية (مع كون جميع الخلايا الأخرى صفرية) ليس له تكوينات سابقة تحتوي على عدد محدود من الخلايا غير الصفرية. ومع ذلك، فإن هذا التكوين ليس "جنة عدن" لأنه يحتوي على تكوينات سابقة تحتوي على عدد لا نهائي من الخلايا غير الصفرية. ^{[ 17 ]}

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

لأن لكل تكوين عددًا محدودًا من التكوينات السابقة، فإن تطور القاعدة 90 يحافظ على إنتروبيا أي تكوين. على وجه الخصوص، إذا تم اختيار تكوين أولي لانهائي عن طريق اختيار حالة كل خلية بشكل مستقل عشوائيًا، مع تساوي احتمالية اختيار أي من الحالتين، فإنه يمكن وصف كل تكوين لاحق بنفس توزيع الاحتمالات تمامًا. ^{[ 2 ]}