Majority problem
সংখ্যাগরিষ্ঠ সমস্যা, বা ঘনত্ব শ্রেণিবিন্যাসের কাজ হল এক-মাত্রিক সেলুলার অটোমেটন নিয়ম খুঁজে বের করার সমস্যা যা সঠিকভাবে সংখ্যাগরিষ্ঠ ভোটদান সম্পাদন করে। স্থানীয় রূপান্তর নিয়ম ব্যবহার করে, কোষগুলি সিস্টেমে থাকা সমস্ত কোষের মোট গণনা জানতে পারে না। একটির সংখ্যা গণনা করার জন্য (বা, প্রতিসাম্য দ্বারা, শূন্যের সংখ্যা), সিস্টেমের মোট আকারে বিটের একটি লগারিদমিক সংখ্যা প্রয়োজন। এর জন্য সিস্টেমের আকারের রৈখিক দূরত্বে এবং সিস্টেমের জন্য একটি অ-নিয়মিত ভাষা সনাক্ত করার জন্য বার্তা পাঠানোর প্রয়োজন হয়। সুতরাং, সেলুলার অটোমেটন সিস্টেমের গণনামূলক শক্তি পরিমাপের ক্ষেত্রে এই সমস্যাটি একটি গুরুত্বপূর্ণ পরীক্ষা। সমস্যা বিবৃতি মোট আই + জে কোষ সহ একটি দ্বি-অবস্থা সেলুলার অটোম্যাটনের বিন্যাস দেওয়া হয়েছে, যার মধ্যে আই শূন্য অবস্থায় রয়েছে এবং জে এক অবস্থায় রয়েছে, ভোটদান সমস্যার একটি সঠিক সমাধান অবশ্যই শেষ পর্যন্ত সমস্ত কোষকে শূন্যে সেট করতে হবে যদি আই> জে হয় এবং শেষ পর্যন্ত সমস্ত কোষকে একটিতে সেট করতে হবে যদি আই <জে হয়। কাঙ্ক্ষিত চূড়ান্ত অবস্থা অনির্দিষ্ট হয় যদি i = j হয়। শূন্য এবং একের অনুপাত 50 শতাংশের বাইরে কোনও সীমার উপরে বা নীচে কিনা তা পরীক্ষা করার জন্যও সমস্যাটিকে সাধারণীকরণ করা যেতে পারে। এই সাধারণীকরণে, একজনকে একটি সীমাও দেওয়া হয়; ভোটদান সমস্যার একটি সঠিক সমাধান অবশ্যই শেষ পর্যন্ত সমস্ত কোষকে শূন্যে সেট করতে হবে যদি এবং শেষ পর্যন্ত সমস্ত কোষকে একটিতে সেট করতে হবে যদি। কাঙ্ক্ষিত চূড়ান্ত অবস্থা অনির্দিষ্ট যদি। আনুমানিক সমাধান গ্যাক্স, কুর্দিউমভ এবং লেভিন একটি অটোমেটন খুঁজে পেয়েছেন যা, যদিও এটি সর্বদা সংখ্যাগরিষ্ঠ সমস্যার সঠিক সমাধান করে না, তবে অনেক ক্ষেত্রেই তা করে। সমস্যার প্রতি তাদের দৃষ্টিভঙ্গিতে, একটি সেলুলার অটোমেটন নিয়মের গুণমান সম্ভাব্য প্রারম্ভিক কনফিগারেশনের ভগ্নাংশ দ্বারা পরিমাপ করা হয় যা এটি সঠিকভাবে শ্রেণীবদ্ধ করে। গ্যাক্স, কুর্দিউমভ এবং লেভিন দ্বারা প্রস্তাবিত নিয়মটি প্রতিটি কোষের অবস্থা নিম্নরূপ নির্ধারণ করে। যদি একটি কোষ 0 হয়, তবে তার পরবর্তী অবস্থাটি তার মানগুলির মধ্যে সংখ্যাগরিষ্ঠ হিসাবে গঠিত হয়, বাম দিকে তার নিকটতম প্রতিবেশী এবং বাম দিকে তার প্রতিবেশী তিনটি স্থান। অন্যদিকে, যদি একটি কোষ 1 হয়, তবে তার পরবর্তী অবস্থা প্রতিসমভাবে গঠিত হয়, যেমন তার মানগুলির মধ্যে সংখ্যাগরিষ্ঠতা, ডানদিকে তার নিকটবর্তী প্রতিবেশী এবং ডানদিকে তার প্রতিবেশী তিনটি স্থান। এলোমেলোভাবে সৃষ্ট দৃষ্টান্তগুলিতে, এটি সঠিকভাবে সংখ্যাগরিষ্ঠতা নির্ধারণে প্রায় 78 শতাংশ নির্ভুলতা অর্জন করে। দাস, মিচেল এবং ক্রাচফিল্ড দেখিয়েছেন যে জেনেটিক অ্যালগরিদম ব্যবহার করে আরও ভাল নিয়ম তৈরি করা সম্ভব। একটি নিখুঁত শ্রেণিবিন্যাসের অসম্ভবতা 1995 সালে, ল্যান্ড এবং বেলু দেখিয়েছিলেন যে ব্যাসার্ধ r এবং ঘনত্ব ρ সহ কোনও দ্বি-অবস্থার নিয়ম সঠিকভাবে সমস্ত প্রারম্ভিক কনফিগারেশনে ভোটদানের সমস্যা সমাধান করে না যখন কোষের সংখ্যা যথেষ্ট বড় (প্রায় 4r/ρ এর চেয়ে বড়)। তাদের যুক্তি দেখায় যে যেহেতু সিস্টেমটি নির্ধারক, তাই সম্পূর্ণরূপে শূন্য বা এক দ্বারা বেষ্টিত প্রতিটি কোষকে অবশ্যই শূন্য হতে হবে। একইভাবে, যে কোনও নিখুঁত নিয়ম কখনই একের অনুপাতকে উপরে নিয়ে যেতে পারে না যদি এটি নিচে থাকে (বা তদ্বিপরীত)। তারা তখন দেখায় যে যে কোনও অনুমিত নিখুঁত নিয়ম হয় একটি বিচ্ছিন্ন নিয়মের কারণ হবে যা অনুপাতকে বাতিল করে দেবে অথবা, যদি একটির অনুপাত এর চেয়ে কম হয়, তবে একটি বিচ্ছিন্ন নিয়ম জাল নিয়মকে শূন্যের একটি ব্লকে প্রবর্তন করবে যার ফলে একটির অনুপাত তার চেয়ে বেশি হয়ে যাবে। 2013 সালে, বুসিক, ফাতেস, মার্কোভিচি এবং মাইরেস একটি নিখুঁত ঘনত্বের শ্রেণিবিন্যাসের অসম্ভবতার একটি সহজ প্রমাণ দিয়েছিলেন, যা নির্ধারণমূলক এবং স্টোকাস্টিক সেলুলার এবং যে কোনও মাত্রার জন্য ধারণ করে। বিকল্প সমাপ্তি শর্তগুলির সাথে সঠিক সমাধান ক্যাপকারেরে, সিপার এবং টোমাসিনি দ্বারা পর্যবেক্ষণ করা হয়েছে, সংখ্যাগরিষ্ঠ সমস্যাটি নিখুঁতভাবে সমাধান করা যেতে পারে যদি কেউ সেই সংজ্ঞাটিকে শিথিল করে যার দ্বারা অটোমেটন সংখ্যাগরিষ্ঠকে স্বীকৃতি দিয়েছে বলে বলা হয়। বিশেষত, নিয়ম 184 অটোমেটন-এর জন্য, যখন চক্রাকার সীমানা শর্ত সহ একটি সীমাবদ্ধ মহাবিশ্বে চালানো হয়, তখন প্রতিটি কোষ অসীমভাবে প্রায়শই পরপর দুটি ধাপের জন্য সংখ্যাগরিষ্ঠ অবস্থায় থাকবে এবং কেবলমাত্র সীমিতভাবে বহুবার পরপর দুটি ধাপের জন্য সংখ্যালঘু অবস্থায় থাকবে। বিকল্পভাবে, একটি হাইব্রিড অটোমেটন যা অ্যারের আকারে রৈখিকভাবে বেশ কয়েকটি ধাপের জন্য নিয়ম 184 চালায় এবং তারপরে সংখ্যাগরিষ্ঠ নিয়মে (নিয়ম 232) স্যুইচ করে, যা প্রতিটি কোষকে নিজের এবং তার প্রতিবেশীদের সংখ্যাগরিষ্ঠের সাথে সেট করে, সমস্ত শূন্য বা চূড়ান্ত অবস্থার সমস্তটির মানক স্বীকৃতির মানদণ্ডের সাথে সংখ্যাগরিষ্ঠ সমস্যার সমাধান করে। তবে, এই যন্ত্রটি নিজেই একটি সেলুলার অটোমেটন নয়। উপরন্তু, এটি দেখানো হয়েছে যে ফুকসের যৌগিক নিয়ম শব্দের প্রতি খুব সংবেদনশীল এবং যে কোনও স্তরের শব্দের জন্য (যেমন, পরিবেশ থেকে বা গতিশীল ভুল থেকে) একটি অসম্পূর্ণ শ্রেণীবিভাগ, গোলমাল গ্যাক্স-কুর্দিউমভ-লেভিন অটোমেটনকে ছাড়িয়ে যেতে পারে না। তথ্যসূত্র সেলুলার অটোমাটা