# نظرية المعلومات الخوارزمية

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

## ملخص

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

## التاريخ

تأسست نظرية المعلومات الخوارزمية على يد راي سولومونوف الذي نشر الأفكار الأساسية التي يقوم عليها هذا المجال كجزء من اختراعه للاحتمالية الخوارزمية - وهي طريقة للتغلب على المشاكل الخطيرة المرتبطة بتطبيق قواعد بايز في الإحصاء. وقد وصف نتائجه لأول مرة في مؤتمر في معهد كاليفورنيا للتكنولوجيا في عام 1960، وفي تقرير في فبراير 1960، «تقرير أولي عن نظرية عامة للاستدلال الاستقرائي.» تم تطوير نظرية المعلومات الخوارزمية بشكل مستقل في وقت لاحق من قبل أندريه كولموغوروف، في عام 1965 وغريغوري تشايتين، حوالي عام 1966.
هناك عدة أشكال مختلفة لتعقيد كولموغوروف أو المعلومات الخوارزمية؛ ولعل أكثرها استخدامًا هو الذي يعتمد على برامج تحديد الذات ويرجع ذلك أساسًا إلى ليونيد ليفين (1974). كما ساهم بير مارتن لوف بشكل كبير في نظرية المعلومات الخاصة بالتسلسلات اللانهائية. كما أن تقديم نهج بديهي لنظرية المعلومات الخوارزمية يعتمد على بديهيات بلوم (بلوم 1967) بواسطة مارك بورجين في ورقة بحثية قدمها للنشر أندريه كولموغوروف (بورجين 1982). أما النهج البديهي فيشمل مناهج أخرى في نظرية المعلومات الخوارزمية. التي من الممكن معالجتها كحالات خاصة من المقاييس المحددة بديهيًا لهذا النهج. وبدلاً من إثبات نظريات مماثلة، مثل نظرية الثبات الأساسية، من الممكن استنتاج كل هذه النتائج بسهولة من نظرية واحدة مقابلة تم إثباتها في الإطار البديهي. وهذه ميزة عامة للنهج البديهي في الرياضيات. لذلك، تم تطوير النهج البديهي لنظرية المعلومات الخوارزمية في الكتاب (Burgin 2005) وتم تطبيقه على مقاييس البرمجيات (Burgin وDebnath، 2003؛ Debnath وBurgin، 2003).

## تعريفات دقيقة

يقال أن السلسلة الثنائية عشوائية إذا كانت تعقيد كولموغوروف للسلسلة تساوي على الأقل طول السلسلة. تظهر حجة العد البسيطة أن بعض السلاسل ذات أي طول معين تكون عشوائية، وأن جميع السلاسل تقريبًا قريبة جدًا من أن تكون كذلك أيضا. نظرًا لأن تعقيد كولموغوروف يعتمد على اختيار ثابت لآلة تورينج العالمية (بشكل غير رسمي، "لغة وصف" ثابتة يتم فيها تقديم "الأوصاف")، فإن مجموعة السلاسل العشوائية تعتمد على اختيار آلة عالمية ثابتة. ومع ذلك، فإن مجموعة هذه الأخيرة، ككل، لها خصائص مماثلة بغض النظر عن الآلة الثابتة، وبالتالي يمكننا (وهذا ما يحدث في كثير من الأحيان) التحدث عن خصائص السلاسل العشوائية كمجموعة دون الحاجة إلى تحديد آلة عالمية أولاً.
يقال أن تسلسل ثنائي لانهائي عشوائي إذا كان بالنسبة لبعض الثوابت c، ولجميع n، فإن تعقيد كولموغوروف للجزء الأولي بطول n من التسلسل يساوي n على الأقل - ج. يمكن إثبات أن كل تسلسل تقريبًا (من وجهة نظر المقياس القياسي - "العملة العادلة" أو مقياس لوبيج - على مساحة التسلسلات الثنائية اللانهائية) عشوائي. بالإضافة إلى ذلك، بما أنه من الممكن إظهار أن تعقيد كولموغوروف بالنسبة إلى آلتين عالميتين مختلفتين يختلف بمقدار ثابت واحد على الأكثر، فإن مجموعة التسلسلات اللانهائية العشوائية لا تعتمد على اختيار الآلة العالمية (على النقيض من السلاسل المحدودة). يُطلق على هذا التعريف للعشوائية عادةً اسم عشوائية مارتن-لوف، نسبةً إلى بير مارتن-لوف، لتمييزها عن المفاهيم الأخرى المشابهة للعشوائية. يُطلق عليه أحيانًا أيضًا اسم العشوائية 1 لتمييزه عن المفاهيم الأقوى الأخرى للعشوائية (العشوائية 2، والعشوائية 3، وما إلى ذلك). فبالإضافة إلى مفاهيم عشوائية مارتن-لوف، هناك أيضًا عشوائية متكررة، وعشوائية شنور، وعشوائية كورتز وما إلى ذلك. أظهر يونج وانج أن كل مفاهيم العشوائية هذه مختلفة تماما عن بعضها البعض.
(يمكن عمل تعريفات ذات صلة للأبجديات الأخرى غير المجموعة$\{0,1\}$.)

## تسلسل محدد

نظرية المعلومات الخوارزمية (AIT) هي نظرية المعلومات الخاصة بالأشياء الفردية، باستخدام علوم الكمبيوتر، وتهتم بالعلاقة بين الحساب والمعلومات والعشوائية.
يمكن قياس محتوى المعلومات أو تعقيد شيء ما من خلال طول أقصر وصف له. على سبيل المثال السلسلة
"0101010101010101010101010101010101010101010101010101010101010101"
تحتوي على وصف قصير "32 تكرارًا لـ '01'"، بينما
"1100100001100001110111101110110011111010010000100101011110010110"
من المفترض أنه لا يوجد وصف بسيط بخلاف كتابة السلسلة نفسها.
بشكل أكثر رسمية، يتم تعريف التعقيد الخوارزمي (AC) لسلسلة x على أنه طول أقصر برنامج يحسب أو يخرج x، حيث يتم تشغيل البرنامج على جهاز كمبيوتر عالمي مرجعي ثابت.
إن المفهوم المرتبط ارتباطًا وثيقًا هو احتمال أن يقوم جهاز كمبيوتر عالمي بإخراج سلسلة x عند تزويده ببرنامج تم اختياره عشوائيًا. لذلك، فإن احتمال "سولومونوف" الخوارزمي (AP) هذا هو المفتاح في معالجة المشكلة الفلسفية القديمة المتمثلة في الاستقراء بطريقة رسمية.
العيب الرئيسي لـ AC وAP هو عدم قابلية الحساب الخاصة بهما. إن التعقيد "ليفين" المحدود بالوقت يعاقب البرنامج البطيء عن طريق إضافة لوغاريتم وقت تشغيله إلى طوله. يؤدي هذا إلى متغيرات قابلة للحساب من AC وAP، ويحل البحث العالمي "ليفين" (الولايات المتحدة) جميع مشاكل العكس في الوقت الأمثل (باستثناء بعض الثوابت المضاعفة الكبيرة بشكل غير واقعي).
يسمح كل من AC وAP أيضًا بتعريف رسمي ودقيق لعشوائية السلاسل الفردية بحيث لا تعتمد على الحدس الفيزيائي أو الفلسفي حول عدم الحتمية أو الاحتمالية. تقريبًا، تكون السلسلة عشوائية خوارزمية "مارتن-لوف" (AR) إذا كانت غير قابلة للضغط. بمعنى أن تعقيدها الخوارزمي يساوي طولها.
AC وAP وAR هي التخصصات الفرعية الأساسية لـ AIT، لكن AIT تولد العديد من المجالات الأخرى. إنه بمثابة الأساس لمبدأ طول الوصف الأدنى (MDL)، ويمكنه تبسيط الأدلة في نظرية التعقيد الحسابي أيضا، وقد تم استخدامه لتحديد مقياس التشابه العالمي بين الكائنات، وحل مشكلة ديمون ماكسويل، وغيرها الكثير.

## مراجع

* 1 2 Chaitin 1975
* ↑ or, for the mutual algorithmic information, informing the algorithmic complexity of the input along with the input itself.
* 1 2 Calude 2013
* ↑ Downey، Rodney G.؛ Hirschfeldt، Denis R. (2010). Algorithmic Randomness and Complexity. Springer. ISBN:978-0-387-68441-3.
* ↑ Li & Vitanyi 2013
* ↑ Vitanyi, P. "Obituary: Ray Solomonoff, Founding Father of Algorithmic Information Theory" |مسار أرشيف =https://archive.today/20120630213134/http://homepages.cwi.nl/~paulv/obituary.html%7Cdate=2012-06-30}}
* ↑ Paper from conference on "Cerebral Systems and Computers", California Institute of Technology, February 8–11, 1960, cited in "A Formal Theory of Inductive Inference, Part 1, 1964, p. 1
* ↑ Solomonoff, R., "A Preliminary Report on a General Theory of Inductive Inference", Report V-131, Zator Co., Cambridge, Ma., (November Revision of February 4, 1960 report.) نسخة محفوظة 2022-10-28 على موقع واي باك مشين.
* ↑ Wang، Yongge (1996). Randomness and Complexity (PDF) (PhD thesis). University of Heidelberg. مؤرشف من الأصل (PDF) في 2021-12-02.
* بوابة رياضيات
* بوابة علم الحاسوب