Majority problem
बहुमत समस्या, या घनत्व वर्गीकरण कार्य, एक आयामी सेलुलर स्वचालित नियमों को खोजने की समस्या है जो बहुमत मतदान को सटीक रूप से करते हैं। स्थानीय संक्रमण नियमों का उपयोग करके, कोशिकाएं प्रणाली में सभी की कुल गिनती नहीं जान सकती हैं। एक की संख्या (या, समरूपता द्वारा, शून्यों की संख्या) की गणना करने के लिए, प्रणाली को प्रणाली के कुल आकार में बिट्स की एक लघुगणक संख्या की आवश्यकता होती है। इसके लिए प्रणाली को प्रणाली के आकार में एक दूरी पर रैखिक संदेश भेजने और प्रणाली को एक गैर-नियमित भाषा को पहचानने की भी आवश्यकता होती है। इस प्रकार, यह समस्या सेलुलर ऑटोमेटन प्रणालियों की कम्प्यूटेशनल शक्ति को मापने में एक महत्वपूर्ण परीक्षण मामला है। समस्या कथन कुल आई + जे कोशिकाओं के साथ दो-अवस्था सेलुलर ऑटोमेटन के विन्यास को देखते हुए, जिनमें से आई शून्य अवस्था में हैं और जे एक अवस्था में हैं, मतदान समस्या का एक सही समाधान अंततः सभी कोशिकाओं को शून्य पर सेट करना चाहिए यदि आई> जे और अंततः सभी कोशिकाओं को एक पर सेट करना चाहिए यदि आई <जे। वांछित अंतिम अवस्था अनिर्दिष्ट है यदि i = j। इस समस्या को यह परीक्षण करने के लिए भी सामान्यीकृत किया जा सकता है कि क्या शून्य और शून्य का अनुपात 50 प्रतिशत के अलावा किसी सीमा से ऊपर या नीचे है। इस सामान्यीकरण में, किसी को एक सीमा भी दी जाती है; मतदान की समस्या का एक सही समाधान अंततः सभी कक्षों को शून्य पर सेट करना चाहिए और अंततः सभी कक्षों को एक पर सेट करना चाहिए। वांछित अंतिम स्थिति अनिर्दिष्ट है यदि। गैक्स, कुर्द्युमोव और लेविन ने एक स्वचालित समाधान पाया जो, हालांकि यह हमेशा बहुमत की समस्या को सही ढंग से हल नहीं करता है, लेकिन कई मामलों में ऐसा करता है। समस्या के प्रति उनके दृष्टिकोण में, एक सेलुलर ऑटोमेटन नियम की गुणवत्ता को संभावित प्रारंभिक विन्यास के अंश से मापा जाता है जिसे यह सही ढंग से वर्गीकृत करता है। गैक्स, कुर्द्युमोव और लेविन द्वारा प्रस्तावित नियम प्रत्येक कोशिका की स्थिति को निम्नानुसार निर्धारित करता है। यदि एक कोशिका 0 है, तो इसकी अगली अवस्था स्वयं के मूल्यों के बीच बहुमत के रूप में बनती है, बाईं ओर इसका निकटतम पड़ोसी और बाईं ओर इसके पड़ोसी तीन रिक्त स्थान होते हैं। यदि, दूसरी ओर, एक कोशिका 1 है, तो इसकी अगली स्थिति सममित रूप से बनती है, अपने मूल्यों के बीच बहुमत के रूप में, इसका निकटतम पड़ोसी दाईं ओर, और इसका पड़ोसी दाईं ओर तीन रिक्त स्थान है। यादृच्छिक रूप से उत्पन्न उदाहरणों में, यह बहुमत का सही निर्धारण करने में लगभग 78 प्रतिशत सटीकता प्राप्त करता है। दास, मिशेल और क्रचफील्ड ने दिखाया कि आनुवंशिक एल्गोरिदम का उपयोग करके बेहतर नियम विकसित करना संभव है। एक पूर्ण वर्गीकरण की असंभवता 1995 में, लैंड और बेलेव ने दिखाया कि त्रिज्या r और घनत्व ρ के साथ कोई भी दो-अवस्था नियम सभी प्रारंभिक विन्यासों पर मतदान की समस्या को सही ढंग से हल नहीं करता है जब कोशिकाओं की संख्या पर्याप्त रूप से बड़ी होती है (लगभग 4r/ρ से बड़ी)। उनके तर्क से पता चलता है कि चूंकि प्रणाली नियतात्मक है, इसलिए पूरी तरह से शून्य या शून्य से घिरी प्रत्येक कोशिका को शून्य होना चाहिए। इसी तरह, कोई भी पूर्ण नियम कभी भी एक के अनुपात को ऊपर नहीं ले जा सकता है यदि यह नीचे था (या इसके विपरीत)। वे तब दिखाते हैं कि कोई भी अनुमानित पूर्ण नियम या तो एक पृथक नियम का कारण बनेगा जिसने अनुपात को रद्द करने के लिए धक्का दिया या, यदि एक का अनुपात शून्य से कम है, तो एक पृथक नियम शून्य के एक खंड में नकली नियमों को शामिल करने का कारण बनेगा जिससे एक का अनुपात शून्य से अधिक हो जाएगा। 2013 में, बुसिक, फैटेस, मार्कोविची और मैरेस ने एक पूर्ण घनत्व वर्गीकरण की असंभवता का एक सरल प्रमाण दिया, जो नियतात्मक और यादृच्छिक सेलुलर और किसी भी आयाम दोनों के लिए है। वैकल्पिक समाप्ति स्थितियों के साथ सटीक समाधान जैसा कि कैपकेरेरे, सिपर और टोमासिनी द्वारा देखा गया है, बहुमत की समस्या को पूरी तरह से हल किया जा सकता है यदि कोई उस परिभाषा को शिथिल करता है जिसके द्वारा कहा जाता है कि ऑटोमेटन ने बहुमत को मान्यता दी है। विशेष रूप से, नियम 184 ऑटोमेटन के लिए, जब चक्रीय सीमा स्थितियों के साथ एक परिमित ब्रह्मांड पर चलाया जाता है, तो प्रत्येक कोशिका अनंत रूप से अक्सर लगातार दो चरणों के लिए बहुसंख्यक अवस्था में रहेगी, जबकि केवल सीमित रूप से कई बार लगातार दो चरणों के लिए अल्पसंख्यक अवस्था में होगी। वैकल्पिक रूप से, एक संकर स्वचालित यंत्र जो सरणी के आकार में रैखिक कई चरणों के लिए नियम 184 चलाता है, और फिर बहुमत नियम (नियम 232) पर स्विच करता है, जो प्रत्येक कोशिका को अपने और अपने पड़ोसियों के बहुमत के लिए सेट करता है, सभी शून्यों या अंतिम अवस्था में सभी की मानक मान्यता मानदंड के साथ बहुमत समस्या का समाधान करता है। हालाँकि, यह मशीन अपने आप में एक सेलुलर ऑटोमेटन नहीं है। इसके अलावा, यह दिखाया गया है कि फुक का समग्र नियम शोर के प्रति बहुत संवेदनशील है और शोर के किसी भी स्तर (जैसे, पर्यावरण से या गतिशील गलतियों से) के लिए एक अपूर्ण वर्गीकरण, शोर गैक्स-कुर्द्युमोव-लेविन ऑटोमेटन से बेहतर प्रदर्शन नहीं कर सकता है। संदर्भ सेलुलर ऑटोमेटा