يمكن أن تتعلق مشكلة ضغط البيانات، في أبسط أشكالها، بالأرقام وترميزاتها. يمكن الإشارة إلى الأرقام بالأرقام ("أحد عشر" للرقم 11)، التعابير الرياضية ("اثنان في العشرين" لـ 1048576)، تعبيرات السلسلة ("خمس تسعات" لـ 99999)، الأسماء الصحيحة ("عدد الوحش" لـ 666، "عام وفاة تورينج" لعام 1954)، أو مجموعات عشوائية منها. أي تسمية مناسبة يمكن للمحاور من خلالها تحديد الرقم الذي نتحدث عنه بوضوح. من الواضح، أخبر محاورك "مضروب الثمانية" أكثر كفاءة من التدوين المعادل "أربعون ألفاً وثلاثمائة وعشرون". وهنا يطرح سؤال منطقي: ما هو أقصر تدوين لرقم معين؟
نشر الفيلسوف برتراند راسل عام 1908 ، والذي يتطرق إلى مسألة تدوين الأرقام من الجانب الآخر: ما هو أصغر عدد لا يحتاج إلى ثمانين حرفا؟
يجب أن يكون هذا الرقم موجودًا: من بين ثمانين حرفًا ومسافات روسية، يمكنك تكوين 3480 تعيينًا فقط، مما يعني أنه باستخدام ثمانين حرفًا، لا يمكنك تعيين أكثر من 3480 رقمًا. وهذا يعني أنه من المستحيل تعيين عدد معين لا يزيد عن 3480 بهذه الطريقة.
وهذا يعني أن هذا الرقم سوف يتوافق مع التعيين "أصغر عدد لا يكفيه ثمانين حرفاً"والتي تحتوي على 78 حرفًا فقط! فمن ناحية، يجب أن يكون هذا العدد موجودا؛ ومن ناحية أخرى، إذا كان هذا الرقم موجودا، فإن تسميته لا تتوافق معه. المفارقة!
أسهل طريقة لرفض هذه المفارقة هي الإشارة إلى الطابع غير الرسمي للرموز اللفظية. على سبيل المثال، إذا تم السماح فقط بمجموعة محددة من التعبيرات في التدوين، إذن "أصغر عدد لا يكفيه ثمانين حرفاً" لن يكون تدوينًا صالحًا، في حين أن التدوينات المفيدة عمليًا مثل "مضروب الثمانية" سيبقى مقبولا.
هل هناك طرق رسمية لوصف تسلسل (خوارزمية) الإجراءات على الأرقام؟ هناك، وبوفرة، ما يسمى لغات البرمجة. بدلا من الرموز اللفظية، سوف نستخدم البرامج (على سبيل المثال، في بايثون) التي تعرض الأرقام المطلوبة. على سبيل المثال، لمدة خمس تسعات البرنامج مناسب print("9"*5). سنستمر في الاهتمام بأقصر برنامج لرقم معين. ويسمى طول مثل هذا البرنامج أعداد؛ إنه الحد النظري الذي يمكن ضغط رقم معين إليه.
بدلاً من مفارقة بيري، يمكننا الآن أن نفكر في مفارقة مماثلة: ما هو أصغر رقم لا يكفي برنامج الكيلوبايت لإخراجه؟
سنفكر بنفس الطريقة السابقة: هناك 2561024 نصًا بالكيلو بايت، مما يعني أنه لا يمكن إخراج أكثر من 2561024 رقمًا بواسطة برامج الكيلوبايت. وهذا يعني أنه لا يمكن اشتقاق رقم معين لا يزيد عن 2561024 بهذه الطريقة.
لكن دعونا نكتب برنامجًا بلغة بايثون يقوم بإنشاء جميع النصوص الممكنة بالكيلوبايت، وتشغيلها للتنفيذ، وإذا قاموا بإخراج رقم، فإنه يضيف هذا الرقم إلى قاموس النصوص التي يمكن الوصول إليها. بعد التحقق من جميع الاحتمالات البالغ عددها 2561024، مهما طال الزمن، يبحث البرنامج عن أصغر رقم مفقود من القاموس ويطبع هذا الرقم. يبدو من الواضح أن مثل هذا البرنامج سوف يتناسب مع كيلو بايت من التعليمات البرمجية - وسيخرج نفس الرقم الذي لا يمكن إخراجه بواسطة برنامج كيلو بايت!
ما الفائدة الآن؟ لم يعد من الممكن أن يعزى إلى الطابع غير الرسمي للتدوين!
إذا كنت مرتبكًا من حقيقة أن برنامجنا سيتطلب قدرًا فلكيًا من الذاكرة للعمل - قاموس (أو مصفوفة بت) مكون من 2561024 عنصرًا - فيمكنك فعل الشيء نفسه بدونه: لكل رقم من الأرقام 2561024، بدوره ، قم بمراجعة جميع البرامج الممكنة 2561024، حتى لا يكون هناك برنامج مناسب. لا يهم أن مثل هذا البحث سيستمر لفترة طويلة جدًا: بعد التحقق من أقل من (2561024) زوجًا من الرقم والبرنامج، سينتهي البحث ويجد هذا الرقم العزيز جدًا.
أم أنها لن تنتهي؟ في الواقع، من بين جميع البرامج التي سيتم تجربتها، سيكون هناك while True: pass (ونظائرها الوظيفية) - والأمر لن يتعدى اختبار مثل هذا البرنامج!
على عكس مفارقة بيري، حيث كان المصيد هو عدم رسمية الترميز، في الحالة الثانية لدينا إعادة صياغة مقنعة بشكل جيد . الحقيقة هي أنه من المستحيل تحديد مخرجاته من البرنامج في وقت محدد. على وجه الخصوص، تعقيد كولموغوروف : لا توجد خوارزمية تسمح، لرقم معين، بالعثور على طول أقصر برنامج يطبع هذا الرقم؛ مما يعني أنه لا يوجد حل لمشكلة بيري - لإيجاد طول أقصر تسمية لفظية لرقم معين.
المصدر: www.habr.com