नियम 90: Difference between revisions

जब एक जीवित कोशिका से शुरू किया गया, तो नियम 90 में सिएरपिन्स्की त्रिकोण के रूप में एक समय-स्थान आरेख है। किसी भी अन्य कॉन्फ़िगरेशन के व्यवहार को इस पैटर्न की प्रतियों के सुपरपोजिशन के रूप में समझाया जा सकता है, जो अनन्य या फ़ंक्शन का उपयोग करके संयुक्त है। कोई भी कॉन्फ़िगरेशन केवल सूक्ष्म रूप से कई गैर-शून्य कोशिकाओं के साथ एक रेप्लिकेटर (सेलुलर ऑटोमेटन) बन जाता है जो अंततः सरणी को स्वयं की प्रतियों से भर देता है। जब नियम 90 को एक यादृच्छिक प्रारंभिक विन्यास से शुरू किया जाता है, तो इसका विन्यास हर बार कदम पर यादृच्छिक रहता है। इसका टाइम-स्पेस आरेख विभिन्न आकारों की कई त्रिकोणीय खिड़कियां बनाता है, पैटर्न जो तब बनते हैं जब कोशिकाओं की एक लगातार पंक्ति एक साथ शून्य हो जाती है और फिर मान 1 वाले सेल धीरे-धीरे दोनों सिरों से इस पंक्ति में चले जाते हैं।

नियम 90 के शुरुआती अध्ययनों में से कुछ [[संख्या सिद्धांत]] में एक अनसुलझी समस्या के संबंध में किए गए थे, गिलब्रेथ का अनुमान, क्रमिक अभाज्य संख्याओं के अंतर पर।

यह नियम गॉल्ड के अनुक्रम के माध्यम से संख्या सिद्धांत से एक अलग तरीके से भी जुड़ा हुआ है। यह क्रम एकल लाइव सेल के साथ नियम 90 शुरू करने के बाद प्रत्येक समय चरण में गैर-शून्य कोशिकाओं की संख्या की गणना करता है।

चरण संख्या के [[द्विआधारी प्रतिनिधित्व]] में गैर-शून्य अंकों की संख्या के बराबर एक्सपोनेंट के साथ इसका मान [[दो की शक्ति]] है। नियम 90 के अन्य अनुप्रयोगों में [[टेपेस्ट्री]] का डिज़ाइन शामिल है।

नियम 90 के प्रत्येक विन्यास में ठीक चार पूर्ववर्ती हैं, अन्य विन्यास जो एक चरण के बाद दिए गए विन्यास का निर्माण करते हैं। इसलिए, कॉनवे के गेम ऑफ लाइफ जैसे कई अन्य सेलुलर ऑटोमेटा के विपरीत, नियम 90 में कोई गार्डन ऑफ ईडन (सेलुलर ऑटोमेटन) नहीं है, एक कॉन्फ़िगरेशन जिसमें कोई पूर्ववर्ती नहीं है। यह एक सेलुलर automaton का उदाहरण प्रदान करता है जो [[विशेषण]] है (प्रत्येक कॉन्फ़िगरेशन में पूर्ववर्ती है) लेकिन [[इंजेक्शन]] नहीं है (इसमें एक ही उत्तराधिकारी के साथ एक से अधिक कॉन्फ़िगरेशन के सेट हैं)। यह ईडन प्रमेय के गार्डन से अनुसरण करता है कि नियम 90 स्थानीय रूप से इंजेक्शन है (एक ही उत्तराधिकारी के साथ सभी कॉन्फ़िगरेशन अनंत संख्या में कोशिकाओं में भिन्न होते हैं)।

[[File:Rule 90 gate array.svg|thumb|नियम 90 में, प्रत्येक सेल के मान की गणना पिछले समय चरण में अनन्य या दो पड़ोसी मानों के रूप में की जाती है।]]नियम 90 एक प्राथमिक कोशिकीय automaton है। इसका मतलब यह है कि इसमें कोशिकाओं की एक-आयामी सरणी होती है, जिनमें से प्रत्येक में एक एकल बाइनरी मान होता है, या तो 0 या 1. सभी कोशिकाओं को मानों का असाइनमेंट एक कॉन्फ़िगरेशन कहलाता है। Automaton को प्रारंभिक कॉन्फ़िगरेशन दिया जाता है, और फिर अलग-अलग समय चरणों के अनुक्रम में अन्य कॉन्फ़िगरेशन के माध्यम से प्रगति करता है। प्रत्येक चरण पर, सभी सेल एक साथ अपडेट किए जाते हैं। एक पूर्व-निर्दिष्ट नियम प्रत्येक सेल के नए मान को उसके पिछले मूल्य और उसके दो पड़ोसी कोशिकाओं के मूल्यों के एक समारोह के रूप में निर्धारित करता है। सभी कक्ष एक ही नियम का पालन करते हैं, जो या तो एक सूत्र के रूप में या एक नियम तालिका के रूप में दिया जा सकता है जो पड़ोसी मानों के प्रत्येक संभावित संयोजन के लिए नया मान निर्दिष्ट करता है।<ref name="w83"/>

नियम 90 के मामले में, प्रत्येक सेल का नया मान अनन्य या दो पड़ोसी मूल्यों का है। समतुल्य रूप से, इस विशेष automaton की अगली स्थिति निम्न नियम तालिका द्वारा नियंत्रित होती है:<ref name="w83"/>

नियम 90 का नाम स्टीफन वोल्फ्राम के [[वोल्फ्राम कोड]] से आता है। एक-आयामी सेलुलर ऑटोमेटन नियमों के लिए बाइनरी-[[दशमलव]] संकेतन। नियम के लिए अंकन की गणना करने के लिए, नियम तालिका में नए राज्यों को एकल [[बाइनरी संख्या]] में जोड़ें, और संख्या को दशमलव में बदलें: 01011010₂ = 90₁₀.<ref name="w83"/>नियम 90 को Sierpinski automaton भी कहा जाता है, इसकी विशेषता Sierpinski त्रिभुज आकार के कारण उत्पन्न होती है,<ref name="cns04"/>और मार्टिन-ओडलीज़को-वोल्फ्राम सेलुलर ऑटोमेटन के शुरुआती शोध के बाद {{harvs|first1=Olivier|last1=Martin|first2=Andrew M.|last2=Odlyzko|author2-link=Andrew Odlyzko|first3=Stephen|last3=Wolfram|author3-link=Stephen Wolfram|year=1984|txt}} इस automaton पर।<ref>{{citation|first1=Michał|last1=Misiurewicz|first2=John G.|last2=Stevens|first3=Diana M.|last3=Thomas|author3-link= Diana Thomas (mathematician) |title=Iterations of linear maps over finite fields|journal=Linear Algebra and Its Applications|volume=413|issue=1|year=2006|pages=218–234|doi=10.1016/j.laa.2005.09.002|doi-access=free}}.</ref>

नियम 90 में एक विन्यास को कोशिकाओं के दो सबसेट में विभाजित किया जा सकता है जो एक दूसरे के साथ बातचीत नहीं करते हैं। इन दो उपसमुच्चयों में से एक में सम समय चरणों में सम स्थिति वाले कक्ष और विषम समय चरणों में विषम स्थिति वाले कक्ष शामिल हैं। दूसरे उपसमुच्चय में विषम समय चरणों में सम स्थिति में कक्ष और सम समय चरणों में विषम स्थिति में कक्ष शामिल हैं। इन दो उपसमुच्चयों में से प्रत्येक को एक कोशिकीय ऑटोमेटन के रूप में देखा जा सकता है, जिसमें केवल इसकी आधी कोशिकाएँ होती हैं।<ref>{{citation|first=Harold V.|last=McIntosh|author-link=Harold V. McIntosh|url=http://delta.cs.cinvestav.mx/~mcintosh/comun/wandl/global.pdf|year=1993|title=Ancestors: Commentaries on "The Global Dynamics of Cellular Automata" by Andrew Wuensche and Mike Lesser (Addison-Wesley, 1992)|publisher=Instituto de Ciencias, Universidad Autónoma de Puebla}}.</ref>

इनमें से प्रत्येक उपसमुच्चय के भीतर ऑटोमेटन के लिए नियम एक अन्य प्राथमिक सेलुलर ऑटोमेटन, नियम 102 के समतुल्य है (प्रति समय चरण में आधे सेल की शिफ्ट को छोड़कर), जिसमें प्रत्येक सेल की नई स्थिति अनन्य या उसके पुराने राज्य की है और उसका सही पड़ोसी। अर्थात्, नियम 90 का व्यवहार अनिवार्य रूप से नियम 102 की दो परस्पर जुड़ी प्रतियों के व्यवहार के समान है।<ref>{{citation

नियम 90 और नियम 102 को योज्य सेलुलर ऑटोमेटा कहा जाता है। इसका मतलब यह है कि, यदि दो प्रारंभिक अवस्थाओं को अलग-अलग या उनके प्रत्येक राज्यों की गणना करके जोड़ा जाता है, तो उनके बाद के विन्यासों को उसी तरह जोड़ा जाएगा। अधिक आम तौर पर, नियम 90 के किसी भी कॉन्फ़िगरेशन को दो उपसमुच्चय में असंबद्ध गैर-शून्य कोशिकाओं के साथ विभाजित कर सकते हैं, दो उपसमुच्चय को अलग-अलग विकसित कर सकते हैं, और मूल ऑटोमेटन के प्रत्येक क्रमिक विन्यास को अनन्य या दो उपसमुच्चय के एक ही समय चरणों पर विन्यास के रूप में गणना कर सकते हैं। .<ref name="mow84"/>

[[File:Rule 90 trees.svg|thumb|upright=1.35|अस्त-व्यस्त पेड़ों का जंगल। यह एक टाइम-स्पेस डायग्राम है, लेकिन समय ऊपर की ओर चल रहा है, नीचे की ओर नहीं। दिलचस्प बात यह है कि पांचवां पेड़ समर्थ होते हुए भी दोनों दिशाओं में नहीं निकला।]]1970 के दशक की शुरुआत में रूल 90 ऑटोमेटन (वैकल्पिक कोशिकाओं के दो स्वतंत्र उपसमुच्चयों में से एक पर इसके समकक्ष रूप में) की जांच की गई, ताकि लगातार [[अभाज्य संख्या]]ओं के अंतर पर गिलब्रेथ के अनुमान में अतिरिक्त जानकारी हासिल की जा सके। [[ आगे अंतर ऑपरेटर ]] को बार-बार लागू करने से अभाज्य संख्याओं के त्रिकोण में, ऐसा प्रतीत होता है कि अधिकांश मान या तो 0 या 2 हैं। विशेष रूप से, गिलब्रेथ के अनुमान का दावा है कि इस त्रिकोण की प्रत्येक पंक्ति में सबसे बाईं ओर के मान सभी 0 या 2 हैं। जब त्रिभुज की एक पंक्ति में मानों का सन्निहित अनुक्रम सभी 0 या 2 हो, तो नियम 90 का उपयोग अगली पंक्ति में संबंधित अनुक्रम को निर्धारित करने के लिए किया जा सकता है। {{harvtxt|Miller|1970}} एक जंगल में पेड़ की वृद्धि के एक रूपक द्वारा नियम की व्याख्या की, इस विषय पर अपने पेपर का हकदार पेड़ों के समय-समय पर जंगल। इस रूपक में, प्रारंभिक विन्यास के प्रत्येक स्थान पर एक पेड़ बढ़ने लगता है जिसका मान 1 है, और पेड़ों का यह जंगल तब एक साथ बढ़ता है, प्रत्येक समय कदम पर जमीन के ऊपर एक नई ऊंचाई तक। प्रत्येक समय कदम पर प्रत्येक अशून्य कक्ष एक ऐसी स्थिति का प्रतिनिधित्व करता है जो एक बढ़ती पेड़ की शाखा द्वारा कब्जा कर लिया जाता है। प्रत्येक क्रमिक समय कदम पर, एक शाखा उसके ऊपर दो कोशिकाओं में से एक में उसके बाएँ और दाएँ विकसित हो सकती है, जब कोई अन्य शाखा उसी कोशिका के लिए प्रतिस्पर्धा नहीं कर रही हो। इन नियमों के अनुसार उगने वाले वृक्षों के जंगल में नियम 90 के समान ही व्यवहार होता है।<ref name="m70">{{citation|first=J. C. P.|last=Miller|authorlink=J. C. P. Miller|title=Periodic forests of stunted trees|journal=Philosophical Transactions of the Royal Society of London|series=Series A, Mathematical and Physical Sciences|volume=266|issue=1172|year=1970|pages=63–111|jstor=73779|doi=10.1098/rsta.1970.0003|bibcode = 1970RSPTA.266...63M |s2cid=123330469 }}.</ref>

यादृच्छिक प्रारंभिक स्थितियों के लिए, इस तरह से बने पेड़ों के बीच की सीमाएं स्वयं एक प्रतीत होता है यादृच्छिक पैटर्न में बदल जाती हैं, और पेड़ अक्सर पूरी तरह से मर जाते हैं। लेकिन [[ शिफ्ट का रजिस्टर ]] के सिद्धांत के माध्यम से वह और अन्य प्रारंभिक स्थितियों को खोजने में सक्षम थे जिसमें सभी पेड़ हमेशा के लिए जीवित रहते हैं, विकास का पैटर्न समय-समय पर दोहराता है, और सभी समाशोधन को आकार में बंधे रहने की गारंटी दी जा सकती है।<ref name="m70"/><ref>{{citation|first=H. G.|last=ApSimon|title=Periodic forests whose largest clearings are of size 3|journal=Philosophical Transactions of the Royal Society of London|series=Series A, Mathematical and Physical Sciences|volume=266|issue=1172|year=1970|pages=113–121|jstor=73780|doi=10.1098/rsta.1970.0004|bibcode=1970RSPTA.266..113A|s2cid=121067116 }}; {{citation|first=H. G.|last=ApSimon|title=Periodic forests whose largest clearings are of size ''n''&nbsp;≥&nbsp;4|journal=Philosophical Transactions of the Royal Society of London|series=Series A, Mathematical and Physical Sciences|volume=266|issue=1538|year=1970|pages=399–404|jstor=73780|doi=10.1098/rspa.1970.0185 |bibcode=1970RSPSA.319..399A|s2cid=119435085 }}. A similar analysis of periodic configurations in Rule 90 also appears in {{harvtxt|Wolfram|2002}}, p. 954.</ref>

टेपेस्ट्री के डिजाइन बनाने के लिए मिलर ने इन दोहराए जाने वाले पैटर्न का इस्तेमाल किया। मिलर के कुछ चित्रपट भौतिक वृक्षों का चित्रण करते हैं; अन्य लोग त्रिकोण के अमूर्त पैटर्न का उपयोग करते हुए नियम 90 ऑटोमेटन की कल्पना करते हैं।<ref name="m70"/>

[[File:R090 pulse wide.png|thumb|upright=1.5|Sierpinski त्रिकोण नियम 90 द्वारा उत्पन्न]]नियम 90 का टाइम-स्पेस डायग्राम एक प्लॉट है जिसमें {{math|''i''}}वीं पंक्ति स्टेप पर ऑटोमेटन के कॉन्फ़िगरेशन को रिकॉर्ड करती है {{math|''i''}}. जब आरंभिक अवस्था में एक एकल अशून्य कोशिका होती है, तो इस आरेख में सिएरपिन्स्की [[त्रिकोण]] का आभास होता है, जो त्रिभुजों को बड़े त्रिभुजों में जोड़कर बनाया गया एक [[भग्न]] है। नियम 18, 22, 26, 82, 146, 154, 210 और 218 भी एक सेल से सीरपिंस्की त्रिकोण उत्पन्न करते हैं, हालांकि ये सभी पूरी तरह से समान रूप से नहीं बनाए जाते हैं। इस संरचना की व्याख्या करने का एक तरीका इस तथ्य का उपयोग करता है कि, नियम 90 में, प्रत्येक कोशिका अनन्य या उसके दो पड़ोसियों में से एक है। क्योंकि यह [[मॉड्यूलर अंकगणित]] -2 जोड़ के बराबर है, यह पास्कल के त्रिकोण के मोडुलो -2 संस्करण को उत्पन्न करता है। आरेख में 1 है जहाँ पास्कल के त्रिभुज में एक [[विषम संख्या]] है, और 0 जहाँ पास्कल के त्रिभुज में एक [[सम संख्या]] है। यह सिएरपिन्स्की त्रिकोण का असतत संस्करण है।<ref name="w83"/><ref>{{harvtxt|Wolfram|2002}}, pp. 25–26, 270–271, 870.</ref>

आरंभिक विन्यास की एकल सजीव कोशिका एक [[सॉटूथ (सेलुलर ऑटोमेटन)]] है। इसका मतलब यह है कि कुछ समय में जीवित कोशिकाओं की संख्या मनमाने ढंग से बड़ी हो जाती है, जबकि अन्य चरणों में वे केवल दो जीवित कोशिकाओं में लौटते हैं, असीम रूप से अक्सर।

नियम 90 में किसी भी विन्यास के विकास में सिएरपिन्स्की त्रिकोण भी अधिक सूक्ष्म तरीके से होता है। किसी भी समय कदम {{math|''i''}} नियम के विकास में, किसी भी सेल की स्थिति की गणना प्रारंभिक कॉन्फ़िगरेशन में कोशिकाओं के अनन्य या सबसेट के रूप में की जा सकती है। उस उपसमुच्चय का आकार वैसा ही होता है जैसा कि होता है {{math|''i''}}सीरपिन्स्की त्रिभुज की चौथी पंक्ति।<ref>{{citation|first1=B. K.|last1=Kar|first2=A.|last2=Gupta|first3=P. Pal|last3=Chaudhuri|title=On explicit expressions in additive cellular automata theory|journal=Information Sciences|volume=72|issue=1–2|pages=83–103|year=1993|doi=10.1016/0020-0255(93)90030-P}}.</ref>

सीरपिन्स्की त्रिकोण में, किसी भी पूर्णांक के लिए {{math|''i''}}, के गुणकों द्वारा क्रमांकित पंक्तियाँ {{math|2^''i''}} में कम से कम अशून्य कक्ष हैं {{math|2^''i''}} इकाइयां अलग। इसलिए, नियम 90 की योज्य संपत्ति के कारण, यदि प्रारंभिक विन्यास में एक परिमित पैटर्न होता है {{math|''P''}} से कम चौड़ाई वाली अशून्य कोशिकाओं की {{math|2^''i''}}, फिर उन चरणों में जो गुणक हैं {{math|2^''i''}}, कॉन्फ़िगरेशन में इसकी प्रतियां शामिल होंगी {{math|''P''}} कम से कम दूरी {{math|2^''i''}} इकाइयां शुरू से शुरू करने के लिए। यह रिक्ति प्रतियों को एक दूसरे के साथ हस्तक्षेप करने से रोकने के लिए पर्याप्त चौड़ी है। प्रतियों की संख्या सिएरपिन्स्की त्रिभुज की संबंधित पंक्ति में शून्येतर कोशिकाओं की संख्या के समान है। इस प्रकार, इस नियम में, प्रत्येक पैटर्न एक रेप्लिकेटर (सेलुलर ऑटोमेटन) है: यह स्वयं की कई प्रतियाँ उत्पन्न करता है जो कॉन्फ़िगरेशन में फैल जाती हैं, अंततः पूरे सरणी को भर देती हैं। [[वॉन न्यूमैन यूनिवर्सल कंस्ट्रक्टर]], कॉड के सेलुलर ऑटोमेटन और लैंगटन के लूप सहित अन्य नियमों में भी प्रतिकृतियां हैं जो स्वयं के निर्माण के लिए निर्देशों के अनुक्रम को लेकर और कॉपी करके काम करती हैं। इसके विपरीत, नियम 90 में प्रतिकृति तुच्छ और स्वचालित है।<ref name="replicator">{{citation|first=Abraham|last=Waksman|title=A model of replication|journal=[[Journal of the ACM]]|volume=16|issue=1|year=1969|pages=178–188|doi=10.1145/321495.321509|s2cid=14547972 }}; {{citation|first1=Serafino|last1=Amoroso|first2=Gerald|last2=Cooper|title=Tessellation structures for reproduction of arbitrary patterns|journal=Journal of Computer and System Sciences|volume=5|issue=5|pages=455–464|year=1971|doi=10.1016/S0022-0000(71)80009-0|doi-access=free}}. {{harvtxt|Wolfram|1983}} (Fig.33 and surrounding text) also mentions the same property, and as well as citing Waksman, Amoroso, and Cooper he credits its observation to unpublished work by [[Edward Fredkin]] in 1981.</ref>

नियम 90 में, अनंत एक आयामी जाली पर, प्रत्येक विन्यास में ठीक चार पूर्ववर्ती विन्यास होते हैं। ऐसा इसलिए है, क्योंकि पूर्ववर्ती में, किसी भी दो लगातार कोशिकाओं में राज्यों का कोई संयोजन हो सकता है, लेकिन एक बार उन दो कोशिकाओं के राज्यों को चुना जाता है, तो शेष कोशिकाओं के राज्यों के लिए केवल एक सुसंगत विकल्प होता है। इसलिए, नियम 90 में कोई गार्डन ऑफ ईडन (सेलुलर ऑटोमेटन) नहीं है, एक कॉन्फ़िगरेशन जिसमें कोई पूर्ववर्ती नहीं है। नियम 90 के विन्यास में एक एकल अशून्य कक्ष (अन्य सभी कक्ष शून्य के साथ) शामिल है, जिसका कोई पूर्ववर्ती नहीं है जिसमें बहुत से अशून्य हैं। हालाँकि, यह कॉन्फ़िगरेशन ईडन गार्डन नहीं है क्योंकि इसमें असीमित संख्या में गैर शून्य वाले पूर्ववर्ती हैं।<ref name="skyum"/>

तथ्य यह है कि प्रत्येक कॉन्फ़िगरेशन में एक पूर्ववर्ती है, यह कहकर संक्षेप किया जा सकता है कि नियम 90 विशेषण कार्य है। फ़ंक्शन जो प्रत्येक कॉन्फ़िगरेशन को उसके उत्तराधिकारी के लिए मैप करता है, गणितीय रूप से एक विशेषण फ़ंक्शन है। नियम 90 भी अंतःक्षेपी फलन नहीं है। एक इंजेक्शन नियम में, प्रत्येक दो अलग-अलग कॉन्फ़िगरेशन में अलग-अलग उत्तराधिकारी होते हैं, लेकिन नियम 90 में एक ही उत्तराधिकारी के साथ कॉन्फ़िगरेशन के जोड़े होते हैं। नियम 90 एक सेलुलर automaton का एक उदाहरण प्रदान करता है जो विशेषण है लेकिन इंजेक्शन नहीं है। मूर और माइहिल के ईडन गार्डन (सेलुलर ऑटोमेटन) का अर्थ है कि प्रत्येक इंजेक्टिव सेलुलर ऑटोमेटन को विशेषण होना चाहिए, लेकिन यह उदाहरण दिखाता है कि बातचीत सच नहीं है।<ref name="skyum">{{citation|first=Sven|last=Skyum|title=Confusion in the Garden of Eden|journal=[[Proceedings of the American Mathematical Society]]|volume=50|issue=1|pages=332–336|year=1975|doi=10.1090/S0002-9939-1975-0386350-1|doi-access=free}}</ref><ref>{{citation|journal=Complex Systems|volume=5|year=1991|pages=19–30|title=De Bruijn Graphs and Linear Cellular Automata|first=Klaus|last=Sutner|url=http://www.complex-systems.com/pdf/05-1-3.pdf}}. {{harvtxt|Wolfram|2002}}, pp. 959–960. {{harvtxt|Martin|Odlyzko|Wolfram|1984}} provide a similar analysis of the predecessors of the same rule for finite sets of cells with periodic boundary conditions.</ref>