नियम 110: Difference between revisions
No edit summary |
No edit summary |
||
| (7 intermediate revisions by 3 users not shown) | |||
| Line 32: | Line 32: | ||
==इतिहास== | ==इतिहास== | ||
2004 में, [[मैथ्यू कुक]] ने प्रमाण प्रकाशित किया कि विशेष दोहराए जाने वाले पृष्ठभूमि पैटर्न के साथ नियम 110 ट्यूरिंग पूर्णता है, अर्थात्, सार्वभौमिक गणना करने में सक्षम है, जिसे [[स्टीफन वोल्फ्राम]] ने 1985 में अनुमान लगाया था।{{sfnp|Cook|2004}} कुक ने वोल्फ्राम की पुस्तक [[एक नए तरह का विज्ञान| | 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}} | ||
==रोचक गुण== | ==रोचक गुण== | ||
प्राथमिक सेलुलर | 88 संभावित अद्वितीय प्राथमिक सेलुलर ऑटोमेटा में से, नियम 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 62: | Line 64: | ||
}}</ref> कुक के प्रमाण का चरित्र ए न्यू काइंड ऑफ साइंस में नियम 110 की चर्चा से अधिक भिन्न है। कुक ने तब से अपना पूरा प्रमाण बताते हुए पेपर लिखा है।{{sfnp|Cook|2004}} | }}</ref> कुक के प्रमाण का चरित्र ए न्यू काइंड ऑफ साइंस में नियम 110 की चर्चा से अधिक भिन्न है। कुक ने तब से अपना पूरा प्रमाण बताते हुए पेपर लिखा है।{{sfnp|Cook|2004}} | ||
कुक ने सिद्ध कर दिया कि नियम 110 सार्वभौमिक (या ट्यूरिंग पूर्ण) था, यह दिखाकर कि नियम का उपयोग किसी अन्य कम्प्यूटेशनल मॉडल, चक्रीय टैग प्रणाली का अनुकरण | कुक ने सिद्ध कर दिया कि नियम 110 सार्वभौमिक (या ट्यूरिंग पूर्ण) था, यह दिखाकर कि नियम का उपयोग किसी अन्य कम्प्यूटेशनल मॉडल, चक्रीय टैग प्रणाली का अनुकरण करने के लिए संभव था, जिसे सार्वभौमिक माना जाता है। उन्होंने सबसे पहले अनेक [[ अंतरिक्ष यान (सीए) |अंतरिक्ष यान (सीए)]] को भिन्न किया, जो स्व-स्थायी स्थानीयकृत पैटर्न थे, जिनका निर्माण नियम 110 ब्रह्मांड में अनंत रूप से दोहराए जाने वाले पैटर्न पर किया जा सकता था। फिर उन्होंने इन संरचनाओं के संयोजन के लिए इस तरह से परस्पर क्रिया करने की विधि तैयार किया जिसका उपयोग गणना के लिए किया जा सके। | ||
===नियम 110 में अंतरिक्ष यान=== | ===नियम 110 में अंतरिक्ष यान=== | ||
नियम 110 में सार्वभौमिक मशीन के कार्य के लिए असीमित रूप से दोहराए जाने वाले पृष्ठभूमि पैटर्न के अन्दर सीमित संख्या में स्थानीयकृत पैटर्न को एम्बेड करने की आवश्यकता होती है। पृष्ठभूमि पैटर्न चौदह सेल चौड़ा है और | नियम 110 में सार्वभौमिक मशीन के कार्य के लिए असीमित रूप से दोहराए जाने वाले पृष्ठभूमि पैटर्न के अन्दर सीमित संख्या में स्थानीयकृत पैटर्न को एम्बेड करने की आवश्यकता होती है। पृष्ठभूमि पैटर्न चौदह सेल चौड़ा है और प्रत्येक सात पुनरावृत्तियों में स्वयं को दोहराता है। पैटर्न '''00010011011111''' हैं। | ||
नियम 110 सार्वभौमिक मशीन में तीन स्थानीयकृत पैटर्न विशेष महत्व के हैं। उन्हें नीचे दी गई छवि में दिखाया गया है, जो दोहराए जाने वाले पृष्ठभूमि पैटर्न से घिरा हुआ है। सबसे बायीं ओर की संरचना दाहिनी दो | नियम 110 सार्वभौमिक मशीन में तीन स्थानीयकृत पैटर्न विशेष महत्व के हैं। उन्हें नीचे दी गई छवि में दिखाया गया है, जो दोहराए जाने वाले पृष्ठभूमि पैटर्न से घिरा हुआ है। सबसे बायीं ओर की संरचना दाहिनी दो सेलों में स्थानांतरित हो जाती है और प्रत्येक तीन पीढ़ियों में दोहराई जाती है। इसमें अनुक्रम '''0001110111''' सम्मिलित है जो ऊपर दिए गए पृष्ठभूमि पैटर्न से घिरा हुआ है, साथ ही इस अनुक्रम के दो भिन्न-भिन्न विकास भी सम्मिलित हैं। | ||
आंकड़ों में | आंकड़ों में ऊपर से नीचे तक समय व्यतीत होने पर शीर्ष रेखा प्रारंभिक स्थिति को दर्शाती है और प्रत्येक अगली पंक्ति अगली बार की स्थिति को दर्शाती है। | ||
[[Image:ca110-structures2.png]] | |||
केंद्र संरचना आठ सेलों के बाईं ओर बदलती है और प्रत्येक तीस पीढ़ियों में दोहराई जाती है। इसमें अनुक्रम '''1001111''' सम्मिलित है जो ऊपर दिए गए पृष्ठभूमि पैटर्न के साथ-साथ इस अनुक्रम के उनतीस विभिन्न विकासों से घिरा हुआ है। | |||
सबसे दाहिनी संरचना स्थिर रहती है और प्रत्येक सात पीढ़ियों में दोहराई जाती है। इसमें अनुक्रम '''111''' सम्मिलित है जो ऊपर दिए गए पृष्ठभूमि पैटर्न के साथ-साथ इस अनुक्रम के पांच भिन्न-भिन्न विकासों से घिरा हुआ है। | |||
नीचे छवि दी गई है जिसमें पहली दो संरचनाएं बिना अनुवाद के (बाएं) एक-दूसरे से निकलते हुए और तीसरी संरचना (दाएं) बनाने के लिए परस्पर क्रिया करते हुए दिखाई दे रही हैं। | |||
[[Image:ca110-interaction2.png]] | |||
नियम 110 में अनेक अन्य अंतरिक्ष यान हैं, किन्तु वे सार्वभौमिकता प्रमाण में प्रमुखता से सम्मिलित नहीं हैं। | |||
===चक्रीय टैग प्रणाली का निर्माण=== | ===चक्रीय टैग प्रणाली का निर्माण=== | ||
| Line 86: | Line 94: | ||
* घड़ी की धड़कनों की अनंत रूप से दोहराई जाने वाली श्रृंखला जो बाईं ओर से प्रारंभ होती है और दाईं ओर चलती है। | * घड़ी की धड़कनों की अनंत रूप से दोहराई जाने वाली श्रृंखला जो बाईं ओर से प्रारंभ होती है और दाईं ओर चलती है। | ||
इन घटकों के मध्य प्रारंभिक अंतर अत्यंत महत्वपूर्ण है। सेलुलर ऑटोमेटन के लिए चक्रीय टैग प्रणाली को प्रायुक्त करने के लिए, ऑटोमेटन की प्रारंभिक स्थितियों को सावधानीपूर्वक चुना जाना चाहिए जिससे उसमें उपस्थित विभिन्न स्थानीय संरचनाएं उच्च क्रमबद्ध | इन घटकों के मध्य प्रारंभिक अंतर अत्यंत महत्वपूर्ण है। सेलुलर ऑटोमेटन के लिए चक्रीय टैग प्रणाली को प्रायुक्त करने के लिए, ऑटोमेटन की प्रारंभिक स्थितियों को सावधानीपूर्वक चुना जाना चाहिए जिससे उसमें उपस्थित विभिन्न स्थानीय संरचनाएं उच्च क्रमबद्ध विधियों से परस्पर क्रिया कर सकें। | ||
चक्रीय टैग प्रणाली में डेटा स्ट्रिंग को ऊपर दिखाए गए प्रकार की स्थिर दोहराई जाने वाली संरचनाओं की श्रृंखला द्वारा दर्शाया गया है। इन संरचनाओं के मध्य क्षैतिज स्थान की | चक्रीय टैग प्रणाली में डेटा स्ट्रिंग को ऊपर दिखाए गए प्रकार की स्थिर दोहराई जाने वाली संरचनाओं की श्रृंखला द्वारा दर्शाया गया है। इन संरचनाओं के मध्य क्षैतिज स्थान की भिन्न-भिन्न मात्रा 1 प्रतीकों को 0 प्रतीकों से भिन्न करने का काम करती है। ये प्रतीक उस शब्द का प्रतिनिधित्व करते हैं जिस पर चक्रीय टैग प्रणाली चल रही है, और प्रत्येक उत्पादन नियम पर विचार करने पर पहला ऐसा प्रतीक नष्ट हो जाता है। जब यह अग्रणी प्रतीक 1 होता है, तब स्ट्रिंग के अंत में नए प्रतीक जोड़े जाते हैं; जब यह 0 होता है, तब कोई नया प्रतीक नहीं जोड़ा जाता है। इसे प्राप्त करने का तंत्र नीचे वर्णित है। | ||
दाईं ओर से प्रवेश करने पर ऊपर दिखाए गए प्रकार की बाईं ओर चलने वाली संरचनाओं की श्रृंखला होती है, जो क्षैतिज स्थान की | दाईं ओर से प्रवेश करने पर ऊपर दिखाए गए प्रकार की बाईं ओर चलने वाली संरचनाओं की श्रृंखला होती है, जो क्षैतिज स्थान की भिन्न-भिन्न मात्रा से भिन्न होती हैं। चक्रीय टैग प्रणाली के उत्पादन नियमों में 0s और 1s का प्रतिनिधित्व करने के लिए इन संरचनाओं की बड़ी संख्या को विभिन्न रिक्तियों के साथ जोड़ा जाता है। क्योंकि टैग प्रणाली के उत्पादन नियम प्रोग्राम के निर्माण के समय ज्ञात होते हैं, और अनंत रूप से दोहराए जाने वाले, प्रारंभिक स्थिति में 0s और 1s के पैटर्न को अनंत रूप से दोहराई जाने वाली स्ट्रिंग द्वारा दर्शाया जा सकता है। प्रत्येक उत्पादन नियम को अगले नियम से अन्य संरचना द्वारा भिन्न किया जाता है जिसे नियम विभाजक (या ब्लॉक विभाजक) के रूप में जाना जाता है, जो उत्पादन नियमों के एन्कोडिंग के समान दर से बाईं ओर बढ़ता है। | ||
जब बाईं ओर चलने वाला नियम विभाजक चक्रीय टैग प्रणाली के डेटा स्ट्रिंग में स्थिर प्रतीक का सामना करता है, तब यह उसके सामने आने वाले पहले प्रतीक को नष्ट कर देता है। चूँकि, इसका पश्चात का व्यवहार इस पर निर्भर करता है कि स्ट्रिंग द्वारा एन्कोड किया गया प्रतीक 0 | जब बाईं ओर चलने वाला नियम विभाजक चक्रीय टैग प्रणाली के डेटा स्ट्रिंग में स्थिर प्रतीक का सामना करता है, तब यह उसके सामने आने वाले पहले प्रतीक को नष्ट कर देता है। चूँकि, इसका पश्चात का व्यवहार इस पर निर्भर करता है कि स्ट्रिंग द्वारा एन्कोड किया गया प्रतीक 0 या 1 था। यदि 0 है, तब नियम विभाजक नई संरचना में बदल जाता है जो आने वाले उत्पादन नियम को अवरुद्ध कर देता है। यह नई संरचना तब नष्ट हो जाती है जब इसका सामना अगले नियम विभाजक से होता है। | ||
दूसरी ओर, यदि स्ट्रिंग में प्रतीक 1 था, तब नियम विभाजक नई संरचना में बदल जाता है जो आने वाले उत्पादन नियम को स्वीकार करता है। यद्यपि नई संरचना अगले नियम विभाजक का सामना करने पर फिर से नष्ट हो जाती है, यह पहले संरचनाओं की श्रृंखला को बाईं ओर से निकलने की अनुमति देती है। फिर इन संरचनाओं को चक्रीय टैग प्रणाली की डेटा स्ट्रिंग के अंत में जोड़ने के लिए बनाया जाता है। यह अंतिम परिवर्तन ऊपर दिखाए गए दाहिनी ओर चलने वाले पैटर्न में अनंत रूप से दोहराई जाने वाली, दाहिनी ओर चलने वाली घड़ी की दालों की श्रृंखला के माध्यम से पूरा किया जाता है। घड़ी की दालें उत्पादन नियम से आने वाले बाईं ओर चलने वाले 1 प्रतीकों को डेटा स्ट्रिंग के स्थिर 1 प्रतीकों में बदल देती हैं, और उत्पादन नियम से आने वाले 0 प्रतीकों को डेटा स्ट्रिंग के स्थिर 0 प्रतीकों में बदल देती हैं। | दूसरी ओर, यदि स्ट्रिंग में प्रतीक 1 था, तब नियम विभाजक नई संरचना में बदल जाता है जो आने वाले उत्पादन नियम को स्वीकार करता है। यद्यपि नई संरचना अगले नियम विभाजक का सामना करने पर फिर से नष्ट हो जाती है, यह पहले संरचनाओं की श्रृंखला को बाईं ओर से निकलने की अनुमति देती है। फिर इन संरचनाओं को चक्रीय टैग प्रणाली की डेटा स्ट्रिंग के अंत में जोड़ने के लिए बनाया जाता है। यह अंतिम परिवर्तन ऊपर दिखाए गए दाहिनी ओर चलने वाले पैटर्न में अनंत रूप से दोहराई जाने वाली, दाहिनी ओर चलने वाली घड़ी की दालों की श्रृंखला के माध्यम से पूरा किया जाता है। घड़ी की दालें उत्पादन नियम से आने वाले बाईं ओर चलने वाले 1 प्रतीकों को डेटा स्ट्रिंग के स्थिर 1 प्रतीकों में बदल देती हैं, और उत्पादन नियम से आने वाले 0 प्रतीकों को डेटा स्ट्रिंग के स्थिर 0 प्रतीकों में बदल देती हैं। | ||
===चक्रीय टैग प्रणाली काम कर रही है=== | ===चक्रीय टैग प्रणाली काम कर रही है=== | ||
[[Image:Cts-diagram.jpg]]उपरोक्त चित्र नियम 110 में चक्रीय टैग प्रणाली के पुनर्निर्माण का योजनाबद्ध आरेख है। | [[Image:Cts-diagram.jpg]] | ||
उपरोक्त चित्र नियम 110 में चक्रीय टैग प्रणाली के पुनर्निर्माण का योजनाबद्ध आरेख है। | |||
== यह भी देखें == | == यह भी देखें == | ||
| Line 144: | Line 154: | ||
* [http://www.comunidad.escom.ipn.mx/genaro/Rule110.html Rule 110 repository] | * [http://www.comunidad.escom.ipn.mx/genaro/Rule110.html Rule 110 repository] | ||
* [https://www.youtube.com/watch?v=QKnSRw_X2w4 Marble-based mechanical implementation of a 4-bit Rule 110 computer] | * [https://www.youtube.com/watch?v=QKnSRw_X2w4 Marble-based mechanical implementation of a 4-bit Rule 110 computer] | ||
[[Category: | [[Category:CS1 English-language sources (en)]] | ||
[[Category:Commons category link is the pagename]] | |||
[[Category:Created On 09/08/2023]] | [[Category:Created On 09/08/2023]] | ||
[[Category:Lua-based templates]] | |||
[[Category:Machine Translated Page]] | |||
[[Category:Pages with broken file links]] | |||
[[Category:Pages with script errors]] | |||
[[Category:Short description with empty Wikidata description]] | |||
[[Category:Templates Vigyan Ready]] | |||
[[Category:Templates that add a tracking category]] | |||
[[Category:Templates that generate short descriptions]] | |||
[[Category:Templates using TemplateData]] | |||
[[Category:वोल्फ्राम कोड]] | |||
[[Category:सेलुलर ऑटोमेटन नियम]] | |||
Latest revision as of 10:43, 22 August 2023
नियम 110 सेलुलर ऑटोमेटन (अधिकांश इसे केवल नियम 110 कहा जाता है)[lower-alpha 1] स्थिरता और अराजकता के मध्य की सीमा पर रोचक व्यवहार वाला एक प्राथमिक सेलुलर ऑटोमेटन है। इस संबंध में, यह कॉनवे के गेम ऑफ लाइफ के समान है। जीवन की तरह, विशेष दोहराए जाने वाले पृष्ठभूमि पैटर्न के साथ नियम 110 को ट्यूरिंग पूर्णता के रूप में जाना जाता है।[2] इसका तात्पर्य यह है कि, सिद्धांत रूप में, इस ऑटोमेटन का उपयोग करके कोई भी गणना या कंप्यूटर प्रोग्राम का अनुकरण किया जा सकता है।
परिभाषा
प्राथमिक सेलुलर ऑटोमेटन में, 0s और 1s का आयामी पैटर्न नियमों के एक सरल समूह के अनुसार विकसित होता है। नई पीढ़ी में पैटर्न में कोई बिंदु 0 या 1 होगा या नहीं, यह उसके वर्तमान मान के साथ-साथ उसके दो निकटतम मान पर भी निर्भर करता है।
नियम 110 ऑटोमेटन में नियमों का निम्नलिखित समूह है:
| वर्तमान पैटर्न | 111 | 110 | 101 | 100 | 011 | 010 | 001 | 000 |
|---|---|---|---|---|---|---|---|---|
| केंद्र कक्ष के लिए नई अवस्था | 0 | 1 | 1 | 0 | 1 | 1 | 1 | 0 |
नियम 110 का नाम इस तथ्य से लिया गया है कि इस नियम को बाइनरी अनुक्रम 01101110 में संक्षेपित किया जा सकता है; जिसे बाइनरी संख्या के रूप में व्याख्या की गई, और यह दशमलव मान 110 से मेल खाती है। यह वोल्फ्राम कोड नामकरण योजना है।
इतिहास
2004 में, मैथ्यू कुक ने एक प्रमाण प्रकाशित किया कि एक विशेष दोहराए जाने वाले पृष्ठभूमि पैटर्न के साथ नियम 110 ट्यूरिंग पूर्णता है, अर्थात्, सार्वभौमिक गणना करने में सक्षम है, जिसे स्टीफन वोल्फ्राम ने 1985 में अनुमान लगाया था।[2] कुक ने वोल्फ्राम की पुस्तक ए न्यू काइंड ऑफ साइंस के प्रकाशन से पहले सांता फ़े इंस्टीट्यूट सम्मेलन CA98 में अपना प्रमाण प्रस्तुत किया था। इसके परिणामस्वरूप वोल्फ्राम रिसर्च के साथ गैर-प्रकटीकरण समझौते पर आधारित नियमबद्ध स्थिति सामने आई थी।[3] वोल्फ्राम रिसर्च ने अनेक वर्षों तक कुक के प्रमाण के प्रकाशन को अवरुद्ध कर दिया था।[4]
रोचक गुण
88 संभावित अद्वितीय प्राथमिक सेलुलर ऑटोमेटा में से, नियम 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 प्रतीकों में बदल देती हैं।
चक्रीय टैग प्रणाली काम कर रही है
उपरोक्त चित्र नियम 110 में चक्रीय टैग प्रणाली के पुनर्निर्माण का योजनाबद्ध आरेख है।
यह भी देखें
टिप्पणियाँ
- ↑ 110 is the number 110, written in conventional decimal notation, and thus is pronounced as one pronounces nominal numbers ordinarily. For example, Stephen Wolfram pronounces the name "rule one-ten".[1]
संदर्भ
- ↑ Stephen Wolfram (2003). A New Kind of Science - Stephen Wolfram (in English). University of California Television (UCTV). Event occurs at 9:51. Retrieved 2023-06-19.
- ↑ 2.0 2.1 2.2 2.3 Cook (2004).
- ↑ Wolfram Research Inc v. Cook (2:00-cv-09357) (sometimes cited as "Wolfram Research Inc. v. Matthew Cook. 8/31 CV00-9357 CBM")
- ↑ Giles (2002).
- ↑ Wolfram (2002), pp. 169, 675–691
- ↑ Wolfram (2002), p. 229
- ↑ Neary & Woods (2006).
- ↑ Martinez, Genaro J.; Seck Tuoh Mora, Juan; Chapa, Sergio; Lemaitre, Christian (April 2019). "Brief notes and history computing in Mexico during 50 years". International Journal of Parallel, Emergent and Distributed Systems. 35 (2): 185–192. arXiv:1905.07527. doi:10.1080/17445760.2019.1608990. S2CID 150262966. Retrieved 2020-04-15.
उद्धृत कार्य
- 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).
बाहरी संबंध
