बहुसंख्यक समस्या: Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
 
(3 intermediate revisions by 3 users not shown)
Line 1: Line 1:
बहुमत समस्या, या घनत्व वर्गीकरण कार्य, एक-आयामी [[सेलुलर ऑटोमेटन]] नियमों को खोजने की समस्या है जो बहुमत कार्य को सटीक रूप से निष्पादित करते हैं।
'''बहुसंख्यक समस्या''', या घनत्व वर्गीकरण कार्य, एक-आयामी [[सेलुलर ऑटोमेटन]] के नियमों को खोजने की ऐसी समस्या है, जिसका उपयोग बहुसंख्यक कार्यों को सटीक रूप से निष्पादित करने के लिए किया जाता हैं।


स्थानीय संक्रमण नियमों का उपयोग करते हुए, कोशिकाएँ सिस्टम में सभी की कुल संख्या नहीं जान सकती हैं। इकाइयों की संख्या (या, समरूपता द्वारा, शून्य की संख्या) की गणना करने के लिए, सिस्टम को सिस्टम के कुल आकार में बिट्स की लघुगणकीय संख्या की आवश्यकता होती है। इसके लिए सिस्टम को सिस्टम के आकार में रैखिक दूरी पर संदेश भेजने और सिस्टम को गैर-[[नियमित भाषा]] को पहचानने की भी आवश्यकता होती है। इस प्रकार, यह समस्या सेलुलर ऑटोमेटन सिस्टम की कम्प्यूटेशनल शक्ति को मापने में महत्वपूर्ण परीक्षण मामला है।
स्थानीय संक्रमण नियमों का उपयोग करते हुए इस प्रकार की कोशिकाएँ उक्त प्रणाली में कुल संख्या का पता नहीं लगा सकते हैं। इन इकाइयों की संख्या या, समरूपता द्वारा, शून्य की संख्या की गणना करने के लिए इस प्रणाली को कुल आकार में बिट्स की लघुगणकीय संख्या की आवश्यकता होती है। इसके लिए उक्त प्रणाली के आकार में रैखिक दूरी पर संदेश को भेजने और इस प्रकार के उपकरण को [[नियमित भाषा|नाॅन रेगुलर लैंग्वेज]] को पहचानने की भी आवश्यकता होती है। इस प्रकार यह समस्या सेलुलर ऑटोमेटन सिस्टम की कम्प्यूटेशनल शक्ति को मापने में महत्वपूर्ण परीक्षण स्थिति है।


== समस्या कथन ==
== समस्या कथन ==


कुल मिलाकर i + j कोशिकाओं के साथ दो-राज्य सेलुलर ऑटोमेटन के कॉन्फ़िगरेशन को देखते हुए, जिनमें से i शून्य स्थिति में हैं और जिनमें से j स्थिति में हैं, वोटिंग समस्या का सही समाधान अंततः सभी कोशिकाओं को शून्य पर सेट करना होगा यदि i > j और यदि i <j हो तो अंततः सभी कोशिकाओं को पर सेट करना होगा। यदि i=j हो तो वांछित अंतिम स्थिति अनिर्दिष्ट है।
कुल मिलाकर यदि इस बात पर ध्यान केंद्रित करे तो हम पायेंगे कि i + j कोशिकाओं के साथ दो स्थितियों के सेलुलर ऑटोमेटन के कॉन्फ़िगरेशन को देखते हुए, जिनमें से i का मान शून्य रहता हैं और जिनमें से j स्थिति में हैं, इसके आधार पर वोटिंग समस्या का सही हल अंततः सभी कोशिकाओं को शून्य पर सेट करना होगा, इसके कारण यदि i > j और यदि i <j हो तो अंततः सभी कोशिकाओं को पर सेट करना होगा। इस प्रकार i=j हो तो वांछित अंतिम स्थिति अनिर्दिष्ट हो जाती है।


समस्या को यह परीक्षण करने के लिए भी सामान्यीकृत किया जा सकता है कि क्या शून्य और का अनुपात 50% के अलावा किसी सीमा से ऊपर या नीचे है। इस सामान्यीकरण में भी दिया गया है
इस समस्या के इस परीक्षण को करने के लिए भी इसे सामान्यीकृत किया जा सकता है कि क्या शून्य और का अनुपात 50% के अतिरिक्त किसी सीमा से ऊपर या नीचे है। इस सामान्यीकरण में भी दिया गया है।
एक दहलीज <math>\rho</math>; मतदान समस्या के सही समाधान के लिए अंततः सभी कोशिकाओं को शून्य पर सेट करना होगा <math>\tfrac{i}{i+j} < \rho</math> और अंततः सभी कोशिकाओं को पर सेट करना होगा <math>\tfrac{j}{i+j} > \rho</math>. यदि वांछित अंतिम स्थिति अनिर्दिष्ट है <math>\tfrac{j}{i+j} = \rho</math>.
 
इसकी उच्च सीमा <math>\rho</math> होने पर इस प्रकार की समस्या के सही हल को प्राप्त करने के लिए अंततः सभी कोशिकाओं को शून्य पर सेट करना होगा, इस प्रकार <math>\tfrac{i}{i+j} < \rho</math> और अंततः सभी कोशिकाओं को <math>\tfrac{j}{i+j} > \rho</math> पर सेट करना होगा, यदि वांछित अंतिम स्थिति <math>\tfrac{j}{i+j} = \rho</math> अनिर्दिष्ट है।


== अनुमानित समाधान ==
== अनुमानित समाधान ==
[[File:Gacs kurdyumov levin majority.gif|left|thumb|256px|Gács, Kurdyumov, लेविन एल्गोरिथम का 2D विस्तार। यादृच्छिक आरंभिक सेट में सफ़ेद पिक्सेल कुल का केवल 52% हैं।]]गैक्स, कुर्द्युमोव और [[लियोनिद लेविन]] ने ऑटोमेटन पाया, जो हालांकि हमेशा बहुमत की समस्या को सही ढंग से हल नहीं करता है, लेकिन कई मामलों में ऐसा करता है।<ref>{{cite journal|last1=Gács|first1=Péter|last2= Kurdyumov|first2=G. L.|author3-link=Leonid Levin|last3=Levin|first3=L. A.|year=1978|title=एक आयामी एकसमान सरणियाँ जो परिमित द्वीपों को धो देती हैं|journal=Problemy Peredachi Informatsii|volume=14|pages=92–98|language=Russian|url=http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=ppi&paperid=1551&option_lang=eng}}</ref> समस्या के प्रति उनके दृष्टिकोण में,
[[File:Gacs kurdyumov levin majority.gif|left|thumb|256px|Gács, Kurdyumov, लेविन एल्गोरिथम का 2D विस्तार। यादृच्छिक आरंभिक सेट में सफ़ेद पिक्सेल कुल का केवल 52% हैं।]]गैक्स, कुर्द्युमोव और [[लियोनिद लेविन]] ने ऑटोमेटन पाया, जो चूंकि सदैव बहुसंख्यक की समस्या को सही विधि से हल नहीं करता है, किन्तु कई स्थितियों में ऐसा करता है।<ref>{{cite journal|last1=Gács|first1=Péter|last2= Kurdyumov|first2=G. L.|author3-link=Leonid Levin|last3=Levin|first3=L. A.|year=1978|title=एक आयामी एकसमान सरणियाँ जो परिमित द्वीपों को धो देती हैं|journal=Problemy Peredachi Informatsii|volume=14|pages=92–98|language=Russian|url=http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=ppi&paperid=1551&option_lang=eng}}</ref> इस प्रकार की समस्या के लिए प्रति दृष्टिकोण में, सेलुलर ऑटोमेटन नियम की गुणवत्ता को इसके अंश <math>2^{i+j}</math> द्वारा मापा जाता है, इस प्रकार संभावित प्रारंभिक कॉन्फ़िगरेशन जिन्हें यह सही विधि से वर्गीकृत करता है।
सेलुलर ऑटोमेटन नियम की गुणवत्ता को इसके अंश द्वारा मापा जाता है <math>2^{i+j}</math> संभावित प्रारंभिक कॉन्फ़िगरेशन जिन्हें यह सही ढंग से वर्गीकृत करता है।
 
गैक्स, कुर्द्युमोव और लेविन द्वारा प्रस्तावित नियम प्रत्येक कोशिका की स्थिति को निम्नानुसार निर्धारित करता है। यदि कोई सेल 0 है, तो इसकी अगली स्थिति स्वयं के मानों के बीच बहुमत के रूप में बनती है, बाईं ओर इसका निकटतम पड़ोसी, और बाईं ओर इसका पड़ोसी तीन स्थान। दूसरी ओर, यदि सेल 1 है, तो इसकी अगली स्थिति सममित रूप से बनती है, स्वयं के मूल्यों के बीच बहुमत के रूप में, दाईं ओर इसका निकटतम पड़ोसी, और दाईं ओर इसका पड़ोसी तीन स्थान। बेतरतीब ढंग से उत्पन्न उदाहरणों में, यह बहुमत को सही ढंग से निर्धारित करने में लगभग 78% सटीकता प्राप्त करता है।
 
दास, [[मेलानी मिशेल]] और क्रचफ़ील्ड ने दिखाया कि आनुवंशिक एल्गोरिदम का उपयोग करके बेहतर नियम विकसित करना संभव है।<ref>{{cite conference|last1=Das|first1=Rajarshi|last2=Crutchfield|first2=J. P.|author3-link=Melanie Mitchell|last3=Mitchell|first3=Melanie|last4=Hanson|first4=J. E.|date=1995|title=विश्व स्तर पर सिंक्रनाइज़ सेलुलर ऑटोमेटा का विकास|editor-last=Eshelman|editor-first=Larry J.|work=Proceedings of the Sixth International Conference on Genetic Algorithms|location=San Francisco|publisher=Morgan Kaufmann|url=https://melaniemitchell.me/PapersContent/EGSCA.pdf}}</ref>


गैक्स, कुर्द्युमोव और लेविन द्वारा प्रस्तावित नियम प्रत्येक कोशिका की स्थिति को निम्नानुसार निर्धारित करता है। यदि कोई सेल 0 है, तो इसकी अगली स्थिति स्वयं के मानों के बीच बहुसंख्यक के रूप में बनती है, जिसके बाईं ओर इसका निकटतम और बाईं ओर इसका निकटतम मान तीन स्थान तक रहता हैं। इसके आधार पर दूसरी ओर यदि सेल 1 है, तो इसकी अगली स्थिति सममित रूप से बनती है, स्वयं के मूल्यों के बीच बहुसंख्यक के रूप में, दाईं ओर इसका निकटतम मान, और दाईं ओर इसका निकटतम मान तीन स्थान तक होता हैं। इस प्रकार विचित्र तरीके से जब इस प्रकार से उत्पन्न उदाहरणों की बात करते हैं तो यह बहुसंख्यक को सही विधि से निर्धारित करने में लगभग 78% मान सही प्राप्त करता है।


दास, [[मेलानी मिशेल]] और क्रचफ़ील्ड ने दिखाया कि आनुवंशिक एल्गोरिदम का उपयोग करके इसका उत्तम नियम विकसित करना संभव है।<ref>{{cite conference|last1=Das|first1=Rajarshi|last2=Crutchfield|first2=J. P.|author3-link=Melanie Mitchell|last3=Mitchell|first3=Melanie|last4=Hanson|first4=J. E.|date=1995|title=विश्व स्तर पर सिंक्रनाइज़ सेलुलर ऑटोमेटा का विकास|editor-last=Eshelman|editor-first=Larry J.|work=Proceedings of the Sixth International Conference on Genetic Algorithms|location=San Francisco|publisher=Morgan Kaufmann|url=https://melaniemitchell.me/PapersContent/EGSCA.pdf}}</ref>
== एक पूर्ण वर्गीकारक की असंभवता ==
== एक पूर्ण वर्गीकारक की असंभवता ==


1995 में, लैंड और बेलेव<ref>{{cite journal|last1=Land|first1=Mark|last2=Belew|first2=Richard|title=घनत्व वर्गीकरण के लिए कोई आदर्श दो-राज्य सेलुलर ऑटोमेटा मौजूद नहीं है|journal=Physical Review Letters|volume=74|issue=25|year=1995|pages=1548–1550|doi=10.1103/PhysRevLett.74.5148|pmid=10058695|bibcode=1995PhRvL..74.5148L}}</ref> पता चला कि त्रिज्या आर और घनत्व ρ के साथ कोई भी दो-राज्य नियम सभी प्रारंभिक कॉन्फ़िगरेशन पर वोटिंग समस्या को सही ढंग से हल नहीं करता है जब कोशिकाओं की संख्या पर्याप्त रूप से बड़ी होती है (लगभग 4r/ρ से बड़ी)।
1995 में, लैंड और बेलेव<ref>{{cite journal|last1=Land|first1=Mark|last2=Belew|first2=Richard|title=घनत्व वर्गीकरण के लिए कोई आदर्श दो-राज्य सेलुलर ऑटोमेटा मौजूद नहीं है|journal=Physical Review Letters|volume=74|issue=25|year=1995|pages=1548–1550|doi=10.1103/PhysRevLett.74.5148|pmid=10058695|bibcode=1995PhRvL..74.5148L}}</ref> पता चला कि त्रिज्या आर और घनत्व ρ के साथ कोई भी दो स्थितियों के लिए उक्त नियम के आधार पर सभी प्रारंभिक कॉन्फ़िगरेशन पर वोटिंग समस्या को सही विधि से हल नहीं करता है, जब कोशिकाओं की संख्या लगभग 4r/ρ से बड़ी होती है।


उनके तर्क से पता चलता है कि चूंकि सिस्टम नियतात्मक एल्गोरिदम है, इसलिए पूरी तरह से शून्य या से घिरी प्रत्येक कोशिका को शून्य बनना चाहिए। इसी प्रकार, कोई भी आदर्श नियम कभी भी इकाइयों के अनुपात को ऊपर नहीं ले जा सकता <math>\rho</math> यदि यह नीचे था (या इसके विपरीत)। फिर वे दिखाते हैं कि कोई भी आदर्श आदर्श नियम या तो पृथक नियम का कारण बनेगा जिसने अनुपात को खत्म कर दिया है <math>\rho</math> रद्द किया जाना चाहिए या, यदि लोगों का अनुपात इससे कम है <math>\rho</math>, पृथक शून्य के ब्लॉक में नकली लोगों को शामिल करने का कारण बनेगा जिससे शून्यों का अनुपात इससे अधिक हो जाएगा <math>\rho</math>.
उनके तर्क से पता चलता है कि चूंकि सिस्टम नियतात्मक एल्गोरिदम है, इसलिए पूर्ण रूप से शून्य या से घिरी प्रत्येक कोशिका को शून्य बनना चाहिए। इसी प्रकार, कोई भी आदर्श नियम कभी भी इकाइयों के अनुपात <math>\rho</math> को ऊपर नहीं ले जा सकता, इस प्रकार यदि यह नीचे होता हैं या इसके विपरीत रहता हैं। इसके आधार पर हम देख सकते हैं कि कोई भी आदर्श नियम या तो पृथक नियम का कारण बनेगा जिसने अनुपात को खत्म कर दिया है, जिससे <math>\rho</math> का मान निरस्त किया जाना चाहिए या, यदि लोगों का अनुपात <math>\rho</math> इससे कम है, इस स्थिति में पृथक शून्य के ब्लॉक में नकली लोगों को उपस्थित करने का कारण बनेगा जिससे शून्यों का अनुपात <math>\rho</math> इससे अधिक हो जाएगा।


2013 में, बुसिक, फेटेस, मार्कोविसी और मैरेसे ने आदर्श घनत्व क्लासिफायरियर की असंभवता का सरल प्रमाण दिया, जो नियतात्मक और स्टोकेस्टिक सेलुलर और किसी भी आयाम दोनों के लिए मान्य है।<ref>{{cite journal|last1=Bušić|first1=Ana|last2=Fatès|first2=Nazim|last3=Marcovici|first3=Irène|last4=Mairesse|first4=Jean|title=अनंत जालियों और पेड़ों पर घनत्व वर्गीकरण|journal=Electronic Journal of Probability|volume=51|year=2013|doi=10.1214/EJP.v18-2325|doi-access=free}}</ref>
2013 में, बुसिक, फेटेस, मार्कोविसी और मैरेसे ने आदर्श घनत्व क्लासिफायरियर की असंभवता का सरल प्रमाण दिया, जो नियतात्मक और स्टोकेस्टिक सेलुलर और किसी भी आयाम दोनों के लिए मान्य है।<ref>{{cite journal|last1=Bušić|first1=Ana|last2=Fatès|first2=Nazim|last3=Marcovici|first3=Irène|last4=Mairesse|first4=Jean|title=अनंत जालियों और पेड़ों पर घनत्व वर्गीकरण|journal=Electronic Journal of Probability|volume=51|year=2013|doi=10.1214/EJP.v18-2325|doi-access=free}}</ref>
 
==वैकल्पिक समाप्ति शर्तों के साथ इसका सही हल==
 
==वैकल्पिक समाप्ति शर्तों के साथ सटीक समाधान==
जैसा कि कैपकेरेरे, सिपर और टोमासिनी ने देखा,<ref>{{cite journal
जैसा कि कैपकेरेरे, सिपर और टोमासिनी ने देखा,<ref>{{cite journal
  | last1 = Capcarrere | first1= Mathieu S. | last2= Sipper | first2 = Moshe | last3= Tomassini | first3 = Marco
  | last1 = Capcarrere | first1= Mathieu S. | last2= Sipper | first2 = Moshe | last3= Tomassini | first3 = Marco
Line 44: Line 40:
  | title = Effect of boundary conditions on cellular automata that classify density
  | title = Effect of boundary conditions on cellular automata that classify density
  | year = 1998
  | year = 1998
  | arxiv=comp-gas/9804001|bibcode = 1998comp.gas..4001S }}</ref> बहुमत की समस्या पूरी तरह से हल हो सकती है यदि कोई उस परिभाषा में ढील दे जिसके द्वारा कहा जाता है कि ऑटोमेटन ने बहुमत को पहचान लिया है। विशेष रूप से, [[नियम 184]] ऑटोमेटन के लिए, जब आवधिक सीमा शर्तों के साथ सीमित ब्रह्मांड पर चलाया जाता है, तो प्रत्येक कोशिका अनंत बार लगातार दो चरणों के लिए बहुसंख्यक अवस्था में रहेगी, जबकि केवल कई बार लगातार दो चरणों के लिए अल्पसंख्यक अवस्था में रहेगी।
  | arxiv=comp-gas/9804001|bibcode = 1998comp.gas..4001S }}</ref> बहुसंख्यक की समस्या पूर्ण रूप से हल हो सकती है, जिसके आधार पर यदि कोई उस परिभाषा में इसे छोड़ देता हैं, जिसके द्वारा कहा जाता है कि ऑटोमेटन ने बहुसंख्यक को पहचान लिया है। इसके कारण विशेष रूप से, [[नियम 184]] ऑटोमेटन के लिए, जब आवधिक सीमा शर्तों के साथ सीमित ब्रह्मांड पर चलाया जाता है, तो प्रत्येक कोशिका अनंत बार लगातार दो चरणों के लिए बहुसंख्यक अवस्था में रहेगी, जबकि केवल कई बार लगातार दो चरणों के लिए अल्पसंख्यक अवस्था में रहेगी।


वैकल्पिक रूप से, हाइब्रिड ऑटोमेटन जो सरणी के आकार में रैखिक कई चरणों के लिए नियम 184 चलाता है, और फिर बहुमत नियम (नियम 232) पर स्विच करता है, जो प्रत्येक कोशिका को स्वयं और उसके पड़ोसियों के बहुमत पर सेट करता है, बहुमत को हल करता है या तो सभी शून्यों या अंतिम स्थिति में सभी शून्यों की मानक मान्यता मानदंड के साथ समस्या। हालाँकि, यह मशीन स्वयं सेलुलर ऑटोमेटन नहीं है।<ref>{{Cite journal|title=दो सेलुलर ऑटोमेटा नियमों के साथ घनत्व वर्गीकरण समस्या का समाधान|first=Henryk|last=Fukś|arxiv=comp-gas/9703001|journal=Physical Review E|volume=55|issue=3|year=1997|pages=2081–2084|bibcode = 1997PhRvE..55.2081F |doi=10.1103/physreve.55.r2081 |s2cid=118954791}}</ref> इसके अलावा, यह दिखाया गया है कि फुकस का समग्र नियम शोर के प्रति बहुत संवेदनशील है और शोर के किसी भी स्तर (उदाहरण के लिए, पर्यावरण से या गतिशील गलतियों से) के लिए अपूर्ण वर्गीकरणकर्ता, शोर गैक्स-कुर्द्युमोव-लेविन ऑटोमेटन से बेहतर प्रदर्शन नहीं कर सकता है।<ref>{{Cite journal|title=घनत्व को वर्गीकृत करने वाली सेलुलर ऑटोमेटा की असेंबली लाइन की शोर और एर्गोडिसिटी के प्रति संवेदनशीलता|first=J. R. G.|last=Mendonça|arxiv=1010.0239|journal=Physical Review E|volume=83|issue=3|year=2011|pages=031112|doi=10.1103/PhysRevE.83.031112|pmid=21517459|bibcode=2011PhRvE..83c1112M|s2cid=118494753}}</ref>
वैकल्पिक रूप से हाइब्रिड ऑटोमेटन जो सरणी के आकार में रैखिक कई चरणों के लिए नियम 184 चलाता है, और फिर बहुसंख्यक नियम (नियम 232) पर स्विच करता है, जो प्रत्येक कोशिका को स्वयं और उसके समीपस्थ बहुसंख्यक पर इसे स्थित कर सकता है, इस प्रकार बहुसंख्यक मान को हल करता है या तो सभी शून्यों या अंतिम स्थिति में सभी शून्यों की मानक मान्यता मानदंड के साथ समस्या को हल करता हैं। चूंकि, यह मशीन स्वयं सेलुलर ऑटोमेटन नहीं है।<ref>{{Cite journal|title=दो सेलुलर ऑटोमेटा नियमों के साथ घनत्व वर्गीकरण समस्या का समाधान|first=Henryk|last=Fukś|arxiv=comp-gas/9703001|journal=Physical Review E|volume=55|issue=3|year=1997|pages=2081–2084|bibcode = 1997PhRvE..55.2081F |doi=10.1103/physreve.55.r2081 |s2cid=118954791}}</ref> इसके अतिरिक्त, यह दिखाया गया है कि फुकस का समग्र नियम ध्वनि के प्रति बहुत संवेदनशील है, और ध्वनि के किसी भी स्तर पर उदाहरण के लिए, पर्यावरण से या गतिशील गलतियों के लिए अपूर्ण वर्गीकरणकर्ता, ध्वनि गैक्स-कुर्द्युमोव-लेविन ऑटोमेटन से उत्तम प्रदर्शन नहीं कर सकता है।<ref>{{Cite journal|title=घनत्व को वर्गीकृत करने वाली सेलुलर ऑटोमेटा की असेंबली लाइन की शोर और एर्गोडिसिटी के प्रति संवेदनशीलता|first=J. R. G.|last=Mendonça|arxiv=1010.0239|journal=Physical Review E|volume=83|issue=3|year=2011|pages=031112|doi=10.1103/PhysRevE.83.031112|pmid=21517459|bibcode=2011PhRvE..83c1112M|s2cid=118494753}}</ref>
== संदर्भ ==
== संदर्भ ==
{{Reflist|colwidth=30em}}
{{Reflist|colwidth=30em}}
[[Category: सेल्यूलर आटोमेटा]]


[[Category: Machine Translated Page]]
[[Category:CS1 errors]]
[[Category:CS1 maint]]
[[Category:Created On 09/08/2023]]
[[Category:Created On 09/08/2023]]
[[Category:Machine Translated Page]]
[[Category:Pages with script errors]]
[[Category:Templates Vigyan Ready]]
[[Category:सेल्यूलर आटोमेटा]]

Latest revision as of 09:29, 22 August 2023

बहुसंख्यक समस्या, या घनत्व वर्गीकरण कार्य, एक-आयामी सेलुलर ऑटोमेटन के नियमों को खोजने की ऐसी समस्या है, जिसका उपयोग बहुसंख्यक कार्यों को सटीक रूप से निष्पादित करने के लिए किया जाता हैं।

स्थानीय संक्रमण नियमों का उपयोग करते हुए इस प्रकार की कोशिकाएँ उक्त प्रणाली में कुल संख्या का पता नहीं लगा सकते हैं। इन इकाइयों की संख्या या, समरूपता द्वारा, शून्य की संख्या की गणना करने के लिए इस प्रणाली को कुल आकार में बिट्स की लघुगणकीय संख्या की आवश्यकता होती है। इसके लिए उक्त प्रणाली के आकार में रैखिक दूरी पर संदेश को भेजने और इस प्रकार के उपकरण को नाॅन रेगुलर लैंग्वेज को पहचानने की भी आवश्यकता होती है। इस प्रकार यह समस्या सेलुलर ऑटोमेटन सिस्टम की कम्प्यूटेशनल शक्ति को मापने में महत्वपूर्ण परीक्षण स्थिति है।

समस्या कथन

कुल मिलाकर यदि इस बात पर ध्यान केंद्रित करे तो हम पायेंगे कि i + j कोशिकाओं के साथ दो स्थितियों के सेलुलर ऑटोमेटन के कॉन्फ़िगरेशन को देखते हुए, जिनमें से i का मान शून्य रहता हैं और जिनमें से j स्थिति में हैं, इसके आधार पर वोटिंग समस्या का सही हल अंततः सभी कोशिकाओं को शून्य पर सेट करना होगा, इसके कारण यदि i > j और यदि i <j हो तो अंततः सभी कोशिकाओं को पर सेट करना होगा। इस प्रकार i=j हो तो वांछित अंतिम स्थिति अनिर्दिष्ट हो जाती है।

इस समस्या के इस परीक्षण को करने के लिए भी इसे सामान्यीकृत किया जा सकता है कि क्या शून्य और का अनुपात 50% के अतिरिक्त किसी सीमा से ऊपर या नीचे है। इस सामान्यीकरण में भी दिया गया है।

इसकी उच्च सीमा होने पर इस प्रकार की समस्या के सही हल को प्राप्त करने के लिए अंततः सभी कोशिकाओं को शून्य पर सेट करना होगा, इस प्रकार और अंततः सभी कोशिकाओं को पर सेट करना होगा, यदि वांछित अंतिम स्थिति अनिर्दिष्ट है।

अनुमानित समाधान

Gács, Kurdyumov, लेविन एल्गोरिथम का 2D विस्तार। यादृच्छिक आरंभिक सेट में सफ़ेद पिक्सेल कुल का केवल 52% हैं।

गैक्स, कुर्द्युमोव और लियोनिद लेविन ने ऑटोमेटन पाया, जो चूंकि सदैव बहुसंख्यक की समस्या को सही विधि से हल नहीं करता है, किन्तु कई स्थितियों में ऐसा करता है।[1] इस प्रकार की समस्या के लिए प्रति दृष्टिकोण में, सेलुलर ऑटोमेटन नियम की गुणवत्ता को इसके अंश द्वारा मापा जाता है, इस प्रकार संभावित प्रारंभिक कॉन्फ़िगरेशन जिन्हें यह सही विधि से वर्गीकृत करता है।

गैक्स, कुर्द्युमोव और लेविन द्वारा प्रस्तावित नियम प्रत्येक कोशिका की स्थिति को निम्नानुसार निर्धारित करता है। यदि कोई सेल 0 है, तो इसकी अगली स्थिति स्वयं के मानों के बीच बहुसंख्यक के रूप में बनती है, जिसके बाईं ओर इसका निकटतम और बाईं ओर इसका निकटतम मान तीन स्थान तक रहता हैं। इसके आधार पर दूसरी ओर यदि सेल 1 है, तो इसकी अगली स्थिति सममित रूप से बनती है, स्वयं के मूल्यों के बीच बहुसंख्यक के रूप में, दाईं ओर इसका निकटतम मान, और दाईं ओर इसका निकटतम मान तीन स्थान तक होता हैं। इस प्रकार विचित्र तरीके से जब इस प्रकार से उत्पन्न उदाहरणों की बात करते हैं तो यह बहुसंख्यक को सही विधि से निर्धारित करने में लगभग 78% मान सही प्राप्त करता है।

दास, मेलानी मिशेल और क्रचफ़ील्ड ने दिखाया कि आनुवंशिक एल्गोरिदम का उपयोग करके इसका उत्तम नियम विकसित करना संभव है।[2]

एक पूर्ण वर्गीकारक की असंभवता

1995 में, लैंड और बेलेव[3] पता चला कि त्रिज्या आर और घनत्व ρ के साथ कोई भी दो स्थितियों के लिए उक्त नियम के आधार पर सभी प्रारंभिक कॉन्फ़िगरेशन पर वोटिंग समस्या को सही विधि से हल नहीं करता है, जब कोशिकाओं की संख्या लगभग 4r/ρ से बड़ी होती है।

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

2013 में, बुसिक, फेटेस, मार्कोविसी और मैरेसे ने आदर्श घनत्व क्लासिफायरियर की असंभवता का सरल प्रमाण दिया, जो नियतात्मक और स्टोकेस्टिक सेलुलर और किसी भी आयाम दोनों के लिए मान्य है।[4]

वैकल्पिक समाप्ति शर्तों के साथ इसका सही हल

जैसा कि कैपकेरेरे, सिपर और टोमासिनी ने देखा,[5][6] बहुसंख्यक की समस्या पूर्ण रूप से हल हो सकती है, जिसके आधार पर यदि कोई उस परिभाषा में इसे छोड़ देता हैं, जिसके द्वारा कहा जाता है कि ऑटोमेटन ने बहुसंख्यक को पहचान लिया है। इसके कारण विशेष रूप से, नियम 184 ऑटोमेटन के लिए, जब आवधिक सीमा शर्तों के साथ सीमित ब्रह्मांड पर चलाया जाता है, तो प्रत्येक कोशिका अनंत बार लगातार दो चरणों के लिए बहुसंख्यक अवस्था में रहेगी, जबकि केवल कई बार लगातार दो चरणों के लिए अल्पसंख्यक अवस्था में रहेगी।

वैकल्पिक रूप से हाइब्रिड ऑटोमेटन जो सरणी के आकार में रैखिक कई चरणों के लिए नियम 184 चलाता है, और फिर बहुसंख्यक नियम (नियम 232) पर स्विच करता है, जो प्रत्येक कोशिका को स्वयं और उसके समीपस्थ बहुसंख्यक पर इसे स्थित कर सकता है, इस प्रकार बहुसंख्यक मान को हल करता है या तो सभी शून्यों या अंतिम स्थिति में सभी शून्यों की मानक मान्यता मानदंड के साथ समस्या को हल करता हैं। चूंकि, यह मशीन स्वयं सेलुलर ऑटोमेटन नहीं है।[7] इसके अतिरिक्त, यह दिखाया गया है कि फुकस का समग्र नियम ध्वनि के प्रति बहुत संवेदनशील है, और ध्वनि के किसी भी स्तर पर उदाहरण के लिए, पर्यावरण से या गतिशील गलतियों के लिए अपूर्ण वर्गीकरणकर्ता, ध्वनि गैक्स-कुर्द्युमोव-लेविन ऑटोमेटन से उत्तम प्रदर्शन नहीं कर सकता है।[8]

संदर्भ

  1. ↑ Gács, Péter; Kurdyumov, G. L.; Levin, L. A. (1978). "एक आयामी एकसमान सरणियाँ जो परिमित द्वीपों को धो देती हैं". Problemy Peredachi Informatsii (in Russian). 14: 92–98.{{cite journal}}: CS1 maint: unrecognized language (link)
  2. ↑ Das, Rajarshi; Crutchfield, J. P.; Mitchell, Melanie; Hanson, J. E. (1995). Eshelman, Larry J. (ed.). विश्व स्तर पर सिंक्रनाइज़ सेलुलर ऑटोमेटा का विकास (PDF). Proceedings of the Sixth International Conference on Genetic Algorithms. San Francisco: Morgan Kaufmann.
  3. ↑ Land, Mark; Belew, Richard (1995). "घनत्व वर्गीकरण के लिए कोई आदर्श दो-राज्य सेलुलर ऑटोमेटा मौजूद नहीं है". Physical Review Letters. 74 (25): 1548–1550. Bibcode:1995PhRvL..74.5148L. doi:10.1103/PhysRevLett.74.5148. PMID 10058695.
  4. ↑ Bušić, Ana; Fatès, Nazim; Marcovici, Irène; Mairesse, Jean (2013). "अनंत जालियों और पेड़ों पर घनत्व वर्गीकरण". Electronic Journal of Probability. 51. doi:10.1214/EJP.v18-2325.
  5. ↑ Capcarrere, Mathieu S.; Sipper, Moshe; Tomassini, Marco (1996). "Two-state, r = 1 cellular automaton that classifies density". Phys. Rev. Lett. 77 (24): 4969–4971. Bibcode:1996PhRvL..77.4969C. doi:10.1103/PhysRevLett.77.4969. PMID 10062680.
  6. ↑ Sukumar, N. (1998). "Effect of boundary conditions on cellular automata that classify density". arXiv:comp-gas/9804001. Bibcode:1998comp.gas..4001S. {{cite journal}}: Cite journal requires |journal= (help)
  7. ↑ Fukś, Henryk (1997). "दो सेलुलर ऑटोमेटा नियमों के साथ घनत्व वर्गीकरण समस्या का समाधान". Physical Review E. 55 (3): 2081–2084. arXiv:comp-gas/9703001. Bibcode:1997PhRvE..55.2081F. doi:10.1103/physreve.55.r2081. S2CID 118954791.
  8. ↑ Mendonça, J. R. G. (2011). "घनत्व को वर्गीकृत करने वाली सेलुलर ऑटोमेटा की असेंबली लाइन की शोर और एर्गोडिसिटी के प्रति संवेदनशीलता". Physical Review E. 83 (3): 031112. arXiv:1010.0239. Bibcode:2011PhRvE..83c1112M. doi:10.1103/PhysRevE.83.031112. PMID 21517459. S2CID 118494753.
Retrieved from ‘https://www.vigyanwiki.in/index.php?title=बहुसंख्यक_समस्या&oldid=252044’