नियम 110

नियम 110 सेलुलर ऑटोमेटन (अक्सर इसे केवल नियम 110 कहा जाता है)स्थिरता और अराजकता के बीच की सीमा पर दिलचस्प व्यवहार वाला एक प्राथमिक सेलुलर ऑटोमेटन है। इस संबंध में, यह कॉनवे के गेम ऑफ लाइफ के समान है। जीवन की तरह, एक विशेष दोहराए जाने वाले पृष्ठभूमि पैटर्न के साथ नियम 110 को ट्यूरिंग पूर्णता के रूप में जाना जाता है। इसका तात्पर्य यह है कि, सिद्धांत रूप में, इस ऑटोमेटन का उपयोग करके किसी भी गणना या कंप्यूटर प्रोग्राम का अनुकरण किया जा सकता है।

नियम 110 सेलुलर ऑटोमेटन का एक उदाहरण

परिभाषा

एक प्राथमिक सेलुलर ऑटोमेटन में, 0s और 1s का एक आयामी पैटर्न नियमों के एक सरल सेट के अनुसार विकसित होता है। नई पीढ़ी में पैटर्न में कोई बिंदु 0 या 1 होगा या नहीं, यह उसके वर्तमान मूल्य के साथ-साथ उसके दो पड़ोसियों के मूल्य पर भी निर्भर करता है।

नियम 110 का उपयोग करते हुए 1डी सेल्युलर ऑटोमेटन के नियम अगली पीढ़ी को कैसे निर्धारित करते हैं, इसका एक एनीमेशन।

नियम 110 ऑटोमेटन में नियमों का निम्नलिखित सेट है:

Current pattern	111	110	101	100	011	010	001	000
New state for center cell	0	1	1	0	1	1	1	0

नियम 110 नाम इस तथ्य से लिया गया है कि इस नियम को बाइनरी अनुक्रम 01101110 में संक्षेपित किया जा सकता है; एक द्विआधारी संख्या के रूप में व्याख्या की गई, यह दशमलव मान 110 से मेल खाती है। यह वोल्फ्राम कोड नामकरण योजना है।

इतिहास

2004 में, मैथ्यू कुक ने एक प्रमाण प्रकाशित किया कि एक विशेष दोहराए जाने वाले पृष्ठभूमि पैटर्न के साथ नियम 110 ट्यूरिंग पूर्णता है, यानी, सार्वभौमिक गणना करने में सक्षम है, जिसे स्टीफन वोल्फ्राम ने 1985 में अनुमान लगाया था। कुक ने वोल्फ्राम की पुस्तक एक नए तरह का विज्ञान के प्रकाशन से पहले सांता फ़े संस्थान सम्मेलन CA98 में अपना प्रमाण प्रस्तुत किया। इसके परिणामस्वरूप वोल्फ्राम अनुसंधान के साथ एक गैर-प्रकटीकरण समझौते पर आधारित कानूनी मामला सामने आया। वोल्फ्राम रिसर्च ने कई वर्षों तक कुक के प्रमाण के प्रकाशन को अवरुद्ध कर दिया।

रोचक गुण

प्राथमिक सेलुलर ऑटोमेटन#प्रतिबिंब और पूरकों में, नियम 110 एकमात्र ऐसा है जिसके लिए ट्यूरिंग पूर्णता सीधे तौर पर सिद्ध की गई है, हालांकि कई समान नियमों के प्रमाण सरल परिणाम के रूप में अनुसरण करते हैं (उदाहरण के लिए नियम 124, जो नियम 110 का क्षैतिज प्रतिबिंब है)। नियम 110 संभवतः सबसे सरल ज्ञात ट्यूरिंग पूर्ण प्रणाली है। नियम 110, कॉनवे के गेम ऑफ लाइफ की तरह, स्टीफन वोल्फ्राम को सेल्युलर ऑटोमेटन#क्लासिफिकेशन व्यवहार कहते हैं, जो न तो पूरी तरह से स्थिर है और न ही पूरी तरह से अराजक है। स्थानीयकृत संरचनाएँ जटिल तरीकों से प्रकट होती हैं और परस्पर क्रिया करती हैं। मैथ्यू कुक ने टैग सिस्टम#साइक्लिक टैग सिस्टम, फिर 2-टैग सिस्टम#साइक्लिक टैग सिस्टम और फिर ट्यूरिंग मशीनों का क्रमिक अनुकरण करके नियम 110 को सार्वभौमिक गणना का समर्थन करने में सक्षम साबित किया। अंतिम चरण में समय जटिलता#घातीय समय ओवरहेड है क्योंकि ट्यूरिंग मशीन का टेप एक यूनरी अंक प्रणाली के साथ एन्कोड किया गया है। नियरी और वुड्स (2006) ने एक अलग निर्माण प्रस्तुत किया जो 2-टैग सिस्टम को क्लॉकवाइज ट्यूरिंग मशीनों से बदल देता है और इसमें बहुपद जटिलता ओवरहेड होती है।

सार्वभौमिकता का प्रमाण

मैथ्यू कुक ने ए न्यू काइंड ऑफ साइंस के प्रकाशन से पहले आयोजित सांता फ़े इंस्टीट्यूट सम्मेलन में नियम 110 की सार्वभौमिकता का प्रमाण प्रस्तुत किया। वोल्फ्राम रिसर्च ने दावा किया कि इस प्रस्तुति ने अपने नियोक्ता के साथ कुक के गैर-प्रकटीकरण समझौते का उल्लंघन किया, और प्रकाशित सम्मेलन की कार्यवाही से कुक के पेपर को बाहर करने का एक अदालती आदेश प्राप्त किया। कुक के प्रमाण का अस्तित्व फिर भी ज्ञात हो गया। उनके प्रमाण में रुचि इसके परिणाम से उतनी अधिक नहीं थी जितनी इसके तरीकों से, विशेष रूप से इसके निर्माण के तकनीकी विवरण से। कुक के प्रमाण का चरित्र ए न्यू काइंड ऑफ साइंस में नियम 110 की चर्चा से काफी भिन्न है। कुक ने तब से अपना पूरा सबूत बताते हुए एक पेपर लिखा है।

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

नियम 110 में अंतरिक्ष यान

नियम 110 में सार्वभौमिक मशीन के कार्य के लिए असीमित रूप से दोहराए जाने वाले पृष्ठभूमि पैटर्न के भीतर एक सीमित संख्या में स्थानीयकृत पैटर्न को एम्बेड करने की आवश्यकता होती है। पृष्ठभूमि पैटर्न चौदह सेल चौड़ा है और हर सात पुनरावृत्तियों में खुद को दोहराता है। पैटर्न 00010011011111 है.

नियम 110 सार्वभौमिक मशीन में तीन स्थानीयकृत पैटर्न विशेष महत्व के हैं। उन्हें नीचे दी गई छवि में दिखाया गया है, जो दोहराए जाने वाले पृष्ठभूमि पैटर्न से घिरा हुआ है। सबसे बायीं ओर की संरचना दाहिनी दो कोशिकाओं में स्थानांतरित हो जाती है और हर तीन पीढ़ियों में दोहराई जाती है। इसमें अनुक्रम 0001110111 शामिल है जो ऊपर दिए गए पृष्ठभूमि पैटर्न से घिरा हुआ है, साथ ही इस अनुक्रम के दो अलग-अलग विकास भी शामिल हैं।

आंकड़ों में, समय ऊपर से नीचे तक बीतता है: शीर्ष रेखा प्रारंभिक स्थिति का प्रतिनिधित्व करती है, और प्रत्येक अगली पंक्ति अगली बार की स्थिति का प्रतिनिधित्व करती है।

केंद्र संरचना आठ कोशिकाओं के बाईं ओर बदलती है और हर तीस पीढ़ियों में दोहराई जाती है। इसमें ऊपर दिए गए पृष्ठभूमि पैटर्न से घिरा अनुक्रम 1001111, साथ ही इस अनुक्रम के उनतीस अलग-अलग विकास शामिल हैं।

सबसे दाहिनी संरचना स्थिर रहती है और हर सात पीढ़ियों में दोहराई जाती है। इसमें ऊपर दिए गए पृष्ठभूमि पैटर्न से घिरा अनुक्रम 111, साथ ही इस अनुक्रम के पांच अलग-अलग विकास शामिल हैं।

नीचे एक छवि दी गई है जिसमें पहली दो संरचनाएं बिना अनुवाद के (बाएं) एक-दूसरे से गुजरते हुए और तीसरी संरचना (दाएं) बनाने के लिए बातचीत करते हुए दिखाई दे रही हैं।

नियम 110 में कई अन्य अंतरिक्ष यान हैं, लेकिन वे सार्वभौमिकता प्रमाण में प्रमुखता से शामिल नहीं हैं।

चक्रीय टैग प्रणाली का निर्माण

चक्रीय टैग सिस्टम मशीनरी के तीन मुख्य घटक हैं:

• एक डेटा स्ट्रिंग जो स्थिर है;
• परिमित उत्पादन नियमों की एक अनंत रूप से दोहराई जाने वाली श्रृंखला जो दाईं ओर शुरू होती है और बाईं ओर चलती है;
• घड़ी की धड़कनों की एक अनंत रूप से दोहराई जाने वाली श्रृंखला जो बाईं ओर से शुरू होती है और दाईं ओर चलती है।

इन घटकों के बीच प्रारंभिक अंतर अत्यंत महत्वपूर्ण है। सेलुलर ऑटोमेटन के लिए चक्रीय टैग प्रणाली को लागू करने के लिए, ऑटोमेटन की प्रारंभिक स्थितियों को सावधानीपूर्वक चुना जाना चाहिए ताकि उसमें मौजूद विभिन्न स्थानीय संरचनाएं उच्च क्रमबद्ध तरीके से बातचीत कर सकें।

चक्रीय टैग प्रणाली में डेटा स्ट्रिंग को ऊपर दिखाए गए प्रकार की स्थिर दोहराई जाने वाली संरचनाओं की एक श्रृंखला द्वारा दर्शाया गया है। इन संरचनाओं के बीच क्षैतिज स्थान की अलग-अलग मात्रा 1 प्रतीकों को 0 प्रतीकों से अलग करने का काम करती है। ये प्रतीक उस शब्द का प्रतिनिधित्व करते हैं जिस पर चक्रीय टैग प्रणाली चल रही है, और प्रत्येक उत्पादन नियम पर विचार करने पर पहला ऐसा प्रतीक नष्ट हो जाता है। जब यह अग्रणी प्रतीक 1 होता है, तो स्ट्रिंग के अंत में नए प्रतीक जोड़े जाते हैं; जब यह 0 होता है, तो कोई नया प्रतीक नहीं जोड़ा जाता है। इसे प्राप्त करने का तंत्र नीचे वर्णित है।

दाईं ओर से प्रवेश करने पर ऊपर दिखाए गए प्रकार की बाईं ओर चलने वाली संरचनाओं की एक श्रृंखला होती है, जो क्षैतिज स्थान की अलग-अलग मात्रा से अलग होती हैं। चक्रीय टैग प्रणाली के उत्पादन नियमों में 0s और 1s का प्रतिनिधित्व करने के लिए इन संरचनाओं की बड़ी संख्या को विभिन्न रिक्तियों के साथ जोड़ा जाता है। क्योंकि टैग सिस्टम के उत्पादन नियम प्रोग्राम के निर्माण के समय ज्ञात होते हैं, और अनंत रूप से दोहराए जाने वाले, प्रारंभिक स्थिति में 0s और 1s के पैटर्न को एक अनंत रूप से दोहराई जाने वाली स्ट्रिंग द्वारा दर्शाया जा सकता है। प्रत्येक उत्पादन नियम को अगले नियम से एक अन्य संरचना द्वारा अलग किया जाता है जिसे नियम विभाजक (या ब्लॉक विभाजक) के रूप में जाना जाता है, जो उत्पादन नियमों के एन्कोडिंग के समान दर से बाईं ओर बढ़ता है।

जब बाईं ओर चलने वाला नियम विभाजक चक्रीय टैग सिस्टम के डेटा स्ट्रिंग में एक स्थिर प्रतीक का सामना करता है, तो यह उसके सामने आने वाले पहले प्रतीक को नष्ट कर देता है। हालाँकि, इसका बाद का व्यवहार इस पर निर्भर करता है कि स्ट्रिंग द्वारा एन्कोड किया गया प्रतीक 0 था या 1। यदि 0 है, तो नियम विभाजक एक नई संरचना में बदल जाता है जो आने वाले उत्पादन नियम को अवरुद्ध कर देता है। यह नई संरचना तब नष्ट हो जाती है जब इसका सामना अगले नियम विभाजक से होता है।

दूसरी ओर, यदि स्ट्रिंग में प्रतीक 1 था, तो नियम विभाजक एक नई संरचना में बदल जाता है जो आने वाले उत्पादन नियम को स्वीकार करता है। यद्यपि नई संरचना अगले नियम विभाजक का सामना करने पर फिर से नष्ट हो जाती है, यह पहले संरचनाओं की एक श्रृंखला को बाईं ओर से गुजरने की अनुमति देती है। फिर इन संरचनाओं को चक्रीय टैग सिस्टम की डेटा स्ट्रिंग के अंत में जोड़ने के लिए बनाया जाता है। यह अंतिम परिवर्तन ऊपर दिखाए गए दाहिनी ओर चलने वाले पैटर्न में अनंत रूप से दोहराई जाने वाली, दाहिनी ओर चलने वाली घड़ी की दालों की एक श्रृंखला के माध्यम से पूरा किया जाता है। घड़ी की दालें उत्पादन नियम से आने वाले बाईं ओर चलने वाले 1 प्रतीकों को डेटा स्ट्रिंग के स्थिर 1 प्रतीकों में बदल देती हैं, और उत्पादन नियम से आने वाले 0 प्रतीकों को डेटा स्ट्रिंग के स्थिर 0 प्रतीकों में बदल देती हैं।

चक्रीय टैग प्रणाली काम कर रही है

File:Cts-diagram.jpgउपरोक्त चित्र नियम 110 में चक्रीय टैग प्रणाली के पुनर्निर्माण का योजनाबद्ध आरेख है।

यह भी देखें

• नियम 30
• नियम 90
• नियम 184

संदर्भ

उद्धृत कार्य

• Cook, Matthew (2004). "प्राथमिक सेलुलर ऑटोमेटा में सार्वभौमिकता" (PDF). Complex Systems. 15: 1–40.
• Giles, Jim (2002). "यह कैसा विज्ञान है?". Nature. 417 (6886): 216–218. Bibcode:2002Natur.417..216G. doi:10.1038/417216a. PMID 12015565. S2CID 10636328.
• Neary, Turlough; Woods, Damien (2006). "P-completeness of cellular automaton Rule 110". In Bugliesi, Michele; Preneel, Bart; Sassone, Vladimiro; Wegener, Ingo (eds.). ऑटोमेटा, भाषाएँ और प्रोग्रामिंग: 33वीं अंतर्राष्ट्रीय संगोष्ठी, आईसीएएलपी 2006, वेनिस, इटली, 10-14 जुलाई, 2006, कार्यवाही, भाग I. Lecture Notes in Computer Science. Vol. 4051. Springer. pp. 132–143. doi:10.1007/11786986_13.
• Wolfram, Stephen (2002). एक नए तरह का विज्ञान. Wolfram Media. ISBN 1-57955-008-8.

अग्रिम पठन

• Cook, Matthew (2008). "A Concrete View of Rule 110 Computation". In Neary, T.; Woods, D.; Seda, A. K.; Murphy, N. (eds.). The Complexity of Simple Programs. pp. 31–55. arXiv:0906.3248v1. doi:10.4204/EPTCS.1.4. S2CID 10266058. {{cite book}}: |journal= ignored (help)
• Martínez, Genaro J.; Adamatzky, A.; Chen, Fangyue; Chua, Leon (2012). "On Soliton Collisions between Localizations in Complex Elementary Cellular Automata: Rules 54 and 110 and Beyond". 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). "Cellular automaton supercolliders". Int. J. Mod. Phys. C. 22 (4): 419–439. arXiv:1105.4332. Bibcode:2011IJMPC..22..419M. doi:10.1142/S0129183111016348. S2CID 7508070.
• Martínez, Genaro J.; McIntosh, Harold V.; Mora, Juan C.S.T.; Vergara, Sergio V.C. (2003–2008). "Reproducing the cyclic tag systems developed by Matthew Cook with Rule 110 using the phases fi_1" (PDF). Journal of Cellular Automata. 6 (2–3): 121–161.
• Martínez, Genaro J.; McIntosh, Harold V.; Mora, Juan C.S.T.; Vergara, Sergio V.C. (2008). "Determining a regular language by glider-based structures called phases fi_1 in Rule 110". Journal of Cellular Automata. 3 (3): 231–270. arXiv:0706.3348v1. Bibcode:2007arXiv0706.3348J.
• Martínez, Genaro J.; McIntosh, Harold V.; Mora, Juan C.S.T.; Vergara, Sergio V.C. (2007). "Rule 110 objects and other constructions based-collisions" (PDF). Journal of Cellular Automata. 2 (3): 219–242.
• Martínez, Genaro J.; McIntosh, Harold V.; Mora, Juan C.S.T. (2006). "Gliders in Rule 110" (PDF). Int. J. Of Unconventional Computing. 2: 1–49.
• Martínez, Genaro J.; McIntosh, Harold V.; Mora, Juan C.S.T. (2003). "Production of gliders by collisions in Rule 110" (PDF). Lecture Notes in Computer Science. 2801: 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: Collisions of gliders as phases of ether in rule 110".
• McIntosh, Harold V. (1999). "Rule 110 as it relates to the presence of gliders" (PDF).
• McIntosh, Harold V. (2002). "Rule 110 Is Universal!" (PDF).

बाहरी संबंध

• Rule 110 — from Wolfram MathWorld
• Rule 110 in Wolfram's atlas of cellular automata
• Rule 110 repository
• Marble-based mechanical implementation of a 4-bit Rule 110 computer