ডেটা কম্প্রেশন সম্পর্কে প্যারাডক্স

ডেটা সংকোচনের সমস্যা, তার সহজতম আকারে, সংখ্যা এবং তাদের স্বরলিপির সাথে সম্পর্কিত হতে পারে। সংখ্যাগুলিকে সংখ্যা দ্বারা চিহ্নিত করা যেতে পারে ("এগারো" 11 নম্বরের জন্য), গাণিতিক রাশি ("বিশের মধ্যে দুই" 1048576 এর জন্য), স্ট্রিং এক্সপ্রেশন ("পাঁচ নয়" 99999 এর জন্য), সঠিক নাম ("জন্তুর সংখ্যা" 666 এর জন্য, "টুরিং এর মৃত্যুর বছর" 1954 এর জন্য), অথবা এর নির্বিচারে সংমিশ্রণ। যে কোনও উপাধি উপযুক্ত যার দ্বারা কথোপকথক স্পষ্টভাবে নির্ধারণ করতে পারে যে আমরা কোন সংখ্যার কথা বলছি। স্পষ্টতই, আপনার কথোপকথনকে বলুন "আটটির ফ্যাক্টরিয়াল" সমতুল্য স্বরলিপির চেয়ে বেশি দক্ষ "চল্লিশ হাজার তিনশ বিশ". একটি যৌক্তিক প্রশ্ন এখানে উঠে: একটি প্রদত্ত সংখ্যার জন্য সংক্ষিপ্ত স্বরলিপি কি?

দার্শনিক বার্ট্রান্ড রাসেল 1908 সালে প্রকাশিত "বেরির প্যারাডক্স", যা বিপরীত দিক থেকে সংখ্যার স্বরলিপির ইস্যুতে স্পর্শ করে: আশিটি বর্ণের প্রয়োজন হয় না এমন ক্ষুদ্রতম সংখ্যা কী?
এই জাতীয় সংখ্যা অবশ্যই বিদ্যমান থাকতে হবে: আশিটি রাশিয়ান অক্ষর এবং স্পেস থেকে আপনি কেবল 3480টি উপাধি তৈরি করতে পারেন, যার অর্থ আশিটি অক্ষর ব্যবহার করে আপনি 3480টির বেশি সংখ্যা নির্ধারণ করতে পারবেন না। এর মানে হল যে এইভাবে 3480 এর বেশি একটি নির্দিষ্ট সংখ্যা নির্ধারণ করা অসম্ভব।

এর মানে হল এই সংখ্যাটি উপাধির সাথে মিলে যাবে "সবচেয়ে ছোট সংখ্যা যার জন্য আশিটি অক্ষর যথেষ্ট নয়"যার মাত্র ৭৮টি অক্ষর আছে! একদিকে, এই সংখ্যাটি অবশ্যই বিদ্যমান থাকবে; অন্যদিকে, যদি এই সংখ্যাটি বিদ্যমান থাকে, তাহলে এর পদবীটি এর সাথে সঙ্গতিপূর্ণ নয়। প্যারাডক্স !

এই প্যারাডক্স খারিজ করার সবচেয়ে সহজ উপায় হল মৌখিক স্বরলিপির অনানুষ্ঠানিকতা উল্লেখ করা। যেমন, যদি স্বরলিপিতে শুধুমাত্র নির্দিষ্টভাবে সংজ্ঞায়িত অভিব্যক্তির সেট অনুমোদিত হয়, তাহলে "সবচেয়ে ছোট সংখ্যা যার জন্য আশিটি অক্ষর যথেষ্ট নয়" একটি বৈধ স্বরলিপি হবে না, যেখানে ব্যবহারিকভাবে দরকারী স্বরলিপি যেমন "আটটির ফ্যাক্টরিয়াল" গ্রহণযোগ্য থাকবে।

সংখ্যার উপর কর্মের ক্রম (অ্যালগরিদম) বর্ণনা করার আনুষ্ঠানিক উপায় আছে কি? আছে, এবং প্রচুর পরিমাণে - তাদের প্রোগ্রামিং ভাষা বলা হয়। মৌখিক নোটেশনের পরিবর্তে, আমরা প্রোগ্রামগুলি ব্যবহার করব (উদাহরণস্বরূপ, পাইথনে) যা প্রয়োজনীয় সংখ্যাগুলি প্রদর্শন করে। উদাহরণস্বরূপ, পাঁচ নাইনের জন্য প্রোগ্রামটি উপযুক্ত print("9"*5). আমরা একটি প্রদত্ত সংখ্যার জন্য সংক্ষিপ্ততম প্রোগ্রামে আগ্রহী হতে থাকব। এই ধরনের একটি প্রোগ্রামের দৈর্ঘ্য বলা হয় কোলমোগোরভ জটিলতা সংখ্যা; এটি একটি তাত্ত্বিক সীমা যেখানে একটি প্রদত্ত সংখ্যা সংকুচিত করা যেতে পারে।

বেরির প্যারাডক্সের পরিবর্তে, আমরা এখন একটি অনুরূপ বিবেচনা করতে পারি: একটি কিলোবাইট প্রোগ্রাম আউটপুট করার জন্য যথেষ্ট নয় এমন ক্ষুদ্রতম সংখ্যা কী?

আমরা আগের মতই যুক্তি করব: 2561024 কিলোবাইট টেক্সট আছে, যার মানে হল 2561024 সংখ্যার বেশি কিলোবাইট প্রোগ্রাম দ্বারা আউটপুট করা যাবে না। এর মানে হল যে একটি নির্দিষ্ট সংখ্যা 2561024 এর বেশি নয় এইভাবে প্রাপ্ত করা যাবে না।

তবে আসুন পাইথনে একটি প্রোগ্রাম লিখি যা সমস্ত সম্ভাব্য কিলোবাইট পাঠ্য তৈরি করে, সেগুলিকে কার্যকর করার জন্য চালায় এবং যদি তারা একটি সংখ্যা আউটপুট করে, তাহলে এই সংখ্যাটিকে পৌঁছানো যায় এমন অভিধানে যোগ করে। সমস্ত 2561024 সম্ভাবনাগুলি পরীক্ষা করার পরে, এটি যতই সময় নেয় না কেন, প্রোগ্রামটি অভিধান থেকে অনুপস্থিত ক্ষুদ্রতম সংখ্যাটি সন্ধান করে এবং সেই সংখ্যাটি প্রিন্ট করে৷ এটা স্পষ্ট যে এই ধরনের একটি প্রোগ্রাম কোডের একটি কিলোবাইট মধ্যে মাপসই করা হবে - এবং একটি কিলোবাইট প্রোগ্রাম দ্বারা আউটপুট করা যাবে না যে খুব সংখ্যা আউটপুট হবে!

এখন ধরা কি? এটাকে আর স্বরলিপির অনানুষ্ঠানিকতার জন্য দায়ী করা যায় না!

আপনি যদি এই বিষয়টিতে বিভ্রান্ত হন যে আমাদের প্রোগ্রামটির কাজ করার জন্য একটি জ্যোতির্বিজ্ঞানের পরিমাণ মেমরির প্রয়োজন হবে - 2561024 উপাদানগুলির একটি অভিধান (বা বিট অ্যারে) - তাহলে আপনি এটি ছাড়া একই জিনিস করতে পারেন: 2561024 নম্বরগুলির প্রতিটির জন্য, পালাক্রমে , সমস্ত 2561024 সম্ভাব্য প্রোগ্রামের মধ্য দিয়ে যান, যতক্ষণ না কোন উপযুক্ত প্রোগ্রাম নেই। এটা কোন ব্যাপার না যে এই ধরনের অনুসন্ধানটি খুব দীর্ঘ সময় ধরে চলবে: সংখ্যা এবং প্রোগ্রাম থেকে 2561024 জোড়ার কম (2) চেক করার পরে, এটি শেষ হবে এবং সেই খুব লালিত সংখ্যাটি খুঁজে পাবে।

নাকি শেষ হবে না? প্রকৃতপক্ষে, চেষ্টা করা হবে যে সব প্রোগ্রাম মধ্যে, থাকবে while True: pass (এবং এর কার্যকরী অ্যানালগগুলি) - এবং বিষয়টি এমন একটি প্রোগ্রাম পরীক্ষা করার চেয়ে আরও বেশি যাবে না!

বেরির প্যারাডক্সের বিপরীতে, যেখানে ক্যাচটি স্বরলিপির অনানুষ্ঠানিকতায় ছিল, দ্বিতীয় ক্ষেত্রে আমাদের একটি ভাল ছদ্মবেশী সংস্কার রয়েছে "সমস্যা বন্ধ করা". আসল বিষয়টি হ'ল একটি নির্দিষ্ট সময়ের মধ্যে একটি প্রোগ্রাম থেকে এর আউটপুট নির্ধারণ করা অসম্ভব। বিশেষ করে, Kolmogorov জটিলতা অসংগত: এমন কোনো অ্যালগরিদম নেই যা একটি প্রদত্ত সংখ্যার জন্য, এই সংখ্যাটি প্রিন্ট করে এমন সংক্ষিপ্ততম প্রোগ্রামের দৈর্ঘ্য খুঁজে বের করতে দেয়; যার অর্থ বেরির সমস্যার কোন সমাধান নেই - একটি প্রদত্ত সংখ্যার জন্য সংক্ষিপ্ততম মৌখিক পদবীটির দৈর্ঘ্য খুঁজে বের করা।

উত্স: www.habr.com