नियम 90: Difference between revisions

[[File:R090 rand 0.png|thumb|upright=1.35|यादृच्छिक प्रारंभिक स्थितियों के साथ नियम 90 का समय-स्थान आरेख। पिक्सेल की प्रत्येक पंक्ति ऑटोमेटन का एक विन्यास है; समय लंबवत रूप से ऊपर से नीचे की ओर बढ़ता है।]][[सेलुलर automaton]] के गणित के अध्ययन में, नियम 90 अनन्य या फ़ंक्शन के आधार पर एक [[प्राथमिक सेलुलर automaton]] है। इसमें कोशिकाओं की एक-आयामी सरणी होती है, जिनमें से प्रत्येक में 0 या 1 मान हो सकता है। प्रत्येक समय चरण में सभी मूल्यों को एक साथ अनन्य या उनके दो पड़ोसी मूल्यों द्वारा प्रतिस्थापित किया जाता है।<ref name="w83">{{citation|first=Stephen|last=Wolfram|authorlink=Stephen Wolfram|title=Statistical mechanics of cellular automata|journal=Reviews of Modern Physics|issue=3|volume=55|pages=601–644|year=1983|doi=10.1103/RevModPhys.55.601|url=http://www.stephenwolfram.com/publications/articles/ca/83-statistical/|bibcode=1983RvMP...55..601W}}.</ref> {{harvtxt|Martin|Odlyzko|Wolfram|1984}} इसे सरलतम गैर-तुच्छ सेलुलर ऑटोमेटन कहते हैं,<ref name="mow84">{{citation|first1=Olivier|last1=Martin|first2=Andrew M.|last2=Odlyzko|author2-link=Andrew Odlyzko|first3=Stephen|last3=Wolfram|author3-link=Stephen Wolfram|title=Algebraic properties of cellular automata|year=1984|journal=Communications in Mathematical Physics|pages=219–258|volume=93|issue=2|doi=10.1007/BF01223745|url=http://www.stephenwolfram.com/publications/articles/ca/84-properties/|bibcode = 1984CMaPh..93..219M |s2cid=6900060 }}.</ref> और [[स्टीफन वोल्फ्राम]] की 2002 की किताब [[एक नए तरह का विज्ञान]] में इसका विस्तार से वर्णन किया गया है।<ref>{{citation|first=Stephen|last=Wolfram|authorlink=Stephen Wolfram|title= A New Kind of Science|url=https://www.wolframscience.com/nks/|year=2002|publisher=Wolfram Media}}. The book's index lists over 50 distinct subtopics for Rule 90.</ref>

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

नियम 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"/>

! current pattern !! 111 !! 110 !! 101 !! 100 !! 011 !! 010 !! 001 !! 000

! new state for center cell

नियम 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>

=== Additivity, सुपरपोजिशन, और अपघटन ===

नियम 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>

नियम 90 के किसी भी प्रारंभिक विन्यास से, एक पेड़ (ग्राफ सिद्धांत) बना सकता है, एक [[निर्देशित अचक्रीय ग्राफ]] जिसमें प्रत्येक वर्टेक्स (ग्राफ सिद्धांत) में अधिकतम एक आउटगोइंग एज होता है, जिसके पेड़ मिलर के रूपक में पेड़ों के समान होते हैं। जंगल में प्रत्येक जोड़ी के लिए एक शीर्ष है {{math|(''x'',''i'')}} ऐसा वह सेल {{math|''x''}} समय पर अशून्य है {{math|''i''}}. समय 0 पर शीर्षों में कोई आउटगोइंग एज नहीं है; हर एक जंगल में एक पेड़ की जड़ बनाता है। प्रत्येक शीर्ष के लिए {{math|(''x'',''i'')}} साथ {{math|''i''}} अशून्य, इसका निवर्तमान किनारा जाता है {{math|(''x'' ± 1, ''i'' &minus; 1)}}, का अद्वितीय अशून्य पड़ोसी {{math|''x''}} समय चरण में {{math|''i'' &minus; 1}}. मिलर ने देखा कि ये जंगल त्रिकोणीय समाशोधन विकसित करते हैं, समय-स्थान आरेख के क्षेत्र जिनमें कोई गैर-शून्य कोशिकाएं एक सपाट तल किनारे और विकर्ण पक्षों से बंधी होती हैं। ऐसा समाशोधन तब बनता है जब कोशिकाओं का एक क्रमिक क्रम एक समय के चरण में एक साथ शून्य हो जाता है, और फिर (वृक्ष रूपक में) शाखाएं अंदर की ओर बढ़ती हैं, अंततः अनुक्रम की कोशिकाओं को फिर से ढक लेती हैं।<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>

इस प्रतिमान की प्रत्येक पंक्ति में जीवित कोशिकाओं की संख्या दो की शक्ति है। में {{math|''i''}}वीं पंक्ति, यह बराबर है {{math|2^''k''}}, कहाँ {{math|''k''}} संख्या की बाइनरी संख्या में गैर-शून्य अंकों की संख्या है{{math|''i''}}. जीवित कोशिकाओं की इन संख्याओं का क्रम,

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

नियम 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>