اكتشاف قوة نظرية المعلومات الخوارزمية

نظرية المعلومات الخوارزمية (بالإنجليزية: Algorithmic information theory) (AIT) هي فرع من علوم الكمبيوتر النظرية التي تهتم بالعلاقة بين الحساب والمعلومات الخاصة بالأشياء المولدة حسابيًا على عكس الأشياء المولدة تصادفيا، مثل السلاسل أو أي من هياكل البيانات أخرى. بعبارة أخرى، تبين هذه نظرية المعلومات الخوارزمية أن عدم قابلية الضغط الحسابي "تحاكي" (باستثناء الثابت الذي يعتمد فقط على لغة البرمجة العالمية المختارة) العلاقات أو التفاوتات الموجودة في نظرية المعلومات. نتيجة لذلك، ووفقًا لغريجوري تشايتين، هذا الشيء يعني: «وضع نظرية المعلومات الخاصة بشانون ونظرية الحوسبة الخاصة بتورينج في هزاز الكوكتيل ورجّها بقوة».

بالإضافة إلى صياغة مقياس عالمي لمحتوى المعلومات غير القابل للاختزال للأشياء المولدة حاسوبيًا، كانت بعض الإنجازات الرئيسية لـهذه النظرية هي إظهار أن: التعقيد الخوارزمي في الواقع يتبع (في الحالة المحددة ذاتيًا) نفس التفاوتات (باستثناء الثابت) التي تتبعها الإنتروبية، كما هو الحال في نظرية المعلومات الكلاسيكية؛ العشوائية هي عدم القابلية للضغط؛ وفي نطاق البرامج المولدة عشوائيًا، فإن احتمال حدوث أي بنية بيانات هو من رتبة أقصر برنامج يولدها عند تشغيله على جهاز عالمي.

تدرس AIT بشكل أساسي مقاييس محتوى المعلومات غير القابلة للاختزال في السلاسل (أو هياكل البيانات الأخرى).إضافة إلى ذلك، ونظرًا لأنه يمكن وصف معظم الكائنات الرياضية من حيث السلاسل، أو كنهاية ممتالية من السلاسل، فيمكن استخدامها لدراسة مجموعة واسعة من الكائنات الرياضية، بما في ذلك الأعداد الصحيحة. أحد الدوافع الرئيسية وراء AIT هو دراسة المعلومات التي تحملها الكائنات الرياضية كما هو الحال في مجال ماوراء الرياضيات، على سبيل المثال، كما هو موضح من خلال نتائج عدم الاكتمال المذكورة أدناه. وقد جاءت الدوافع الرئيسية الأخرى من تجاوز حدود نظرية المعلومات الكلاسيكية للأشياء الفردية والثابتة، وإضفاء الطابع الرسمي على مفهوم العشوائية، وإيجاد استنتاج احتمالي ذي معنى دون معرفة مسبقة بتوزيع الاحتمالات (على سبيل المثال، ما إذا كان مستقلاً وموزعًا بشكل متطابق، أو ماركوفي، أو حتى ثابتًا). إذن، فهي تعتمد بشكل أساسي على ثلاثة مفاهيم رياضية رئيسية والعلاقات بينها: التعقيد الخوارزمي، والعشوائية الخوارزمية، والاحتمالية الخوارزمية.