नियम 110: Difference between revisions
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
{{short description|Elementary cellular automaton}}नियम 110 सेलुलर ऑटोमेटन ( | {{short description|Elementary cellular automaton}}नियम 110 सेलुलर ऑटोमेटन (अधिकांश इसे केवल नियम 110 कहा जाता है){{efn|'''110''' is the [[number 110]], written in conventional decimal notation, and thus is pronounced [[english numeral | as one pronounces]] [[nominal numbers]] ordinarily. For example, [[Stephen Wolfram]] pronounces the name "rule one-ten".<ref>{{cite AV media |people=Stephen Wolfram |publisher=University of California Television (UCTV) |title=A New Kind of Science - Stephen Wolfram |url=https://www.youtube.com/watch?v=_eC14GonZnU&t=9m51s |access-date=2023-06-19 |language=en |year=2003 |time=9:51}}</ref>}}स्थिरता और अराजकता के मध्य की सीमा पर रोचक व्यवहार वाला [[प्राथमिक सेलुलर ऑटोमेटन]] है। इस संबंध में, यह कॉनवे के गेम ऑफ लाइफ के समान है। जीवन की तरह, विशेष दोहराए जाने वाले पृष्ठभूमि पैटर्न के साथ नियम 110 को [[ट्यूरिंग पूर्णता]] के रूप में जाना जाता है।{{sfnp|Cook|2004}} इसका तात्पर्य यह है कि, सिद्धांत रूप में, इस ऑटोमेटन का उपयोग करके किसी भी गणना या कंप्यूटर प्रोग्राम का अनुकरण किया जा सकता है। | ||
[[File:CA rule110s.png|thumb|नियम 110 सेलुलर ऑटोमेटन का उदाहरण]] | [[File:CA rule110s.png|thumb|नियम 110 सेलुलर ऑटोमेटन का उदाहरण]] | ||
==परिभाषा== | ==परिभाषा== | ||
प्राथमिक सेलुलर ऑटोमेटन में, 0s और 1s का आयामी पैटर्न नियमों के सरल | प्राथमिक सेलुलर ऑटोमेटन में, 0s और 1s का आयामी पैटर्न नियमों के सरल समूह के अनुसार विकसित होता है। नई पीढ़ी में पैटर्न में कोई बिंदु 0 या 1 होगा या नहीं, यह उसके वर्तमान मूल्य के साथ-साथ उसके दो पड़ोसियों के मूल्य पर भी निर्भर करता है। | ||
[[File:One-d-cellular-automaton-rule-110.gif|thumb|नियम 110 का उपयोग करते हुए 1डी सेल्युलर ऑटोमेटन के नियम अगली पीढ़ी को कैसे निर्धारित करते हैं, इसका एनीमेशन।]]नियम 110 ऑटोमेटन में नियमों का निम्नलिखित | [[File:One-d-cellular-automaton-rule-110.gif|thumb|नियम 110 का उपयोग करते हुए 1डी सेल्युलर ऑटोमेटन के नियम अगली पीढ़ी को कैसे निर्धारित करते हैं, इसका एनीमेशन।]]नियम 110 ऑटोमेटन में नियमों का निम्नलिखित समूह है: | ||
{| class="wikitable" style="text-align: center" | {| class="wikitable" style="text-align: center" | ||
| Line 32: | Line 32: | ||
==इतिहास== | ==इतिहास== | ||
2004 में, [[मैथ्यू कुक]] ने प्रमाण प्रकाशित किया कि विशेष दोहराए जाने वाले पृष्ठभूमि पैटर्न के साथ नियम 110 ट्यूरिंग पूर्णता है, | 2004 में, [[मैथ्यू कुक]] ने प्रमाण प्रकाशित किया कि विशेष दोहराए जाने वाले पृष्ठभूमि पैटर्न के साथ नियम 110 ट्यूरिंग पूर्णता है, अर्थात्, सार्वभौमिक गणना करने में सक्षम है, जिसे [[स्टीफन वोल्फ्राम]] ने 1985 में अनुमान लगाया था।{{sfnp|Cook|2004}} कुक ने वोल्फ्राम की पुस्तक [[एक नए तरह का विज्ञान|नए तरह का विज्ञान]] के प्रकाशन से पहले [[सांता फ़े संस्थान]] सम्मेलन CA98 में अपना प्रमाण प्रस्तुत किया। इसके परिणामस्वरूप [[ वोल्फ्राम अनुसंधान ]] के साथ गैर-प्रकटीकरण समझौते पर आधारित नियमबद्ध स्थिति सामने आया।<ref>[https://www.courtlistener.com/docket/4155086/wolfram-research-inc-v-cook/ Wolfram Research Inc v. Cook (2:00-cv-09357)] (sometimes cited as "Wolfram Research Inc. v. Matthew Cook. 8/31 CV00-9357 CBM")</ref> वोल्फ्राम रिसर्च ने अनेक वर्षों तक कुक के प्रमाण के प्रकाशन को अवरुद्ध कर दिया।{{sfnp|Giles|2002}} | ||
==रोचक गुण== | ==रोचक गुण== | ||
प्राथमिक सेलुलर ऑटोमेटन#प्रतिबिंब और पूरकों में, नियम 110 एकमात्र ऐसा है जिसके लिए ट्यूरिंग पूर्णता सीधे तौर पर सिद्ध की गई है, | प्राथमिक सेलुलर ऑटोमेटन#प्रतिबिंब और पूरकों में, नियम 110 एकमात्र ऐसा है जिसके लिए ट्यूरिंग पूर्णता सीधे तौर पर सिद्ध की गई है, चूंकि अनेक समान नियमों के प्रमाण सरल परिणाम के रूप में अनुसरण करते हैं (उदाहरण के लिए नियम 124, जो नियम 110 का क्षैतिज प्रतिबिंब है)। नियम 110 संभवतः सबसे सरल ज्ञात ट्यूरिंग पूर्ण प्रणाली है।{{sfnp|Cook|2004}}<ref>{{harvp|Wolfram|2002|pp=169, 675–691}}</ref> | ||
नियम 110, कॉनवे के गेम ऑफ लाइफ की तरह, स्टीफन वोल्फ्राम को सेल्युलर ऑटोमेटन#क्लासिफिकेशन व्यवहार कहते हैं, जो न | नियम 110, कॉनवे के गेम ऑफ लाइफ की तरह, स्टीफन वोल्फ्राम को सेल्युलर ऑटोमेटन#क्लासिफिकेशन व्यवहार कहते हैं, जो न तब पूरी तरह से स्थिर है और न ही पूरी तरह से अराजक है। स्थानीयकृत संरचनाएँ जटिल विधियों से प्रकट होती हैं और परस्पर क्रिया करती हैं।<ref>{{harvp|Wolfram|2002|p=229}}</ref> | ||
मैथ्यू कुक ने टैग | मैथ्यू कुक ने टैग प्रणाली#साइक्लिक टैग प्रणाली, फिर 2-टैग प्रणाली#साइक्लिक टैग प्रणाली और फिर [[ट्यूरिंग मशीन]]ों का क्रमिक अनुकरण करके नियम 110 को सार्वभौमिक गणना का समर्थन करने में सक्षम सिद्ध किया। अंतिम चरण में समय जटिलता#घातीय समय ओवरहेड है क्योंकि ट्यूरिंग मशीन का टेप यूनरी अंक प्रणाली के साथ एन्कोड किया गया है। नियरी और वुड्स (2006) ने अलग निर्माण प्रस्तुत किया जो 2-टैग प्रणाली को क्लॉकवाइज ट्यूरिंग मशीनों से बदल देता है और इसमें [[बहुपद जटिलता]] ओवरहेड होती है।{{sfnp|Neary|Woods|2006}} | ||
==सार्वभौमिकता का प्रमाण== | ==सार्वभौमिकता का प्रमाण== | ||
मैथ्यू कुक ने ए न्यू काइंड ऑफ साइंस के प्रकाशन से पहले आयोजित सांता फ़े इंस्टीट्यूट सम्मेलन में नियम 110 की सार्वभौमिकता का प्रमाण प्रस्तुत किया। वोल्फ्राम रिसर्च ने | मैथ्यू कुक ने ए न्यू काइंड ऑफ साइंस के प्रकाशन से पहले आयोजित सांता फ़े इंस्टीट्यूट सम्मेलन में नियम 110 की सार्वभौमिकता का प्रमाण प्रस्तुत किया। वोल्फ्राम रिसर्च ने प्रमाणित किया कि इस प्रस्तुति ने अपने नियोक्ता के साथ कुक के गैर-प्रकटीकरण समझौते का उल्लंघन किया, और प्रकाशित सम्मेलन की कार्यवाही से कुक के पेपर को बाहर करने का अदालती आदेश प्राप्त किया। कुक के प्रमाण का अस्तित्व फिर भी ज्ञात हो गया। उनके प्रमाण में रुचि इसके परिणाम से उतनी अधिक नहीं थी जितनी इसके विधियों से, विशेष रूप से इसके निर्माण के विधिी विवरण से।<ref>{{Cite journal | ||
| last1 = Martinez | | last1 = Martinez | ||
| first1 = Genaro J. | | first1 = Genaro J. | ||
| Line 60: | Line 60: | ||
| issue = 2 | | issue = 2 | ||
| s2cid = 150262966 | | s2cid = 150262966 | ||
}}</ref> कुक के प्रमाण का चरित्र ए न्यू काइंड ऑफ साइंस में नियम 110 की चर्चा से | }}</ref> कुक के प्रमाण का चरित्र ए न्यू काइंड ऑफ साइंस में नियम 110 की चर्चा से अधिक भिन्न है। कुक ने तब से अपना पूरा प्रमाण बताते हुए पेपर लिखा है।{{sfnp|Cook|2004}} | ||
कुक ने | कुक ने सिद्ध कर दिया कि नियम 110 सार्वभौमिक (या ट्यूरिंग पूर्ण) था, यह दिखाकर कि नियम का उपयोग किसी अन्य कम्प्यूटेशनल मॉडल, चक्रीय टैग प्रणाली का अनुकरण करना संभव था, जिसे सार्वभौमिक माना जाता है। उन्होंने सबसे पहले अनेक [[ अंतरिक्ष यान (सीए) ]] को अलग किया, जो स्व-स्थायी स्थानीयकृत पैटर्न थे, जिनका निर्माण नियम 110 ब्रह्मांड में अनंत रूप से दोहराए जाने वाले पैटर्न पर किया जा सकता था। फिर उन्होंने इन संरचनाओं के संयोजन के लिए इस तरह से बातचीत करने का विधि तैयार किया जिसका उपयोग गणना के लिए किया जा सके। | ||
===नियम 110 में अंतरिक्ष यान=== | ===नियम 110 में अंतरिक्ष यान=== | ||
नियम 110 में सार्वभौमिक मशीन के कार्य के लिए असीमित रूप से दोहराए जाने वाले पृष्ठभूमि पैटर्न के | नियम 110 में सार्वभौमिक मशीन के कार्य के लिए असीमित रूप से दोहराए जाने वाले पृष्ठभूमि पैटर्न के अन्दर सीमित संख्या में स्थानीयकृत पैटर्न को एम्बेड करने की आवश्यकता होती है। पृष्ठभूमि पैटर्न चौदह सेल चौड़ा है और हर सात पुनरावृत्तियों में खुद को दोहराता है। पैटर्न 00010011011111 है. | ||
नियम 110 सार्वभौमिक मशीन में तीन स्थानीयकृत पैटर्न विशेष महत्व के हैं। उन्हें नीचे दी गई छवि में दिखाया गया है, जो दोहराए जाने वाले पृष्ठभूमि पैटर्न से घिरा हुआ है। सबसे बायीं ओर की संरचना दाहिनी दो कोशिकाओं में स्थानांतरित हो जाती है और हर तीन पीढ़ियों में दोहराई जाती है। इसमें अनुक्रम 0001110111 | नियम 110 सार्वभौमिक मशीन में तीन स्थानीयकृत पैटर्न विशेष महत्व के हैं। उन्हें नीचे दी गई छवि में दिखाया गया है, जो दोहराए जाने वाले पृष्ठभूमि पैटर्न से घिरा हुआ है। सबसे बायीं ओर की संरचना दाहिनी दो कोशिकाओं में स्थानांतरित हो जाती है और हर तीन पीढ़ियों में दोहराई जाती है। इसमें अनुक्रम 0001110111 सम्मिलित है जो ऊपर दिए गए पृष्ठभूमि पैटर्न से घिरा हुआ है, साथ ही इस अनुक्रम के दो अलग-अलग विकास भी सम्मिलित हैं। | ||
आंकड़ों में, समय ऊपर से नीचे तक बीतता है: शीर्ष रेखा प्रारंभिक स्थिति का प्रतिनिधित्व करती है, और प्रत्येक अगली पंक्ति अगली बार की स्थिति का प्रतिनिधित्व करती है। | आंकड़ों में, समय ऊपर से नीचे तक बीतता है: शीर्ष रेखा प्रारंभिक स्थिति का प्रतिनिधित्व करती है, और प्रत्येक अगली पंक्ति अगली बार की स्थिति का प्रतिनिधित्व करती है। | ||
[[Image:ca110-structures2.png]]केंद्र संरचना आठ कोशिकाओं के बाईं ओर बदलती है और हर तीस पीढ़ियों में दोहराई जाती है। इसमें ऊपर दिए गए पृष्ठभूमि पैटर्न से घिरा अनुक्रम 1001111, साथ ही इस अनुक्रम के उनतीस अलग-अलग विकास | [[Image:ca110-structures2.png]]केंद्र संरचना आठ कोशिकाओं के बाईं ओर बदलती है और हर तीस पीढ़ियों में दोहराई जाती है। इसमें ऊपर दिए गए पृष्ठभूमि पैटर्न से घिरा अनुक्रम 1001111, साथ ही इस अनुक्रम के उनतीस अलग-अलग विकास सम्मिलित हैं। | ||
सबसे दाहिनी संरचना स्थिर रहती है और हर सात पीढ़ियों में दोहराई जाती है। इसमें ऊपर दिए गए पृष्ठभूमि पैटर्न से घिरा अनुक्रम 111, साथ ही इस अनुक्रम के पांच अलग-अलग विकास | सबसे दाहिनी संरचना स्थिर रहती है और हर सात पीढ़ियों में दोहराई जाती है। इसमें ऊपर दिए गए पृष्ठभूमि पैटर्न से घिरा अनुक्रम 111, साथ ही इस अनुक्रम के पांच अलग-अलग विकास सम्मिलित हैं। | ||
नीचे छवि दी गई है जिसमें पहली दो संरचनाएं बिना अनुवाद के (बाएं) एक-दूसरे से | नीचे छवि दी गई है जिसमें पहली दो संरचनाएं बिना अनुवाद के (बाएं) एक-दूसरे से निकलते हुए और तीसरी संरचना (दाएं) बनाने के लिए बातचीत करते हुए दिखाई दे रही हैं। | ||
[[Image:ca110-interaction2.png]]नियम 110 में | [[Image:ca110-interaction2.png]]नियम 110 में अनेक अन्य अंतरिक्ष यान हैं, किन्तु वे सार्वभौमिकता प्रमाण में प्रमुखता से सम्मिलित नहीं हैं। | ||
===चक्रीय टैग प्रणाली का निर्माण=== | ===चक्रीय टैग प्रणाली का निर्माण=== | ||
चक्रीय टैग | चक्रीय टैग प्रणाली मशीनरी के तीन मुख्य घटक हैं: | ||
* डेटा स्ट्रिंग जो स्थिर है; | * डेटा स्ट्रिंग जो स्थिर है; | ||
* परिमित उत्पादन नियमों की अनंत रूप से दोहराई जाने वाली श्रृंखला जो दाईं ओर | * परिमित उत्पादन नियमों की अनंत रूप से दोहराई जाने वाली श्रृंखला जो दाईं ओर प्रारंभ होती है और बाईं ओर चलती है; | ||
* घड़ी की धड़कनों की अनंत रूप से दोहराई जाने वाली श्रृंखला जो बाईं ओर से | * घड़ी की धड़कनों की अनंत रूप से दोहराई जाने वाली श्रृंखला जो बाईं ओर से प्रारंभ होती है और दाईं ओर चलती है। | ||
इन घटकों के | इन घटकों के मध्य प्रारंभिक अंतर अत्यंत महत्वपूर्ण है। सेलुलर ऑटोमेटन के लिए चक्रीय टैग प्रणाली को प्रायुक्त करने के लिए, ऑटोमेटन की प्रारंभिक स्थितियों को सावधानीपूर्वक चुना जाना चाहिए जिससे उसमें उपस्थित विभिन्न स्थानीय संरचनाएं उच्च क्रमबद्ध विधियां से बातचीत कर सकें। | ||
चक्रीय टैग प्रणाली में डेटा स्ट्रिंग को ऊपर दिखाए गए प्रकार की स्थिर दोहराई जाने वाली संरचनाओं की श्रृंखला द्वारा दर्शाया गया है। इन संरचनाओं के | चक्रीय टैग प्रणाली में डेटा स्ट्रिंग को ऊपर दिखाए गए प्रकार की स्थिर दोहराई जाने वाली संरचनाओं की श्रृंखला द्वारा दर्शाया गया है। इन संरचनाओं के मध्य क्षैतिज स्थान की अलग-अलग मात्रा 1 प्रतीकों को 0 प्रतीकों से अलग करने का काम करती है। ये प्रतीक उस शब्द का प्रतिनिधित्व करते हैं जिस पर चक्रीय टैग प्रणाली चल रही है, और प्रत्येक उत्पादन नियम पर विचार करने पर पहला ऐसा प्रतीक नष्ट हो जाता है। जब यह अग्रणी प्रतीक 1 होता है, तब स्ट्रिंग के अंत में नए प्रतीक जोड़े जाते हैं; जब यह 0 होता है, तब कोई नया प्रतीक नहीं जोड़ा जाता है। इसे प्राप्त करने का तंत्र नीचे वर्णित है। | ||
दाईं ओर से प्रवेश करने पर ऊपर दिखाए गए प्रकार की बाईं ओर चलने वाली संरचनाओं की श्रृंखला होती है, जो क्षैतिज स्थान की अलग-अलग मात्रा से अलग होती हैं। चक्रीय टैग प्रणाली के उत्पादन नियमों में 0s और 1s का प्रतिनिधित्व करने के लिए इन संरचनाओं की बड़ी संख्या को विभिन्न रिक्तियों के साथ जोड़ा जाता है। क्योंकि टैग | दाईं ओर से प्रवेश करने पर ऊपर दिखाए गए प्रकार की बाईं ओर चलने वाली संरचनाओं की श्रृंखला होती है, जो क्षैतिज स्थान की अलग-अलग मात्रा से अलग होती हैं। चक्रीय टैग प्रणाली के उत्पादन नियमों में 0s और 1s का प्रतिनिधित्व करने के लिए इन संरचनाओं की बड़ी संख्या को विभिन्न रिक्तियों के साथ जोड़ा जाता है। क्योंकि टैग प्रणाली के उत्पादन नियम प्रोग्राम के निर्माण के समय ज्ञात होते हैं, और अनंत रूप से दोहराए जाने वाले, प्रारंभिक स्थिति में 0s और 1s के पैटर्न को अनंत रूप से दोहराई जाने वाली स्ट्रिंग द्वारा दर्शाया जा सकता है। प्रत्येक उत्पादन नियम को अगले नियम से अन्य संरचना द्वारा अलग किया जाता है जिसे नियम विभाजक (या ब्लॉक विभाजक) के रूप में जाना जाता है, जो उत्पादन नियमों के एन्कोडिंग के समान दर से बाईं ओर बढ़ता है। | ||
जब बाईं ओर चलने वाला नियम विभाजक चक्रीय टैग | जब बाईं ओर चलने वाला नियम विभाजक चक्रीय टैग प्रणाली के डेटा स्ट्रिंग में स्थिर प्रतीक का सामना करता है, तब यह उसके सामने आने वाले पहले प्रतीक को नष्ट कर देता है। चूँकि, इसका पश्चात का व्यवहार इस पर निर्भर करता है कि स्ट्रिंग द्वारा एन्कोड किया गया प्रतीक 0 था या 1। यदि 0 है, तब नियम विभाजक नई संरचना में बदल जाता है जो आने वाले उत्पादन नियम को अवरुद्ध कर देता है। यह नई संरचना तब नष्ट हो जाती है जब इसका सामना अगले नियम विभाजक से होता है। | ||
दूसरी ओर, यदि स्ट्रिंग में प्रतीक 1 था, | दूसरी ओर, यदि स्ट्रिंग में प्रतीक 1 था, तब नियम विभाजक नई संरचना में बदल जाता है जो आने वाले उत्पादन नियम को स्वीकार करता है। यद्यपि नई संरचना अगले नियम विभाजक का सामना करने पर फिर से नष्ट हो जाती है, यह पहले संरचनाओं की श्रृंखला को बाईं ओर से निकलने की अनुमति देती है। फिर इन संरचनाओं को चक्रीय टैग प्रणाली की डेटा स्ट्रिंग के अंत में जोड़ने के लिए बनाया जाता है। यह अंतिम परिवर्तन ऊपर दिखाए गए दाहिनी ओर चलने वाले पैटर्न में अनंत रूप से दोहराई जाने वाली, दाहिनी ओर चलने वाली घड़ी की दालों की श्रृंखला के माध्यम से पूरा किया जाता है। घड़ी की दालें उत्पादन नियम से आने वाले बाईं ओर चलने वाले 1 प्रतीकों को डेटा स्ट्रिंग के स्थिर 1 प्रतीकों में बदल देती हैं, और उत्पादन नियम से आने वाले 0 प्रतीकों को डेटा स्ट्रिंग के स्थिर 0 प्रतीकों में बदल देती हैं। | ||
===चक्रीय टैग प्रणाली काम कर रही है=== | ===चक्रीय टैग प्रणाली काम कर रही है=== | ||
Revision as of 19:43, 10 August 2023
नियम 110 सेलुलर ऑटोमेटन (अधिकांश इसे केवल नियम 110 कहा जाता है)[lower-alpha 1]स्थिरता और अराजकता के मध्य की सीमा पर रोचक व्यवहार वाला प्राथमिक सेलुलर ऑटोमेटन है। इस संबंध में, यह कॉनवे के गेम ऑफ लाइफ के समान है। जीवन की तरह, विशेष दोहराए जाने वाले पृष्ठभूमि पैटर्न के साथ नियम 110 को ट्यूरिंग पूर्णता के रूप में जाना जाता है।[2] इसका तात्पर्य यह है कि, सिद्धांत रूप में, इस ऑटोमेटन का उपयोग करके किसी भी गणना या कंप्यूटर प्रोग्राम का अनुकरण किया जा सकता है।
परिभाषा
प्राथमिक सेलुलर ऑटोमेटन में, 0s और 1s का आयामी पैटर्न नियमों के सरल समूह के अनुसार विकसित होता है। नई पीढ़ी में पैटर्न में कोई बिंदु 0 या 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 में अनुमान लगाया था।[2] कुक ने वोल्फ्राम की पुस्तक नए तरह का विज्ञान के प्रकाशन से पहले सांता फ़े संस्थान सम्मेलन CA98 में अपना प्रमाण प्रस्तुत किया। इसके परिणामस्वरूप वोल्फ्राम अनुसंधान के साथ गैर-प्रकटीकरण समझौते पर आधारित नियमबद्ध स्थिति सामने आया।[3] वोल्फ्राम रिसर्च ने अनेक वर्षों तक कुक के प्रमाण के प्रकाशन को अवरुद्ध कर दिया।[4]
रोचक गुण
प्राथमिक सेलुलर ऑटोमेटन#प्रतिबिंब और पूरकों में, नियम 110 एकमात्र ऐसा है जिसके लिए ट्यूरिंग पूर्णता सीधे तौर पर सिद्ध की गई है, चूंकि अनेक समान नियमों के प्रमाण सरल परिणाम के रूप में अनुसरण करते हैं (उदाहरण के लिए नियम 124, जो नियम 110 का क्षैतिज प्रतिबिंब है)। नियम 110 संभवतः सबसे सरल ज्ञात ट्यूरिंग पूर्ण प्रणाली है।[2][5] नियम 110, कॉनवे के गेम ऑफ लाइफ की तरह, स्टीफन वोल्फ्राम को सेल्युलर ऑटोमेटन#क्लासिफिकेशन व्यवहार कहते हैं, जो न तब पूरी तरह से स्थिर है और न ही पूरी तरह से अराजक है। स्थानीयकृत संरचनाएँ जटिल विधियों से प्रकट होती हैं और परस्पर क्रिया करती हैं।[6] मैथ्यू कुक ने टैग प्रणाली#साइक्लिक टैग प्रणाली, फिर 2-टैग प्रणाली#साइक्लिक टैग प्रणाली और फिर ट्यूरिंग मशीनों का क्रमिक अनुकरण करके नियम 110 को सार्वभौमिक गणना का समर्थन करने में सक्षम सिद्ध किया। अंतिम चरण में समय जटिलता#घातीय समय ओवरहेड है क्योंकि ट्यूरिंग मशीन का टेप यूनरी अंक प्रणाली के साथ एन्कोड किया गया है। नियरी और वुड्स (2006) ने अलग निर्माण प्रस्तुत किया जो 2-टैग प्रणाली को क्लॉकवाइज ट्यूरिंग मशीनों से बदल देता है और इसमें बहुपद जटिलता ओवरहेड होती है।[7]
सार्वभौमिकता का प्रमाण
मैथ्यू कुक ने ए न्यू काइंड ऑफ साइंस के प्रकाशन से पहले आयोजित सांता फ़े इंस्टीट्यूट सम्मेलन में नियम 110 की सार्वभौमिकता का प्रमाण प्रस्तुत किया। वोल्फ्राम रिसर्च ने प्रमाणित किया कि इस प्रस्तुति ने अपने नियोक्ता के साथ कुक के गैर-प्रकटीकरण समझौते का उल्लंघन किया, और प्रकाशित सम्मेलन की कार्यवाही से कुक के पेपर को बाहर करने का अदालती आदेश प्राप्त किया। कुक के प्रमाण का अस्तित्व फिर भी ज्ञात हो गया। उनके प्रमाण में रुचि इसके परिणाम से उतनी अधिक नहीं थी जितनी इसके विधियों से, विशेष रूप से इसके निर्माण के विधिी विवरण से।[8] कुक के प्रमाण का चरित्र ए न्यू काइंड ऑफ साइंस में नियम 110 की चर्चा से अधिक भिन्न है। कुक ने तब से अपना पूरा प्रमाण बताते हुए पेपर लिखा है।[2]
कुक ने सिद्ध कर दिया कि नियम 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 में चक्रीय टैग प्रण
