Majority problem
اکثریتی مسئلہ، یا کثافت کی درجہ بندی کا کام، ایک جہتی سیلولر آٹومیٹن قوانین کو تلاش کرنے کا مسئلہ ہے جو اکثریت ووٹنگ کو درست طریقے سے انجام دیتے ہیں۔ مقامی منتقلی کے اصولوں کا استعمال کرتے ہوئے خلیات نظام میں موجود تمام خلیات کی کل گنتی نہیں جان سکتے۔ ایک کی تعداد کو شمار کرنے کے لیے (یا، ہم آہنگی کے لحاظ سے، صفر کی تعداد)، نظام کو نظام کے کل سائز میں بٹس کے لوگرتھمک نمبر کی ضرورت ہوتی ہے۔ اس کے لیے نظام کو نظام کے سائز میں لکیری فاصلے پر پیغامات بھیجنے اور نظام کے لیے غیر باقاعدہ زبان کو پہچاننے کی بھی ضرورت ہوتی ہے۔ اس طرح، یہ مسئلہ سیلولر آٹومیٹن سسٹمز کی کمپیوٹیشنل طاقت کی پیمائش میں ایک اہم ٹیسٹ کیس ہے۔ دشواری کا بیان کل i + j خلیوں کے ساتھ دو ریاستی سیلولر آٹومیٹن کی ترتیب کو دیکھتے ہوئے، جن میں سے i صفر حالت میں ہے اور j ایک ریاست میں ہے، ووٹنگ کے مسئلے کا درست حل بالآخر تمام خلیوں کو صفر پر سیٹ کرنا چاہیے اگر i> j اور آخر کار تمام خلیوں کو ایک پر سیٹ کرنا چاہیے اگر i <j۔ مطلوبہ حتمی حالت غیر متعین ہے اگر i = j۔ اس مسئلے کو یہ جانچنے کے لیے بھی عام کیا جا سکتا ہے کہ آیا صفر اور ایک کا تناسب 50 فیصد کے علاوہ کسی حد سے اوپر یا نیچے ہے۔ اس عمومی شکل میں، کسی کو ایک حد بھی دی جاتی ہے ؛ ووٹنگ کے مسئلے کا ایک درست حل بالآخر تمام خلیوں کو صفر پر سیٹ کرنا چاہیے اگر اور آخر کار تمام خلیوں کو ایک پر سیٹ کرنا چاہیے اگر۔ مطلوبہ حتمی حالت غیر متعین ہے اگر۔ گیکس، کرڈیوموف اور لیون نے ایک ایسا آٹومیٹن پایا جو اگرچہ ہمیشہ اکثریت کے مسئلے کو صحیح طریقے سے حل نہیں کرتا ہے، لیکن بہت سے معاملات میں ایسا کرتا ہے۔ مسئلے کے بارے میں ان کے نقطہ نظر میں، سیلولر آٹومیٹن اصول کے معیار کو ممکنہ ابتدائی ترتیبات کے اس حصے سے ماپا جاتا ہے جس کی یہ صحیح درجہ بندی کرتا ہے۔ گیکس، کرڈیوموف اور لیون کی طرف سے تجویز کردہ قاعدہ ہر خلیے کی حالت کو درج ذیل ترتیب دیتا ہے۔ اگر کوئی خلیہ 0 ہے، تو اس کی اگلی حالت خود کی اقدار میں اکثریت کے طور پر بنتی ہے، اس کا فوری پڑوسی بائیں طرف، اور اس کا پڑوسی بائیں طرف تین خالی جگہوں پر ہوتا ہے۔ اگر، دوسری طرف، ایک خلیہ 1 ہے، تو اس کی اگلی حالت ہم آہنگی سے بنتی ہے، جیسا کہ خود کی اقدار میں اکثریت، دائیں طرف اس کا فوری پڑوسی، اور دائیں طرف اس کے پڑوسی کے لیے تین خالی جگہیں۔ تصادفی طور پر پیدا شدہ مثالوں میں، یہ اکثریت کا صحیح تعین کرنے میں تقریبا 78 فیصد درستگی حاصل کرتا ہے۔ داس، مچل اور کرچ فیلڈ نے دکھایا کہ جینیاتی الگورتھم کا استعمال کرتے ہوئے بہتر قوانین تیار کرنا ممکن ہے۔ ایک کامل درجہ بندی کی ناممکنیت 1995 میں، لینڈ اور بیلیو نے ظاہر کیا کہ رداس r اور کثافت ρ کے ساتھ کوئی بھی دو ریاستی قاعدہ تمام ابتدائی ترتیبات پر ووٹنگ کے مسئلے کو صحیح طریقے سے حل نہیں کرتا ہے جب خلیوں کی تعداد کافی زیادہ ہو (تقریبا 4r/ρ سے بڑی)۔ ان کی دلیل سے پتہ چلتا ہے کہ چونکہ نظام متعین ہے، اس لیے ہر خلیے کو مکمل طور پر صفر یا ایک سے گھرا ہوا ہونا چاہیے پھر صفر بن جانا چاہیے۔ اسی طرح، کوئی بھی کامل قاعدہ کسی کے تناسب کو کبھی بھی اوپر نہیں لے جا سکتا اگر یہ نیچے تھا (یا اس کے برعکس)۔ اس کے بعد وہ ظاہر کرتے ہیں کہ کوئی بھی فرض شدہ کامل قاعدہ یا تو ایک الگ تھلگ اصول کا سبب بنے گا جس نے تناسب کو ختم کر دیا ہے اسے منسوخ کر دیا جائے گا یا، اگر ان کا تناسب اس سے کم ہے تو، ایک الگ تھلگ اصول جعلی قوانین کو صفر کے ایک بلاک میں داخل کرنے کا سبب بنے گا جس کی وجہ سے ان کا تناسب ان سے زیادہ ہو جائے گا۔ 2013 میں، بسک، فیٹس، مارکوویسی اور مائریس نے ایک کامل کثافت کی درجہ بندی کرنے کے ناممکن ہونے کا ایک آسان ثبوت دیا، جو تعیناتی اور اسٹاکسٹک سیلولر اور کسی بھی جہت دونوں کے لیے ہے۔ متبادل اختتامی شرائط کے ساتھ درست حل جیسا کہ کیپ کیریری، سیپر اور ٹامسینی نے مشاہدہ کیا ہے، اکثریت کا مسئلہ بالکل ٹھیک حل ہو سکتا ہے اگر کوئی اس تعریف میں نرمی کرے جس کے ذریعے کہا جاتا ہے کہ آٹومیٹن نے اکثریت کو تسلیم کیا ہے۔ خاص طور پر، قاعدہ 184 آٹومیٹن کے لیے، جب چکور حد کے حالات کے ساتھ ایک محدود کائنات پر چلتا ہے، تو ہر خلیہ لامحدود طور پر اکثر مسلسل دو مراحل کے لیے اکثریتی حالت میں رہے گا جبکہ صرف محدود طور پر کئی بار مسلسل دو مراحل کے لیے اقلیتی حالت میں رہے گا۔ متبادل طور پر، ایک ہائبرڈ آٹومیٹن جو صف کے سائز میں کئی مراحل کے لیے قاعدہ 184 چلاتا ہے، اور پھر اکثریت کے اصول (قاعدہ 232) کی طرف جاتا ہے، جو ہر خلیے کو اپنے اور اپنے پڑوسیوں کی اکثریت کے لیے ترتیب دیتا ہے، اکثریت کے مسئلے کو تمام صفر یا حتمی حالت میں موجود تمام افراد کی معیاری شناخت کے معیار کے ساتھ حل کرتا ہے۔ تاہم، یہ مشین خود سیلولر آٹومیٹن نہیں ہے۔ مزید برآں، یہ دکھایا گیا ہے کہ فوکش کا جامع قاعدہ شور کے لیے بہت حساس ہے اور شور کی کسی بھی سطح کے لیے (مثال کے طور پر ماحول سے یا متحرک غلطیوں سے) ایک نامکمل درجہ بندی کرنے والے شور والے گیکس-کرڈیوموف-لیون آٹومیٹن کو پیچھے نہیں چھوڑ سکتا۔ حوالہ جات سیلولر آٹومیٹا