बहुसंख्यक समस्या

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

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

समस्या कथन

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

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

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

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

गैक्स, कुर्द्युमोव और लियोनिद लेविन ने एक ऑटोमेटन पाया, जो हालांकि हमेशा बहुमत की समस्या को सही ढंग से हल नहीं करता है, लेकिन कई मामलों में ऐसा करता है। समस्या के प्रति उनके दृष्टिकोण में,

सेलुलर ऑटोमेटन नियम की गुणवत्ता को इसके अंश द्वारा मापा जाता है $2^{i+j}$ संभावित प्रारंभिक कॉन्फ़िगरेशन जिन्हें यह सही ढंग से वर्गीकृत करता है।

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

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

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

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

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

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

वैकल्पिक समाप्ति शर्तों के साथ सटीक समाधान

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

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