ڈیٹا کمپریشن کا مسئلہ، اپنی آسان ترین شکل میں، اعداد اور ان کے اشارے سے متعلق ہو سکتا ہے۔ اعداد کو ہندسوں سے ظاہر کیا جا سکتا ہے ("گیارہ" نمبر 11 کے لیے، ریاضیاتی اظہار ("بیسویں میں دو" 1048576 کے لیے، سٹرنگ ایکسپریشنز ("پانچ نو" 99999 کے لیے، مناسب نام ("جانور کی تعداد" 666 کے لیے، "ٹورنگ کی موت کا سال" 1954 کے لیے) یا اس کے صوابدیدی امتزاج۔ کوئی بھی عہدہ موزوں ہے جس کے ذریعے بات کرنے والا واضح طور پر تعین کر سکے کہ ہم کس نمبر کے بارے میں بات کر رہے ہیں۔ ظاہر ہے، اپنے بات چیت کرنے والے کو بتائیں "آٹھ کا فیکٹریل" مساوی اشارے سے زیادہ موثر "چالیس ہزار تین سو بیس". یہاں ایک منطقی سوال پیدا ہوتا ہے: دیے گئے نمبر کے لیے مختصر ترین اشارے کیا ہے؟
فلسفی برٹرینڈ رسل نے 1908 میں شائع کیا۔ ، جو مخالف سمت سے نمبر اشارے کے مسئلے کو چھوتا ہے: وہ کونسا چھوٹا عدد ہے جس کے لیے اسّی حروف کی ضرورت نہیں ہے؟
اس طرح کا نمبر ہونا ضروری ہے: اسّی روسی حروف اور خالی جگہوں سے آپ صرف 3480 عہدہ بنا سکتے ہیں، جس کا مطلب ہے کہ اسّی حروف کا استعمال کرتے ہوئے آپ 3480 سے زیادہ نمبر نہیں دے سکتے۔ اس کا مطلب یہ ہے کہ اس طرح سے کسی مخصوص نمبر کو 3480 سے زیادہ متعین کرنا ناممکن ہے۔
اس کا مطلب ہے کہ یہ نمبر عہدہ کے مطابق ہوگا۔ "سب سے چھوٹی تعداد جس کے لیے اسّی حروف کافی نہیں ہیں"جس میں صرف 78 حروف ہیں! ایک طرف، یہ نمبر موجود ہونا چاہیے؛ دوسری طرف، اگر یہ نمبر موجود ہے، تو اس کا عہدہ اس سے مطابقت نہیں رکھتا۔ پیراڈاکس!
اس تضاد کو مسترد کرنے کا سب سے آسان طریقہ یہ ہے کہ زبانی اشارے کی غیر رسمی بات کا حوالہ دیا جائے۔ جیسے، اگر اشارے میں اظہار کے صرف ایک مخصوص سیٹ کی اجازت دی گئی ہو، تو پھر "سب سے چھوٹی تعداد جس کے لیے اسّی حروف کافی نہیں ہیں" ایک درست اشارے نہیں ہوں گے، جبکہ عملی طور پر مفید اشارے جیسے "آٹھ کا فیکٹریل" قابل قبول رہے گا.
کیا اعداد پر عمل کی ترتیب (الگورتھم) کو بیان کرنے کے رسمی طریقے ہیں؟ ہیں، اور کثرت میں - انہیں پروگرامنگ زبانیں کہا جاتا ہے۔ زبانی اشارے کے بجائے، ہم ایسے پروگرام استعمال کریں گے (مثال کے طور پر، Python میں) جو مطلوبہ نمبر ظاہر کرتے ہیں۔ مثال کے طور پر، پانچ نائنز کے لیے پروگرام موزوں ہے۔ print("9"*5). ہم دیے گئے نمبر کے لیے مختصر ترین پروگرام میں دلچسپی لیتے رہیں گے۔ اس طرح کے پروگرام کی لمبائی کہا جاتا ہے نمبرز یہ وہ نظریاتی حد ہے جس میں دیے گئے نمبر کو کمپریس کیا جا سکتا ہے۔
بیری کے تضاد کے بجائے، اب ہم اسی طرح کے ایک پر غور کر سکتے ہیں: وہ سب سے چھوٹی تعداد کیا ہے جو ایک کلو بائٹ پروگرام آؤٹ پٹ کے لیے کافی نہیں ہے؟
ہم پہلے کی طرح ہی استدلال کریں گے: یہاں 2561024 کلو بائٹ ٹیکسٹس ہیں، جس کا مطلب ہے کہ کلو بائٹ پروگرام کے ذریعے 2561024 سے زیادہ نمبر نہیں نکل سکتے۔ اس کا مطلب یہ ہے کہ 2561024 سے زیادہ کوئی مخصوص نمبر اس طرح اخذ نہیں کیا جا سکتا۔
لیکن آئیے Python میں ایک ایسا پروگرام لکھتے ہیں جو تمام ممکنہ کلو بائٹ ٹیکسٹس تیار کرتا ہے، انہیں عمل درآمد کے لیے چلاتا ہے، اور اگر وہ کوئی نمبر نکالتا ہے، تو اس نمبر کو قابل رسائی کی لغت میں شامل کرتا ہے۔ تمام 2561024 امکانات کو چیک کرنے کے بعد، اس سے کوئی فرق نہیں پڑتا ہے کہ اس میں کتنا وقت لگتا ہے، پروگرام لغت میں موجود سب سے چھوٹی تعداد کو تلاش کرتا ہے اور اس نمبر کو پرنٹ کرتا ہے۔ ایسا لگتا ہے کہ ایسا پروگرام ایک کلو بائٹ کوڈ میں فٹ ہو جائے گا - اور وہ نمبر آؤٹ پٹ کرے گا جو کلو بائٹ پروگرام کے ذریعے آؤٹ پٹ نہیں ہو سکتا!
اب کیچ کیا ہے؟ اسے اب نوٹیشن کی غیر رسمی حیثیت سے منسوب نہیں کیا جاسکتا!
اگر آپ اس حقیقت سے الجھن میں ہیں کہ ہمارے پروگرام کو کام کرنے کے لیے ایک فلکیاتی مقدار کی میموری کی ضرورت ہوگی - 2561024 عناصر کی ایک لغت (یا بٹ سرنی) - تو آپ اس کے بغیر بھی ایسا ہی کرسکتے ہیں: 2561024 نمبروں میں سے ہر ایک کے لیے، بدلے میں تمام 2561024 ممکنہ پروگراموں سے گزریں، جب تک کہ کوئی مناسب نہ ہو۔ اس سے کوئی فرق نہیں پڑتا کہ اس طرح کی تلاش بہت طویل عرصے تک جاری رہے گی: نمبر اور پروگرام سے (2561024)2 جوڑوں سے کم چیک کرنے کے بعد، یہ ختم ہو جائے گا اور وہ بہت پیارا نمبر مل جائے گا۔
یا ختم نہیں ہو گا؟ درحقیقت، جتنے بھی پروگراموں کی کوشش کی جائے گی، ان میں سے ہوں گے۔ while True: pass (اور اس کے فنکشنل اینالاگ) - اور معاملہ ایسے پروگرام کی جانچ سے آگے نہیں بڑھے گا!
بیری کے تضاد کے برعکس، جہاں کیچ نوٹیشن کی غیر رسمی تھی، دوسری صورت میں ہمارے پاس ایک اچھی طرح سے بھیس بدلی ہوئی اصلاح ہے۔ . حقیقت یہ ہے کہ ایک مقررہ وقت میں کسی پروگرام سے اس کی پیداوار کا تعین کرنا ناممکن ہے۔ خاص طور پر، Kolmogorov پیچیدگی : کوئی الگورتھم نہیں ہے جو کسی دیے گئے نمبر کے لیے، اس نمبر کو پرنٹ کرنے والے مختصر ترین پروگرام کی لمبائی تلاش کرنے کی اجازت دیتا ہے۔ جس کا مطلب ہے کہ بیری کے مسئلے کا کوئی حل نہیں ہے - دیے گئے نمبر کے لیے مختصر ترین زبانی عہدہ کی لمبائی تلاش کرنا۔
ماخذ: www.habr.com