يمكن أن تتعلق مهمة ضغط البيانات بأبسط أشكالها بالأرقام وترميزها. يمكن الإشارة إلى الأرقام بالأرقام (
"11" للرقم 11) ، التعبيرات الرياضية (
"اثنان في العشرين" لعام 1048576) ، تعبيرات السلسلة (
"خمسة تسع" لعام 99999) ، الأسماء الصحيحة (
"رقم الوحش" لعام 666 ،
"سنة وفاة تورينج" " لعام 1954) ، أو مجموعاتهم التعسفية. أي تسمية يمكن للمحاور من خلالها تحديد نوع الكلام المناسب بشكل لا لبس فيه مناسب. من الواضح أن إبلاغ المحاور بـ
" العامل
الثامن" هو أكثر فاعلية من التعيين المكافئ
"أربعون ألف وثلاثمائة وعشرون" . هذا يثير السؤال المنطقي: ما هو أقصر تعيين لعدد معين؟
نشر الفيلسوف برتراند راسل في عام 1908
"Berry Paradox" ، الذي يعالج مسألة تدوين الأرقام على الجانب الآخر:
ما هو أصغر رقم للإشارة إلى ثمانين حرفًا لا تكفي؟يجب أن يوجد مثل هذا الرقم: من بين ثمانين حرفًا ومسافة روسية ، يمكنك إنشاء ما مجموعه 34
80 تعيينًا ، مما يعني أنه باستخدام ثمانين حرفًا لا يمكنك تعيين أكثر من 34
80 رقمًا. لذلك ، لا يمكن تعيين عدد معين ، لا يزيد عن 34
80 ، بهذه الطريقة.
هذا يعني أن التسمية
"أصغر رقم لا تكفيه 80 حرفًا" سوف تتوافق مع هذا الرقم ، حيث لا يوجد سوى 78 حرفًا! من ناحية ، يجب أن يوجد هذا الرقم ؛ من ناحية أخرى ، إذا كان هذا الرقم موجودًا ، فإن تعيينه لا يتوافق معه. المفارقة!
أسهل طريقة لرفض هذه المفارقة هي الإشارة إلى عدم صحة التعيينات الكلامية. على سبيل المثال ، إذا تم السماح فقط لمجموعة معينة من التعبيرات في الترميز ، فلن يكون
"الرقم الأصغر الذي لا
يكفي فيه ثمانون حرفًا" تسمية صالحة ، بينما تظل التعيينات المفيدة عمليًا من نوع
"الفصائل الثمانية" سارية.
هل هناك طرق رسمية لوصف تسلسل (خوارزمية) الإجراءات على الأرقام؟ هناك ، وبوفرة - يطلق عليهم لغات البرمجة. بدلاً من التدوين اللفظي ، سنستخدم البرامج (على سبيل المثال ، في بيثون) التي تطبع الأرقام اللازمة. على سبيل المثال ، لمدة خمسة تسعة ، برنامج
print("9"*5) مناسب. سنظل مهتمين بأقصر برنامج لعدد معين. ويطلق على طول هذا البرنامج
تعقيد Kolmogorov العدد. هذا هو الحد النظري الذي يمكن ضغط عدد معين عليه.
بدلاً من مفارقة بيري ، يمكن للمرء الآن التفكير في واحدة مماثلة:
ما هو أصغر عدد لا يكفيه برنامج كيلوبايت؟سنناقش بنفس الطريقة كما كان من قبل: هناك
256،1024 نصوص كيلوبايت ، مما يعني أنه لا يمكن عرض أكثر من
256،224 رقمًا في برامج الكيلوبايت. هذا يعني أنه لا يمكن استنتاج عدد معين ، لا يزيد عن 256
1024 ، بهذه الطريقة.
لكننا نكتب في Python برنامجًا يولد جميع النصوص الممكنة للكيلوبايت ، ويطلقها للتنفيذ ، وإذا قاموا بطباعة رقم معين ، فإنه يضيف هذا الرقم إلى القاموس القابل للتحقيق. بعد التحقق من جميع الاحتمالات 256
1024 ، بغض النظر عن المدة التي يستغرقها - يبحث البرنامج عن أصغر عدد غير موجود في القاموس ويعرض هذا الرقم. يبدو من الواضح أن مثل هذا البرنامج سوف يتلاءم مع كيلوبايت من التعليمات البرمجية - وسيخرج العدد ذاته الذي لا يمكن عرضه في برنامج كيلوبايت!
ما هي الفائدة الآن؟ لم يعد من الممكن أن يعزى إلى الطابع غير الرسمي للتدوين!
إذا كنت مرتبكًا من أن برنامجنا سيتطلب قدرًا هائلاً من الذاكرة الفلكية - معجمًا (أو صورة نقطية) يتكون من 256 عنصرًا - يمكنك حينئذٍ فعل نفس الشيء بدونه: لكل 256 رقمًا من الأرقام
1024 ، يمكن تكرارها عبر كل
1024 256 البرامج حتى يتم العثور على واحد مناسب. لا يهم أن يستمر هذا التعداد لفترة طويلة جدًا: بعد التحقق من أقل من (256
1024 )
2 زوجًا من الرقم والبرنامج ، سينتهي ، وسيجد هذا العدد العزيزة للغاية.
أم أنها لن تنتهي؟ في الواقع ، من بين جميع البرامج التي ستتم تجربتها ، سيكون هناك
while True: pass (ونظرائه الوظيفية) - ولن تتجاوز الأشياء التحقق من مثل هذا البرنامج!
على عكس مفارقة بيري ، حيث كان المصيد في الطابع غير الرسمي للتدوين ، في الحالة الثانية لدينا إعادة صياغة متخفية بشكل جيد لـ
"مشكلة التوقف" . الحقيقة هي أنه وفقًا للبرنامج ، من المستحيل تحديد استنتاجه في وقت محدد. على وجه الخصوص ، تعقيد Kolmogorov غير
قابل للحساب : لا توجد خوارزمية من شأنها أن تسمح لعدد معين للعثور على طول أقصر برنامج يخرج هذا الرقم ؛ مما يعني أنه لا يوجد حل لمشكلة بيري - لإيجاد لعدد معين طول أقصر كلمة التعيين.