वॉन न्यूमैन सेलुलर ऑटोमेटन: Difference between revisions
From Vigyanwiki
(Created page with "{{short description|Cellular automaton used to model universal construction}} Image:VonNeumann CA demo.gif|right|frame|वॉन न्यूमैन के सेलुल...") |
No edit summary |
||
| Line 1: | Line 1: | ||
{{short description|Cellular automaton used to model universal construction}} | {{short description|Cellular automaton used to model universal construction}} | ||
[[Image:VonNeumann CA demo.gif|right|frame|वॉन न्यूमैन के सेलुलर ऑटोमेटन में | [[Image:VonNeumann CA demo.gif|right|frame|वॉन न्यूमैन के सेलुलर ऑटोमेटन में सरल विन्यास। उत्तेजित और शांत सामान्य ट्रांसमिशन स्थितियों का उपयोग करते हुए, बाइनरी सिग्नल को नीले तार लूप के चारों ओर बार-बार पारित किया जाता है। संगम सेल विशेष ट्रांसमिशन राज्यों से युक्त लाल तार की लंबाई पर सिग्नल को डुप्लिकेट करता है। सिग्नल इस तार से होकर गुजरता है और अंत में नए सेल का निर्माण करता है। यह विशेष सिग्नल (1011) पूर्व-निर्देशित विशेष ट्रांसमिशन स्थिति के लिए कोड करता है, इस प्रकार हर बार लाल तार को सेल तक विस्तारित करता है। निर्माण के दौरान, नई कोशिका बाइनरी अनुक्रम द्वारा निर्देशित कई संवेदनशील अवस्थाओं से गुजरती है।]]वॉन न्यूमैन सेलुलर ऑटोमेटा सेलुलर ऑटोमेटा की मूल अभिव्यक्ति है, जिसके विकास को [[जॉन वॉन न्यूमैन]] को उनके करीबी दोस्त और साथी गणितज्ञ [[स्टैनिस्लाव मछुआरे]] द्वारा दिए गए सुझावों से प्रेरित किया गया था। उनका मूल उद्देश्य [[स्व-प्रतिकृति मशीन]] | मशीन स्व-प्रतिकृति के लिए तार्किक आवश्यकताओं में अंतर्दृष्टि प्रदान करना था, और उनका उपयोग वॉन न्यूमैन के [[वॉन न्यूमैन यूनिवर्सल कंस्ट्रक्टर]] में किया गया था। | ||
नोबिली [[सेल्यूलर आटोमेटा]]|नोबिली का सेल्युलर ऑटोमेटन वॉन न्यूमैन के सेल्युलर ऑटोमेटन का | नोबिली [[सेल्यूलर आटोमेटा]]|नोबिली का सेल्युलर ऑटोमेटन वॉन न्यूमैन के सेल्युलर ऑटोमेटन का रूप है, जो सिग्नलों को पार करने और जानकारी संग्रहीत करने के लिए संगम कोशिकाओं की क्षमता के साथ संवर्धित है। पूर्व को अतिरिक्त तीन राज्यों की आवश्यकता होती है, इसलिए नोबिली के सेलुलर ऑटोमेटन में 29 के बजाय 32 राज्य होते हैं। हटन का सेलुलर ऑटोमेटन और भिन्नता है, जो लैंगटन के लूप के अनुरूप डेटा के लूप को दोहराने की अनुमति देता है। | ||
== परिभाषा == | == परिभाषा == | ||
| Line 8: | Line 8: | ||
=== कॉन्फ़िगरेशन === | === कॉन्फ़िगरेशन === | ||
सामान्य तौर पर, सेलुलर ऑटोमेटा (सीए) परिमित राज्य मशीन (एफएसए) की | सामान्य तौर पर, सेलुलर ऑटोमेटा (सीए) परिमित राज्य मशीन (एफएसए) की व्यवस्था का गठन करती है जो दूसरे के बीच स्थितीय संबंधों में बैठती है, प्रत्येक एफएसए उन अन्य एफएसए के साथ जानकारी का आदान-प्रदान करता है जिनके साथ यह स्थितिगत रूप से जुड़ा हुआ है। वॉन न्यूमैन के सेलुलर ऑटोमेटन में, परिमित राज्य मशीनें (या ''कोशिकाएं'') दो-आयामी [[कार्टेशियन ग्रिड]] में व्यवस्थित होती हैं, और आसपास की चार कोशिकाओं के साथ इंटरफेस करती हैं। चूंकि वॉन न्यूमैन का सेलुलर ऑटोमेटन इस व्यवस्था का उपयोग करने वाला पहला उदाहरण था, इसे [[[[वॉन न्यूमैन पड़ोस]]]] के रूप में जाना जाता है। | ||
एफएसए का सेट अनंत आकार के सेल स्पेस को परिभाषित करता है। सभी एफएसए राज्य-संक्रमण फ़ंक्शन, या नियम-सेट के संदर्भ में समान हैं। | एफएसए का सेट अनंत आकार के सेल स्पेस को परिभाषित करता है। सभी एफएसए राज्य-संक्रमण फ़ंक्शन, या नियम-सेट के संदर्भ में समान हैं। | ||
| Line 14: | Line 14: | ||
वॉन न्यूमैन पड़ोस (एक समूहीकरण फ़ंक्शन) राज्य-संक्रमण फ़ंक्शन का हिस्सा है, और किसी भी सेल के लिए अन्य कोशिकाओं के सेट को परिभाषित करता है जिस पर उस सेल की स्थिति निर्भर करती है। | वॉन न्यूमैन पड़ोस (एक समूहीकरण फ़ंक्शन) राज्य-संक्रमण फ़ंक्शन का हिस्सा है, और किसी भी सेल के लिए अन्य कोशिकाओं के सेट को परिभाषित करता है जिस पर उस सेल की स्थिति निर्भर करती है। | ||
सभी कोशिकाएं | सभी कोशिकाएं तुल्यकालिक डिजिटल सर्किट की तरह, सार्वभौमिक घड़ी के साथ कदम मिलाकर, तुल्यकालिक रूप से अपना संक्रमण करती हैं। | ||
=== राज्य === | === राज्य === | ||
| Line 23: | Line 23: | ||
# संक्रमण या संवेदी अवस्थाएँ (8 उप-अवस्थाओं में) | # संक्रमण या संवेदी अवस्थाएँ (8 उप-अवस्थाओं में) | ||
## IS (नव संवेदीकरण) {{legend2|#ff0000|(255, 0, 0)}} | ## IS (नव संवेदीकरण) {{legend2|#ff0000|(255, 0, 0)}} | ||
## एस<sub>0</sub>- (संवेदनशील, | ## एस<sub>0</sub>- (संवेदनशील, चक्र के लिए कोई इनपुट प्राप्त नहीं हुआ) {{legend2|#ff7d00|(255, 125, 0)}} | ||
## एस<sub>00</sub>- (संवेदनशील, दो चक्रों तक कोई इनपुट नहीं मिला) {{legend2|#ffaf32|(255, 175, 50)}} | ## एस<sub>00</sub>- (संवेदनशील, दो चक्रों तक कोई इनपुट नहीं मिला) {{legend2|#ffaf32|(255, 175, 50)}} | ||
## एस<sub>000</sub>- (संवेदनशील, तीन चक्रों तक कोई इनपुट नहीं मिला) {{legend2|#fbff00|(251, 255, 0)}} | ## एस<sub>000</sub>- (संवेदनशील, तीन चक्रों तक कोई इनपुट नहीं मिला) {{legend2|#fbff00|(251, 255, 0)}} | ||
## एस<sub>01</sub>- (संवेदनशील, | ## एस<sub>01</sub>- (संवेदनशील, चक्र के लिए कोई इनपुट नहीं मिला और फिर चक्र के लिए इनपुट) {{legend2|#ffc84b|(255, 200, 75)}} | ||
## एस<sub>1</sub>- (संवेदनशील, | ## एस<sub>1</sub>- (संवेदनशील, चक्र के लिए इनपुट प्राप्त होने पर) {{legend2|#ff9619|(255, 150, 25)}} | ||
## एस<sub>10</sub>- (संवेदनशील, | ## एस<sub>10</sub>- (संवेदनशील, चक्र के लिए इनपुट प्राप्त हुआ और फिर चक्र के लिए कोई इनपुट नहीं) {{legend2|#ffff64|(255, 255, 100)}} | ||
## एस<sub>11</sub>- (संवेदनशील, दो चक्रों के लिए इनपुट प्राप्त करने के बाद) {{legend2|#fffa7d|(255, 250, 125)}} | ## एस<sub>11</sub>- (संवेदनशील, दो चक्रों के लिए इनपुट प्राप्त करने के बाद) {{legend2|#fffa7d|(255, 250, 125)}} | ||
# संगम अवस्थाएँ (उत्तेजना की 4 अवस्थाओं में) | # संगम अवस्थाएँ (उत्तेजना की 4 अवस्थाओं में) | ||
| Line 46: | Line 46: | ||
## पूर्व दिशा की ओर (उत्साहित और शांत) {{legend2|#b938ff|(185, 56, 255)}} {{legend2|#eb2424|(235, 36, 36)}} | ## पूर्व दिशा की ओर (उत्साहित और शांत) {{legend2|#b938ff|(185, 56, 255)}} {{legend2|#eb2424|(235, 36, 36)}} | ||
उत्साहित राज्य प्रति राज्य संक्रमण चरण में | उत्साहित राज्य प्रति राज्य संक्रमण चरण में बिट की दर से डेटा ले जाते हैं। | ||
ध्यान दें कि संगम राज्यों में एक-चक्र विलंब की संपत्ति होती है, इस प्रकार किसी भी समय डेटा के दो बिट प्रभावी ढंग से रखे जाते हैं। | ध्यान दें कि संगम राज्यों में एक-चक्र विलंब की संपत्ति होती है, इस प्रकार किसी भी समय डेटा के दो बिट प्रभावी ढंग से रखे जाते हैं। | ||
| Line 53: | Line 53: | ||
कोशिकाओं के बीच बिट्स का प्रवाह दिशा गुण द्वारा दर्शाया जाता है। निम्नलिखित नियम लागू होते हैं: | कोशिकाओं के बीच बिट्स का प्रवाह दिशा गुण द्वारा दर्शाया जाता है। निम्नलिखित नियम लागू होते हैं: | ||
* ट्रांसमिशन स्थिति इनपुट पर OR ऑपरेटर लागू करती है, जिसका अर्थ है कि ट्रांसमिशन स्थिति (सामान्य या विशेष) में | * ट्रांसमिशन स्थिति इनपुट पर OR ऑपरेटर लागू करती है, जिसका अर्थ है कि ट्रांसमिशन स्थिति (सामान्य या विशेष) में सेल समय t+1 पर उत्तेजित होगी यदि इसकी ओर इशारा करने वाले इनपुट में से कोई भी ''समय t पर उत्साहित है। | ||
* डेटा ए की दिशा संपत्ति के अनुसार, सामान्य ट्रांसमिशन स्थिति में सेल ए से आसन्न सेल बी में गुजरता है (जब तक कि बी को भी ए की ओर निर्देशित नहीं किया जाता है, जिस स्थिति में डेटा गायब हो जाता है)। | * डेटा ए की दिशा संपत्ति के अनुसार, सामान्य ट्रांसमिशन स्थिति में सेल ए से आसन्न सेल बी में गुजरता है (जब तक कि बी को भी ए की ओर निर्देशित नहीं किया जाता है, जिस स्थिति में डेटा गायब हो जाता है)। | ||
* डेटा | * डेटा विशेष ट्रांसमिशन स्थिति में सेल ए से विशेष ट्रांसमिशन स्थिति में आसन्न सेल बी में सामान्य ट्रांसमिशन राज्यों के समान नियमों के अनुसार गुजरता है। | ||
* ट्रांसमिशन अवस्थाओं के दो उपसमूह, सामान्य और विशेष, परस्पर विरोधी हैं: | * ट्रांसमिशन अवस्थाओं के दो उपसमूह, सामान्य और विशेष, परस्पर विरोधी हैं: | ||
** उत्तेजित सामान्य संचरण अवस्था में समय t पर | ** उत्तेजित सामान्य संचरण अवस्था में समय t पर सेल A दिया गया है | ||
** किसी विशेष संचरण अवस्था में सेल बी की ओर इशारा करना | ** किसी विशेष संचरण अवस्था में सेल बी की ओर इशारा करना | ||
** समय पर t+1 सेल B जमीनी अवस्था बन जाएगा। विशेष ट्रांसमिशन सेल नष्ट हो गया है. | ** समय पर t+1 सेल B जमीनी अवस्था बन जाएगा। विशेष ट्रांसमिशन सेल नष्ट हो गया है. | ||
** एक समान अनुक्रम विशेष ट्रांसमिशन स्थिति में | ** एक समान अनुक्रम विशेष ट्रांसमिशन स्थिति में सेल के मामले में घटित होगा जो सामान्य ट्रांसमिशन स्थिति में सेल की ओर इशारा करता है | ||
=== संगम राज्य नियम === | === संगम राज्य नियम === | ||
निम्नलिखित विशिष्ट नियम संगम राज्यों पर लागू होते हैं: | निम्नलिखित विशिष्ट नियम संगम राज्यों पर लागू होते हैं: | ||
* संगम राज्य | * संगम राज्य दूसरे के बीच डेटा पास नहीं करते हैं। | ||
* कंफ्लुएंट राज्य | * कंफ्लुएंट राज्य या अधिक सामान्य ट्रांसमिशन राज्यों से इनपुट लेते हैं, और आउटपुट को ट्रांसमिशन राज्यों, सामान्य और विशेष, में वितरित करते हैं, जो कंफ्लुएंट राज्य की ओर निर्देशित नहीं होते हैं। | ||
* डेटा ट्रांसमिशन स्टेट डायरेक्शन प्रॉपर्टी के विरुद्ध प्रसारित नहीं होता है। | * डेटा ट्रांसमिशन स्टेट डायरेक्शन प्रॉपर्टी के विरुद्ध प्रसारित नहीं होता है। | ||
* यदि उस राज्य में कोई आसन्न ट्रांसमिशन स्थिति नहीं है जो कि संगम राज्य पर इंगित नहीं है तो संगम राज्य द्वारा रखा गया डेटा खो जाता है। | * यदि उस राज्य में कोई आसन्न ट्रांसमिशन स्थिति नहीं है जो कि संगम राज्य पर इंगित नहीं है तो संगम राज्य द्वारा रखा गया डेटा खो जाता है। | ||
* इस प्रकार, संगम-अवस्था कोशिकाओं का उपयोग सामान्य-से-विशेष-संचरण राज्य कोशिकाओं की ट्रांसमिशन लाइनों से पुल के रूप में किया जाता है। | * इस प्रकार, संगम-अवस्था कोशिकाओं का उपयोग सामान्य-से-विशेष-संचरण राज्य कोशिकाओं की ट्रांसमिशन लाइनों से पुल के रूप में किया जाता है। | ||
* संगम अवस्था इनपुट पर AND ऑपरेटर लागू करती है, केवल तभी उत्तेजित इनपुट को बचाती है जब सभी संभावित इनपुट | * संगम अवस्था इनपुट पर AND ऑपरेटर लागू करती है, केवल तभी उत्तेजित इनपुट को बचाती है जब सभी संभावित इनपुट साथ उत्तेजित होते हैं। | ||
* कंफ्लुएंट कोशिकाएं ओटीएस कोशिकाओं की तुलना में संकेतों में | * कंफ्लुएंट कोशिकाएं ओटीएस कोशिकाओं की तुलना में संकेतों में पीढ़ी अधिक देरी करती हैं; [[समता (गणित)]] बाधाओं के कारण यह आवश्यक है। | ||
=== निर्माण नियम === | === निर्माण नियम === | ||
[[Image:VonNeumann CA construction demo.gif|right|frame|नौ कोशिका प्रकार जिनका निर्माण वॉन न्यूमैन के सीए में किया जा सकता है। यहां, बाइनरी सिग्नल नौ सामान्य ट्रांसमिशन लाइनों से गुजरते हैं, और अंत में | [[Image:VonNeumann CA construction demo.gif|right|frame|नौ कोशिका प्रकार जिनका निर्माण वॉन न्यूमैन के सीए में किया जा सकता है। यहां, बाइनरी सिग्नल नौ सामान्य ट्रांसमिशन लाइनों से गुजरते हैं, और अंत में जमीनी स्थिति का सामना करने पर नई सेल का निर्माण करते हैं। उदाहरण के लिए, बाइनरी स्ट्रिंग 1011 को पांचवीं पंक्ति पर दिखाया गया है, और पूर्व-निर्देशित विशेष ट्रांसमिशन स्थिति का निर्माण करता है - यह वही प्रक्रिया है जो इस पृष्ठ के शीर्ष पर ऑटोमेटन में उपयोग की जाती है। ध्यान दें कि पड़ोसी तारों के बीच कोई इंटरैक्शन नहीं है, उदाहरण के लिए [[वायरवर्ल्ड]] के विपरीत, घटकों की कॉम्पैक्ट पैकिंग की अनुमति देता है।]]प्रारंभ में, सेल-स्पेस का अधिकांश भाग, सेलुलर ऑटोमेटन का ब्रह्मांड, खाली होता है, जिसमें जमीनी अवस्था यू में कोशिकाएं शामिल होती हैं। जब किसी पड़ोसी सामान्य- या विशेष संचरण अवस्था से इनपुट उत्तेजना दी जाती है, तो जमीनी अवस्था में कोशिका बन जाती है संवेदनशील, अवस्थाओं की शृंखला से गुजरते हुए अंततः शांत संचरण या संगम अवस्था में विश्राम करने से पहले। | ||
सेल किस गंतव्य राज्य तक पहुंचेगा इसका चुनाव इनपुट संकेतों के अनुक्रम से निर्धारित होता है। इसलिए, संक्रमण/संवेदी अवस्थाओं को | सेल किस गंतव्य राज्य तक पहुंचेगा इसका चुनाव इनपुट संकेतों के अनुक्रम से निर्धारित होता है। इसलिए, संक्रमण/संवेदी अवस्थाओं को [[द्विभाजन सिद्धांत]] वृक्ष के नोड्स के रूप में माना जा सकता है जो जमीनी अवस्था से प्रत्येक शांत संचरण और संगम अवस्था की ओर जाता है। | ||
निम्नलिखित ट्री में, इनपुट का क्रम प्रत्येक चरण के बाद बाइनरी स्ट्रिंग के रूप में दिखाया गया है: | निम्नलिखित ट्री में, इनपुट का क्रम प्रत्येक चरण के बाद बाइनरी स्ट्रिंग के रूप में दिखाया गया है: | ||
* जमीनी अवस्था यू में | * जमीनी अवस्था यू में कोशिका, इनपुट दिए जाने पर, अगले चक्र में एस (नव संवेदी) अवस्था में परिवर्तित हो जाएगी (1) | ||
* S अवस्था में | * S अवस्था में सेल, बिना कोई इनपुट दिए, S में परिवर्तित हो जाएगा<sub>0</sub>राज्य (10) | ||
** एस में | ** एस में सेल<sub>0</sub>राज्य, कोई इनपुट नहीं दिए जाने पर, एस में परिवर्तित हो जाएगा<sub>00</sub>राज्य (100) | ||
*** एस में | *** एस में सेल<sub>00</sub>राज्य, कोई इनपुट नहीं दिए जाने पर, एस में परिवर्तित हो जाएगा<sub>000</sub>राज्य (1000) | ||
**** एस में | **** एस में सेल<sub>000</sub>राज्य, कोई इनपुट नहीं दिए जाने पर, पूर्व-निर्देशित सामान्य ट्रांसमिशन राज्य (10000) में परिवर्तित हो जाएगा | ||
**** एस में | **** एस में सेल<sub>000</sub>राज्य, इनपुट दिया गया, उत्तर-निर्देशित सामान्य ट्रांसमिशन राज्य (10001) में परिवर्तित हो जाएगा | ||
*** एस में | *** एस में सेल<sub>00</sub>राज्य, इनपुट दिया गया, पश्चिम-निर्देशित सामान्य ट्रांसमिशन राज्य (1001) में परिवर्तित हो जाएगा | ||
** एस में | ** एस में सेल<sub>0</sub>राज्य, इनपुट दिया गया, एस में परिवर्तित हो जाएगा<sub>01</sub>राज्य (101) | ||
*** एस में | *** एस में सेल<sub>01</sub>राज्य, कोई इनपुट नहीं दिए जाने पर, दक्षिण-निर्देशित सामान्य ट्रांसमिशन राज्य (1010) में परिवर्तित हो जाएगा | ||
*** एस में | *** एस में सेल<sub>01</sub>राज्य, इनपुट दिया गया, पूर्व-निर्देशित विशेष ट्रांसमिशन राज्य (1011) में परिवर्तित हो जाएगा | ||
* S अवस्था में | * S अवस्था में सेल, इनपुट दिए जाने पर, S में परिवर्तित हो जाएगा<sub>1</sub>राज्य (11) | ||
** एस में | ** एस में सेल<sub>1</sub>राज्य, कोई इनपुट नहीं दिए जाने पर, एस में परिवर्तित हो जाएगा<sub>10</sub>राज्य (110) | ||
*** एस में | *** एस में सेल<sub>10</sub>राज्य, कोई इनपुट नहीं दिए जाने पर, उत्तर-निर्देशित विशेष ट्रांसमिशन राज्य (1100) में परिवर्तित हो जाएगा | ||
*** एस में | *** एस में सेल<sub>10</sub>राज्य, इनपुट दिया गया, पश्चिम-निर्देशित विशेष ट्रांसमिशन राज्य (1101) में परिवर्तित हो जाएगा | ||
** एस में | ** एस में सेल<sub>1</sub>राज्य, इनपुट दिया गया, एस में परिवर्तित हो जाएगा<sub>11</sub>राज्य (111) | ||
*** एस में | *** एस में सेल<sub>11</sub>राज्य, कोई इनपुट नहीं दिए जाने पर, दक्षिण-निर्देशित विशेष ट्रांसमिशन राज्य (1110) में परिवर्तित हो जाएगा | ||
*** एस में | *** एस में सेल<sub>11</sub>राज्य, इनपुट दिया गया है, शांत संगम राज्य सी में परिवर्तित हो जाएगा<sub>00</sub>(1111) | ||
ध्यान दें कि: | ध्यान दें कि: | ||
* अन्य राज्यों की तुलना में पूर्व या उत्तर-निर्देशित सामान्य ट्रांसमिशन राज्य का निर्माण करने के लिए इनपुट के | * अन्य राज्यों की तुलना में पूर्व या उत्तर-निर्देशित सामान्य ट्रांसमिशन राज्य का निर्माण करने के लिए इनपुट के और चक्र (प्रारंभिक संवेदीकरण के बाद चार) की आवश्यकता होती है (जिसमें प्रारंभिक संवेदीकरण के बाद इनपुट के तीन चक्र की आवश्यकता होती है), | ||
* निर्माण के परिणामस्वरूप डिफ़ॉल्ट शांत स्थिति पूर्व-निर्देशित सामान्य ट्रांसमिशन स्थिति है - जिसके लिए प्रारंभिक संवेदीकरण इनपुट की आवश्यकता होती है, और फिर बिना किसी इनपुट के चार चक्र होते हैं। | * निर्माण के परिणामस्वरूप डिफ़ॉल्ट शांत स्थिति पूर्व-निर्देशित सामान्य ट्रांसमिशन स्थिति है - जिसके लिए प्रारंभिक संवेदीकरण इनपुट की आवश्यकता होती है, और फिर बिना किसी इनपुट के चार चक्र होते हैं। | ||
=== विनाश नियम === | === विनाश नियम === | ||
[[File:Pixel golly.gif|thumb|एक घुमावदार टेप में लगभग 4000 बिट डेटा | [[File:Pixel golly.gif|thumb|एक घुमावदार टेप में लगभग 4000 बिट डेटा जटिल पैटर्न का निर्माण करता है। यह वॉन न्यूमैन सेलुलर ऑटोमेटा की 32-राज्य भिन्नता का उपयोग करता है जिसे हटन32 के नाम से जाना जाता है।]]* विशेष-संचरण राज्य सेल से कंफ्लुएंट-स्टेट सेल में इनपुट के परिणामस्वरूप कंफ्लुएंट राज्य सेल वापस जमीनी स्थिति में आ जाएगा। | ||
* इसी तरह, | * इसी तरह, विशेष-ट्रांसमिशन राज्य सेल से साधारण ट्रांसमिशन-स्टेट सेल में इनपुट के परिणामस्वरूप साधारण-ट्रांसमिशन राज्य सेल वापस जमीनी स्थिति में आ जाएगा। | ||
* इसके विपरीत, | * इसके विपरीत, साधारण-ट्रांसमिशन राज्य सेल से विशेष ट्रांसमिशन-स्टेट सेल में इनपुट के परिणामस्वरूप विशेष-ट्रांसमिशन राज्य सेल वापस जमीनी स्थिति में आ जाएगा। | ||
==यह भी देखें== | ==यह भी देखें== | ||
| Line 116: | Line 116: | ||
==संदर्भ== | ==संदर्भ== | ||
* Von Neumann, J. and A. W. Burks (1966). Theory of self-reproducing automata. Urbana, University of Illinois Press. | * Von Neumann, J. and A. W. Burks (1966). Theory of self-reproducing automata. Urbana, University of Illinois Press. [https://web.archive.org/web/20080613231120/http://www.walenz.org/vonNeumann/index.html] | ||
==बाहरी संबंध== | ==बाहरी संबंध== | ||
*[http://golly.sourceforge.net Golly] - supports von Neumann's CA along with the [[Conway's Game of Life|Game of Life]], and other rulesets. | *[http://golly.sourceforge.net Golly] - supports von Neumann's CA along with the [[Conway's Game of Life|Game of Life]], and other rulesets. | ||
Revision as of 23:00, 10 August 2023
वॉन न्यूमैन के सेलुलर ऑटोमेटन में सरल विन्यास। उत्तेजित और शांत सामान्य ट्रांसमिशन स्थितियों का उपयोग करते हुए, बाइनरी सिग्नल को नीले तार लूप के चारों ओर बार-बार पारित किया जाता है। संगम सेल विशेष ट्रांसमिशन राज्यों से युक्त लाल तार की लंबाई पर सिग्नल को डुप्लिकेट करता है। सिग्नल इस तार से होकर गुजरता है और अंत में नए सेल का निर्माण करता है। यह विशेष सिग्नल (1011) पूर्व-निर्देशित विशेष ट्रांसमिशन स्थिति के लिए कोड करता है, इस प्रकार हर बार लाल तार को सेल तक विस्तारित करता है। निर्माण के दौरान, नई कोशिका बाइनरी अनुक्रम द्वारा निर्देशित कई संवेदनशील अवस्थाओं से गुजरती है।
वॉन न्यूमैन सेलुलर ऑटोमेटा सेलुलर ऑटोमेटा की मूल अभिव्यक्ति है, जिसके विकास को जॉन वॉन न्यूमैन को उनके करीबी दोस्त और साथी गणितज्ञ स्टैनिस्लाव मछुआरे द्वारा दिए गए सुझावों से प्रेरित किया गया था। उनका मूल उद्देश्य स्व-प्रतिकृति मशीन | मशीन स्व-प्रतिकृति के लिए तार्किक आवश्यकताओं में अंतर्दृष्टि प्रदान करना था, और उनका उपयोग वॉन न्यूमैन के वॉन न्यूमैन यूनिवर्सल कंस्ट्रक्टर में किया गया था।
नोबिली सेल्यूलर आटोमेटा|नोबिली का सेल्युलर ऑटोमेटन वॉन न्यूमैन के सेल्युलर ऑटोमेटन का रूप है, जो सिग्नलों को पार करने और जानकारी संग्रहीत करने के लिए संगम कोशिकाओं की क्षमता के साथ संवर्धित है। पूर्व को अतिरिक्त तीन राज्यों की आवश्यकता होती है, इसलिए नोबिली के सेलुलर ऑटोमेटन में 29 के बजाय 32 राज्य होते हैं। हटन का सेलुलर ऑटोमेटन और भिन्नता है, जो लैंगटन के लूप के अनुरूप डेटा के लूप को दोहराने की अनुमति देता है।
परिभाषा
कॉन्फ़िगरेशन
सामान्य तौर पर, सेलुलर ऑटोमेटा (सीए) परिमित राज्य मशीन (एफएसए) की व्यवस्था का गठन करती है जो दूसरे के बीच स्थितीय संबंधों में बैठती है, प्रत्येक एफएसए उन अन्य एफएसए के साथ जानकारी का आदान-प्रदान करता है जिनके साथ यह स्थितिगत रूप से जुड़ा हुआ है। वॉन न्यूमैन के सेलुलर ऑटोमेटन में, परिमित राज्य मशीनें (या कोशिकाएं) दो-आयामी कार्टेशियन ग्रिड में व्यवस्थित होती हैं, और आसपास की चार कोशिकाओं के साथ इंटरफेस करती हैं। चूंकि वॉन न्यूमैन का सेलुलर ऑटोमेटन इस व्यवस्था का उपयोग करने वाला पहला उदाहरण था, इसे [[वॉन न्यूमैन पड़ोस]] के रूप में जाना जाता है।
एफएसए का सेट अनंत आकार के सेल स्पेस को परिभाषित करता है। सभी एफएसए राज्य-संक्रमण फ़ंक्शन, या नियम-सेट के संदर्भ में समान हैं।
वॉन न्यूमैन पड़ोस (एक समूहीकरण फ़ंक्शन) राज्य-संक्रमण फ़ंक्शन का हिस्सा है, और किसी भी सेल के लिए अन्य कोशिकाओं के सेट को परिभाषित करता है जिस पर उस सेल की स्थिति निर्भर करती है।
सभी कोशिकाएं तुल्यकालिक डिजिटल सर्किट की तरह, सार्वभौमिक घड़ी के साथ कदम मिलाकर, तुल्यकालिक रूप से अपना संक्रमण करती हैं।
राज्य
वॉन न्यूमैन सेल स्पेस का प्रत्येक एफएसए नियम-सेट के 29 राज्यों में से किसी को भी स्वीकार कर सकता है। नियम-सेट को पांच ऑर्थोगोनल उपसमुच्चय में बांटा गया है। प्रत्येक अवस्था में सेल्यूलर ऑटोमेटा प्रोग्राम गॉली में सेल का रंग (लाल, हरा, नीला) शामिल होता है। वे हैं
- एक जमीनी अवस्था यू (48, 48, 48)
- संक्रमण या संवेदी अवस्थाएँ (8 उप-अवस्थाओं में)
- IS (नव संवेदीकरण) (255, 0, 0)
- एस0- (संवेदनशील, चक्र के लिए कोई इनपुट प्राप्त नहीं हुआ) (255, 125, 0)
- एस00- (संवेदनशील, दो चक्रों तक कोई इनपुट नहीं मिला) (255, 175, 50)
- एस000- (संवेदनशील, तीन चक्रों तक कोई इनपुट नहीं मिला) (251, 255, 0)
- एस01- (संवेदनशील, चक्र के लिए कोई इनपुट नहीं मिला और फिर चक्र के लिए इनपुट) (255, 200, 75)
- एस1- (संवेदनशील, चक्र के लिए इनपुट प्राप्त होने पर) (255, 150, 25)
- एस10- (संवेदनशील, चक्र के लिए इनपुट प्राप्त हुआ और फिर चक्र के लिए कोई इनपुट नहीं) (255, 255, 100)
- एस11- (संवेदनशील, दो चक्रों के लिए इनपुट प्राप्त करने के बाद) (255, 250, 125)
- संगम अवस्थाएँ (उत्तेजना की 4 अवस्थाओं में)
- सी00- शांत (और अगले चक्र में भी शांत रहेगा) (0, 255, 128)
- सी01- अगले-उत्साहित (अब शांत, लेकिन अगले चक्र में उत्साहित होंगे) (33, 215, 215)
- सी10- उत्साहित (लेकिन अगले चक्र में शांत हो जाऊंगा) (255, 255, 128)
- सी11– उत्साहित अगले-उत्साहित (वर्तमान में उत्साहित और अगले चक्र में उत्साहित होंगे) (255, 128, 64)
- सामान्य संचरण अवस्थाएँ (4 दिशाओं में, उत्तेजित या शांत, 8 अवस्थाएँ बनाती हैं)
- उत्तर दिशा की ओर (उत्साहित और शांत) (36, 200, 36) (106, 106, 255)
- दक्षिण दिशा की ओर (उत्साहित और शांत) (106, 255, 106) (139, 139, 255)
- पश्चिम दिशा की ओर (उत्साहित और शांत) (73, 255, 73) (122, 122, 255)
- पूर्व दिशा की ओर (उत्साहित और शांत) (27, 176, 27) (89, 89, 255)
- विशेष संचरण अवस्थाएँ (4 दिशाओं में, उत्तेजित या शांत, 8 अवस्थाएँ बनाती हैं)
- उत्तर दिशा की ओर (उत्साहित और शांत) (191, 73, 255) (255, 56, 56)
- दक्षिण दिशा की ओर (उत्साहित और शांत) (203, 106, 255) (255, 89, 89)
- पश्चिम दिशा की ओर (उत्साहित और शांत) (197, 89, 255) (255, 73, 73)
- पूर्व दिशा की ओर (उत्साहित और शांत) (185, 56, 255) (235, 36, 36)
उत्साहित राज्य प्रति राज्य संक्रमण चरण में बिट की दर से डेटा ले जाते हैं।
ध्यान दें कि संगम राज्यों में एक-चक्र विलंब की संपत्ति होती है, इस प्रकार किसी भी समय डेटा के दो बिट प्रभावी ढंग से रखे जाते हैं।
ट्रांसमिशन राज्य नियम
कोशिकाओं के बीच बिट्स का प्रवाह दिशा गुण द्वारा दर्शाया जाता है। निम्नलिखित नियम लागू होते हैं:
- ट्रांसमिशन स्थिति इनपुट पर OR ऑपरेटर लागू करती है, जिसका अर्थ है कि ट्रांसमिशन स्थिति (सामान्य या विशेष) में सेल समय t+1 पर उत्तेजित होगी यदि इसकी ओर इशारा करने वाले इनपुट में से कोई भी समय t पर उत्साहित है।
- डेटा ए की दिशा संपत्ति के अनुसार, सामान्य ट्रांसमिशन स्थिति में सेल ए से आसन्न सेल बी में गुजरता है (जब तक कि बी को भी ए की ओर निर्देशित नहीं किया जाता है, जिस स्थिति में डेटा गायब हो जाता है)।
- डेटा विशेष ट्रांसमिशन स्थिति में सेल ए से विशेष ट्रांसमिशन स्थिति में आसन्न सेल बी में सामान्य ट्रांसमिशन राज्यों के समान नियमों के अनुसार गुजरता है।
- ट्रांसमिशन अवस्थाओं के दो उपसमूह, सामान्य और विशेष, परस्पर विरोधी हैं:
- उत्तेजित सामान्य संचरण अवस्था में समय t पर सेल A दिया गया है
- किसी विशेष संचरण अवस्था में सेल बी की ओर इशारा करना
- समय पर t+1 सेल B जमीनी अवस्था बन जाएगा। विशेष ट्रांसमिशन सेल नष्ट हो गया है.
- एक समान अनुक्रम विशेष ट्रांसमिशन स्थिति में सेल के मामले में घटित होगा जो सामान्य ट्रांसमिशन स्थिति में सेल की ओर इशारा करता है
संगम राज्य नियम
निम्नलिखित विशिष्ट नियम संगम राज्यों पर लागू होते हैं:
- संगम राज्य दूसरे के बीच डेटा पास नहीं करते हैं।
- कंफ्लुएंट राज्य या अधिक सामान्य ट्रांसमिशन राज्यों से इनपुट लेते हैं, और आउटपुट को ट्रांसमिशन राज्यों, सामान्य और विशेष, में वितरित करते हैं, जो कंफ्लुएंट राज्य की ओर निर्देशित नहीं होते हैं।
- डेटा ट्रांसमिशन स्टेट डायरेक्शन प्रॉपर्टी के विरुद्ध प्रसारित नहीं होता है।
- यदि उस राज्य में कोई आसन्न ट्रांसमिशन स्थिति नहीं है जो कि संगम राज्य पर इंगित नहीं है तो संगम राज्य द्वारा रखा गया डेटा खो जाता है।
- इस प्रकार, संगम-अवस्था कोशिकाओं का उपयोग सामान्य-से-विशेष-संचरण राज्य कोशिकाओं की ट्रांसमिशन लाइनों से पुल के रूप में किया जाता है।
- संगम अवस्था इनपुट पर AND ऑपरेटर लागू करती है, केवल तभी उत्तेजित इनपुट को बचाती है जब सभी संभावित इनपुट साथ उत्तेजित होते हैं।
- कंफ्लुएंट कोशिकाएं ओटीएस कोशिकाओं की तुलना में संकेतों में पीढ़ी अधिक देरी करती हैं; समता (गणित) बाधाओं के कारण यह आवश्यक है।
निर्माण नियम
नौ कोशिका प्रकार जिनका निर्माण वॉन न्यूमैन के सीए में किया जा सकता है। यहां, बाइनरी सिग्नल नौ सामान्य ट्रांसमिशन लाइनों से गुजरते हैं, और अंत में जमीनी स्थिति का सामना करने पर नई सेल का निर्माण करते हैं। उदाहरण के लिए, बाइनरी स्ट्रिंग 1011 को पांचवीं पंक्ति पर दिखाया गया है, और पूर्व-निर्देशित विशेष ट्रांसमिशन स्थिति का निर्माण करता है - यह वही प्रक्रिया है जो इस पृष्ठ के शीर्ष पर ऑटोमेटन में उपयोग की जाती है। ध्यान दें कि पड़ोसी तारों के बीच कोई इंटरैक्शन नहीं है, उदाहरण के लिए वायरवर्ल्ड के विपरीत, घटकों की कॉम्पैक्ट पैकिंग की अनुमति देता है।
प्रारंभ में, सेल-स्पेस का अधिकांश भाग, सेलुलर ऑटोमेटन का ब्रह्मांड, खाली होता है, जिसमें जमीनी अवस्था यू में कोशिकाएं शामिल होती हैं। जब किसी पड़ोसी सामान्य- या विशेष संचरण अवस्था से इनपुट उत्तेजना दी जाती है, तो जमीनी अवस्था में कोशिका बन जाती है संवेदनशील, अवस्थाओं की शृंखला से गुजरते हुए अंततः शांत संचरण या संगम अवस्था में विश्राम करने से पहले।
सेल किस गंतव्य राज्य तक पहुंचेगा इसका चुनाव इनपुट संकेतों के अनुक्रम से निर्धारित होता है। इसलिए, संक्रमण/संवेदी अवस्थाओं को द्विभाजन सिद्धांत वृक्ष के नोड्स के रूप में माना जा सकता है जो जमीनी अवस्था से प्रत्येक शांत संचरण और संगम अवस्था की ओर जाता है।
निम्नलिखित ट्री में, इनपुट का क्रम प्रत्येक चरण के बाद बाइनरी स्ट्रिंग के रूप में दिखाया गया है:
- जमीनी अवस्था यू में कोशिका, इनपुट दिए जाने पर, अगले चक्र में एस (नव संवेदी) अवस्था में परिवर्तित हो जाएगी (1)
- S अवस्था में सेल, बिना कोई इनपुट दिए, S में परिवर्तित हो जाएगा0राज्य (10)
- एस में सेल0राज्य, कोई इनपुट नहीं दिए जाने पर, एस में परिवर्तित हो जाएगा00राज्य (100)
- एस में सेल00राज्य, कोई इनपुट नहीं दिए जाने पर, एस में परिवर्तित हो जाएगा000राज्य (1000)
- एस में सेल000राज्य, कोई इनपुट नहीं दिए जाने पर, पूर्व-निर्देशित सामान्य ट्रांसमिशन राज्य (10000) में परिवर्तित हो जाएगा
- एस में सेल000राज्य, इनपुट दिया गया, उत्तर-निर्देशित सामान्य ट्रांसमिशन राज्य (10001) में परिवर्तित हो जाएगा
- एस में सेल00राज्य, इनपुट दिया गया, पश्चिम-निर्देशित सामान्य ट्रांसमिशन राज्य (1001) में परिवर्तित हो जाएगा
- एस में सेल00राज्य, कोई इनपुट नहीं दिए जाने पर, एस में परिवर्तित हो जाएगा000राज्य (1000)
- एस में सेल0राज्य, इनपुट दिया गया, एस में परिवर्तित हो जाएगा01राज्य (101)
- एस में सेल01राज्य, कोई इनपुट नहीं दिए जाने पर, दक्षिण-निर्देशित सामान्य ट्रांसमिशन राज्य (1010) में परिवर्तित हो जाएगा
- एस में सेल01राज्य, इनपुट दिया गया, पूर्व-निर्देशित विशेष ट्रांसमिशन राज्य (1011) में परिवर्तित हो जाएगा
- एस में सेल0राज्य, कोई इनपुट नहीं दिए जाने पर, एस में परिवर्तित हो जाएगा00राज्य (100)
- S अवस्था में सेल, इनपुट दिए जाने पर, S में परिवर्तित हो जाएगा1राज्य (11)
- एस में सेल1राज्य, कोई इनपुट नहीं दिए जाने पर, एस में परिवर्तित हो जाएगा10राज्य (110)
- एस में सेल10राज्य, कोई इनपुट नहीं दिए जाने पर, उत्तर-निर्देशित विशेष ट्रांसमिशन राज्य (1100) में परिवर्तित हो जाएगा
- एस में सेल10राज्य, इनपुट दिया गया, पश्चिम-निर्देशित विशेष ट्रांसमिशन राज्य (1101) में परिवर्तित हो जाएगा
- एस में सेल1राज्य, इनपुट दिया गया, एस में परिवर्तित हो जाएगा11राज्य (111)
- एस में सेल11राज्य, कोई इनपुट नहीं दिए जाने पर, दक्षिण-निर्देशित विशेष ट्रांसमिशन राज्य (1110) में परिवर्तित हो जाएगा
- एस में सेल11राज्य, इनपुट दिया गया है, शांत संगम राज्य सी में परिवर्तित हो जाएगा00(1111)
- एस में सेल1राज्य, कोई इनपुट नहीं दिए जाने पर, एस में परिवर्तित हो जाएगा10राज्य (110)
ध्यान दें कि:
- अन्य राज्यों की तुलना में पूर्व या उत्तर-निर्देशित सामान्य ट्रांसमिशन राज्य का निर्माण करने के लिए इनपुट के और चक्र (प्रारंभिक संवेदीकरण के बाद चार) की आवश्यकता होती है (जिसमें प्रारंभिक संवेदीकरण के बाद इनपुट के तीन चक्र की आवश्यकता होती है),
- निर्माण के परिणामस्वरूप डिफ़ॉल्ट शांत स्थिति पूर्व-निर्देशित सामान्य ट्रांसमिशन स्थिति है - जिसके लिए प्रारंभिक संवेदीकरण इनपुट की आवश्यकता होती है, और फिर बिना किसी इनपुट के चार चक्र होते हैं।
विनाश नियम
* विशेष-संचरण राज्य सेल से कंफ्लुएंट-स्टेट सेल में इनपुट के परिणामस्वरूप कंफ्लुएंट राज्य सेल वापस जमीनी स्थिति में आ जाएगा।
- इसी तरह, विशेष-ट्रांसमिशन राज्य सेल से साधारण ट्रांसमिशन-स्टेट सेल में इनपुट के परिणामस्वरूप साधारण-ट्रांसमिशन राज्य सेल वापस जमीनी स्थिति में आ जाएगा।
- इसके विपरीत, साधारण-ट्रांसमिशन राज्य सेल से विशेष ट्रांसमिशन-स्टेट सेल में इनपुट के परिणामस्वरूप विशेष-ट्रांसमिशन राज्य सेल वापस जमीनी स्थिति में आ जाएगा।
यह भी देखें
- कॉड का सेलुलर ऑटोमेटन
- लैंग्टन के लूप
- वॉन न्यूमैन यूनिवर्सल कंस्ट्रक्टर
- वायरवर्ल्ड
संदर्भ
- Von Neumann, J. and A. W. Burks (1966). Theory of self-reproducing automata. Urbana, University of Illinois Press. [1]
बाहरी संबंध
- Golly - supports von Neumann's CA along with the Game of Life, and other rulesets.
