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

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

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

समस्या कथन

कुल मिलाकर यदि इस बात पर ध्यान केंद्रित करे तो हम पायेंगे कि 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) पर स्विच करता है, जो प्रत्येक कोशिका को स्वयं और उसके समीपस्थ बहुसंख्यक पर इसे स्थित कर सकता है, इस प्रकार बहुसंख्यक मान को हल करता है या तो सभी शून्यों या अंतिम स्थिति में सभी शून्यों की मानक मान्यता मानदंड के साथ समस्या को हल करता हैं। चूंकि, यह मशीन स्वयं सेलुलर ऑटोमेटन नहीं है। इसके अतिरिक्त, यह दिखाया गया है कि फुकस का समग्र नियम ध्वनि के प्रति बहुत संवेदनशील है, और ध्वनि के किसी भी स्तर पर उदाहरण के लिए, पर्यावरण से या गतिशील गलतियों के लिए अपूर्ण वर्गीकरणकर्ता, ध्वनि गैक्स-कुर्द्युमोव-लेविन ऑटोमेटन से उत्तम प्रदर्शन नहीं कर सकता है।