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

نظرية المعلومات الخوارزمية ( AIT ) هي فرع من علوم الحاسوب النظرية يهتم بالعلاقة بين الحوسبة والمعلومات في الكائنات المُولَّدة حاسوبيًا (على عكس الكائنات المُولَّدة عشوائيًا )، مثل السلاسل النصية أو أي بنية بيانات أخرى . بعبارة أخرى، تُبين نظرية المعلومات الخوارزمية أن عدم قابلية الضغط الحسابي "يحاكي" (باستثناء ثابت يعتمد فقط على لغة البرمجة العالمية المختارة) العلاقات أو المتباينات الموجودة في نظرية المعلومات . ^{[ 1 ]} ووفقًا لغريغوري تشايتين ، فهي "نتيجة دمج نظرية المعلومات لشانون ونظرية قابلية الحوسبة لتورينغ في وعاء خلط ورجه بقوة". ^{[ 2 ]}

إلى جانب صياغة مقياس عالمي لمحتوى المعلومات غير القابل للاختزال للكائنات المولدة حاسوبيًا، تمثلت بعض الإنجازات الرئيسية لنظرية المعلومات الآلية في إثبات ما يلي: في الواقع، يتبع التعقيد الخوارزمي (في حالة التحديد الذاتي ) نفس المتباينات (باستثناء ثابت ^{[ 3 ]} ) التي يتبعها الإنتروبيا ، كما هو الحال في نظرية المعلومات الكلاسيكية؛ ^{[ 1 ]} العشوائية هي عدم قابلية للانضغاط؛ ^{[ 4 ]} وفي مجال البرمجيات المولدة عشوائيًا، يكون احتمال ظهور أي بنية بيانات من رتبة أقصر برنامج يولدها عند تشغيله على جهاز عالمي. ^{[ 5 ]}

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

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

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

من هذا المنظور، تحتوي موسوعة من 3000 صفحة في الواقع على معلومات أقل من 3000 صفحة من حروف عشوائية تمامًا، على الرغم من أن الموسوعة أكثر فائدة بكثير. والسبب في ذلك هو أنه لإعادة بناء التسلسل الكامل للحروف العشوائية، يجب معرفة كل حرف على حدة. من ناحية أخرى، لو حُذفت جميع حروف العلة من الموسوعة، لكان بإمكان أي شخص لديه معرفة معقولة باللغة الإنجليزية إعادة بنائها، تمامًا كما يمكن إعادة بناء جملة "Ths sntnc hs lw nfrmtn cntnt" من السياق والحروف الساكنة الموجودة.

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

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

أسس راي سولومونوف نظرية المعلومات الخوارزمية ، ^{[ 7 ]} حيث نشر الأفكار الأساسية التي يقوم عليها هذا المجال كجزء من ابتكاره للاحتمالية الخوارزمية - وهي طريقة للتغلب على المشكلات الجدية المرتبطة بتطبيق قواعد بايز في الإحصاء. وقد وصف نتائجه لأول مرة في مؤتمر في معهد كاليفورنيا للتكنولوجيا (كالتك) عام 1960، ^{[ 8 ]} وفي تقرير نُشر في فبراير 1960 بعنوان "تقرير أولي عن نظرية عامة للاستدلال الاستقرائي". ^{[ 9 ]} ثم طُوّرت نظرية المعلومات الخوارزمية بشكل مستقل لاحقًا على يد أندريه كولموغوروف عام 1965 وغريغوري تشايتين حوالي عام 1966.

توجد عدة صيغ لتعقيد كولموغوروف أو المعلومات الخوارزمية؛ وأكثرها استخدامًا تلك القائمة على البرامج ذاتية التحديد ، والتي يعود الفضل فيها بشكل أساسي إلى ليونيد ليفين (1974). كما أسهم بير مارتن-لوف إسهامًا كبيرًا في نظرية معلومات المتتاليات اللانهائية. وقدّم مارك بورغين منهجًا بديهيًا لنظرية المعلومات الخوارزمية، قائمًا على بديهيات بلوم (بلوم 1967)، في ورقة بحثية قدّمها أندريه كولموغوروف للنشر (بورغين 1982). يشمل المنهج البديهي مناهج أخرى في نظرية المعلومات الخوارزمية. ومن الممكن التعامل مع مقاييس المعلومات الخوارزمية المختلفة كحالات خاصة من مقاييس المعلومات الخوارزمية المُعرّفة بديهيًا. فبدلًا من إثبات نظريات متشابهة، مثل نظرية الثبات الأساسية، لكل مقياس على حدة، يُمكن استنتاج جميع هذه النتائج بسهولة من نظرية واحدة مُقابلة مُثبتة في الإطار البديهي. وهذه ميزة عامة للمنهج البديهي في الرياضيات. تم تطوير النهج البديهي لنظرية المعلومات الخوارزمية بشكل أكبر في الكتاب (Burgin 2005) وتم تطبيقه على مقاييس البرمجيات (Burgin and Debnath, 2003; Debnath and Burgin, 2003).

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

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

(يمكن وضع تعريفات ذات صلة للأبجديات الأخرى غير المجموعة)${\displaystyle \{0,1\}}$.)

نظرية المعلومات الخوارزمية (AIT) هي نظرية المعلومات الخاصة بالأشياء الفردية، باستخدام علوم الحاسوب، وتهتم بالعلاقة بين الحساب والمعلومات والعشوائية.

يمكن قياس محتوى المعلومات أو تعقيد الكائن بطول أقصر وصف له. على سبيل المثال، السلسلة

"0101010101010101010101010101010101010101010101010101010101010101"

يحتوي على وصف مختصر "32 تكرارًا للرقم '01'"، بينما

"1100100001100001110111101110110011111010010000100101011110010110"

من المفترض أنه ليس له وصف بسيط سوى كتابة السلسلة نفسها.

بصورة أكثر رسمية، يتم تعريف التعقيد الخوارزمي (AC) لسلسلة x على أنه طول أقصر برنامج يقوم بحساب أو إخراج x ، حيث يتم تشغيل البرنامج على جهاز كمبيوتر مرجعي عالمي ثابت.

ثمة مفهوم وثيق الصلة باحتمالية أن يُخرج حاسوب شامل سلسلة نصية x عند تغذيته ببرنامج مُختار عشوائيًا. تُعدّ احتمالية "سولومونوف" الخوارزمية هذه أساسية في معالجة مشكلة الاستقراء الفلسفية القديمة بطريقة رسمية.

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

يُتيح كلٌّ من AC و AP تعريفًا رسميًا ودقيقًا لعشوائية السلاسل الفردية، بحيث لا يعتمد على الحدس الفيزيائي أو الفلسفي حول عدم الحتمية أو الاحتمالية. وبشكلٍ عام، تُعتبر السلسلة عشوائية خوارزميًا وفقًا لخوارزمية "مارتن-لوف" (AR) إذا كانت غير قابلة للضغط، بمعنى أن تعقيدها الخوارزمي يساوي طولها.

تُعدّ AC وAP وAR التخصصات الفرعية الأساسية لنظرية الذكاء الاصطناعي، إلا أن هذه النظرية تتفرع إلى العديد من المجالات الأخرى. فهي تُشكّل أساس مبدأ الحد الأدنى لطول الوصف (MDL)، وتُسهّل البراهين في نظرية التعقيد الحسابي ، وقد استُخدمت لتعريف مقياس تشابه عالمي بين الكائنات، كما أنها تُحلّ مشكلة ماكسويل ديمون ، وغيرها الكثير.

• نظرية المعلومات الخوارزمية في موقع سكولاربيديا
• رواية تشايتين لتاريخ معهد آسيا للتكنولوجيا .