نظرية المعلومات الخوارزمية
نظرية المعلومات الخوارزمية (Algorithmic information theory)( AIT ) هي فرع من علوم الكمبيوتر النظرية التي تهتم بالعلاقة بين الحساب والمعلومات الخاصة بالأشياء المولدة حسابيًا (على عكس الأشياء المولدة تصادفيا )، مثل السلاسل أو أي منبنى البيانات أخرى. بعبارة أخرى، تبين هذه نظرية المعلومات الخوارزمية أن عدم قابلية الضغط الحسابي "تحاكي" (باستثناء الثابت الذي يعتمد فقط على لغة البرمجة العالمية المختارة) العلاقات أو التفاوتات الموجودة في نظرية المعلومات . [1] وفقًا لغريجوري تشايتين ، فإن هذا هو "نتيجة وضع نظرية المعلومات الخاصة بشانون ونظرية الحوسبة الخاصة بتورينج في هزاز الكوكتيل و رجّها بقوة."
بالإضافة إلى صياغة مقياس عالمي لمحتوى المعلومات غير القابل للاختزال للأشياء المولدة حاسوبيًا، كانت بعض الإنجازات الرئيسية لـهذه النظرية هي إظهار أن: التعقيد الخوارزمي في الواقع يتبع (في الحالة المحددة ذاتيًا ) نفس التفاوتات (باستثناء الثابت [2] ) التي تتبعها الإنتروبية ، كما هو الحال في نظرية المعلومات الكلاسيكية؛ [1] العشوائية هي عدم القابلية للضغط؛ [3] و في نطاق البرامج المولدة عشوائيًا، فإن احتمال حدوث أي بنية بيانات هو من رتبة أقصر برنامج يولدها عند تشغيله على جهاز عالمي. [4]
تدرس AIT بشكل أساسي مقاييس محتوى المعلومات غير القابلة للاختزال في السلاسل (أو هياكل البيانات الأخرى).إضافة إلى ذلك، و نظرًا لأنه يمكن وصف معظم الكائنات الرياضية من حيث السلاسل، أو كنهاية ممتالية من السلاسل، فيمكن استخدامها لدراسة مجموعة واسعة من الكائنات الرياضية، بما في ذلك الأعداد الصحيحة . أحد الدوافع الرئيسية وراء AIT هو دراسة المعلومات التي تحملها الكائنات الرياضية كما هو الحال في مجال ماوراء الرياضيات ، على سبيل المثال، كما هو موضح من خلال نتائج عدم الاكتمال المذكورة أدناه. وقد جاءت الدوافع الرئيسية الأخرى من تجاوز حدود نظرية المعلومات الكلاسيكية للأشياء الفردية والثابتة، وإضفاء الطابع الرسمي على مفهوم العشوائية ، و إيجاد استنتاج احتمالي ذي معنى دون معرفة مسبقة بتوزيع الاحتمالات (على سبيل المثال، ما إذا كان مستقلاً وموزعًا بشكل متطابق ، أو ماركوفي ، أو حتى ثابتًا ). إذن، فهي تعتمد بشكل أساسي على ثلاثة مفاهيم رياضية رئيسية و العلاقات بينها: التعقيد الخوارزمي ، والعشوائية الخوارزمية ، والاحتمالية الخوارزمية . [5] [3]
ملخص
عدلتدرس نظرية المعلومات الخوارزمية بشكل أساسي مقاييس التعقيد على السلاسل (أو هياكل البيانات الأخرى). نظرًا لأنه يمكن وصف معظم الكائنات الرياضية من حيث السلاسل، أو كنهاية متتالية من السلاسل، فيمكن استخدامها لدراسة مجموعة واسعة من الكائنات الرياضية، بما في ذلك الأعداد الصحيحة .
بشكل غير رسمي، ومن وجهة نظر نظرية المعلومات الخوارزمية، فإن محتوى المعلومات في سلسلة ما يعادل طول التمثيل الذاتي المضغوط قدر الإمكان لتلك السلسلة. إن التمثيل المستقل هو في الأساس برنامج - في بعض لغات البرمجة العالمية الثابتة ولكنها غير ذات صلة - والذي عند تشغيله، يقوم بإخراج السلسلة الأصلية.
و من خلال وجهة النظر تلك، فإن موسوعة مكونة من 3000 صفحة تحتوي في الواقع على معلومات أقل من 3000 صفحة من الحروف العشوائية تمامًا، على الرغم من أن الموسوعة أكثر فائدة بكثير. يرجع ذلك إلى أنه لإعادة بناء التسلسل الكامل للحروف العشوائية، يجب علينا أن نعرف ما هو كل حرف على حدة. من ناحية أخرى، إذا تمت إزالة كل حرف علة من الموسوعة، فيمكن لأي شخص لديه معرفة معقولة باللغة الإنجليزية إعادة بنائها، تمامًا كما يمكن للمرء إعادة بناء الجملة "Ths sntnc hs lw nfrmtn cntnt" من السياق و الحروف الساكنة الموجودة.
على عكس نظرية المعلومات الكلاسيكية، فإن نظرية المعلومات الخوارزمية تقدم تعريفات رسمية و دقيقة لسلسلة عشوائية و تسلسل عشوائي لا نهائي لا يعتمدان على الحدس الفيزيائي أو الفلسفي حول عدم التحديد أو الاحتمالية . (تعتمد مجموعة السلاسل العشوائية على اختيار آلة تورينج العالمية المستخدمة لتحديد تعقيد كولموغوروف ، ولكن أي اختيار يعطي نتائج مقاربة متطابقة لأن تعقيد كولموغوروف للسلسلة ثابت كقيمة إضافية يعتمد فقط على اختيار آلة تورينج العالمية. ولهذا السبب فإن مجموعة التسلسلات اللانهائية العشوائية مستقلة عن اختيار الآلة العالمية. )
يبدو أن بعض نتائج نظرية المعلومات الخوارزمية، مثل نظرية عدم الاكتمال لتشايتين ، تتحدى الحدس الرياضي والفلسفي الشائع. ومن أبرز هذه الاكتشافات هو بناء ثابت تشايتين Ω ، وهو رقم حقيقي يعبر عن احتمالية توقف آلة تورينج العالمية المحددة ذاتيا عندما يتم توفير مدخلاتها عن طريق رمي عملة عادلة (يُعتقد أحيانًا أنها احتمالية توقف برنامج كمبيوتر عشوائي في النهاية). على الرغم من أن ثابتΩ يمكن تعريفه بسهولة، إلا أنه في أي نظرية متسقة قابلة للتحديد البديهي لا يمكننا إلا حساب عدد محدود من أرقام Ω ، وبالتالي فهي غير قابل للمعرفة إلى حد ما، مما يوفر حدًا مطلقًا للمعرفة يذكرنا بنظريات عدم الاكتمال لغودل . على الرغم من أنه لا يمكن تحديد أرقام Ω ، إلا أن العديد من خصائص Ω معروفة؛ على سبيل المثال، فهي عبارة عن تسلسل عشوائي خوارزميًا وبالتالي فإن أرقامه الثنائية موزعة بالتساوي (في الواقع هي طبيعية ).
التاريخ
عدلتأسست نظرية المعلومات الخوارزمية على يد راي سولومونوف [6] الذي نشر الأفكار الأساسية التي يقوم عليها هذا المجال كجزء من اختراعه للاحتمالية الخوارزمية - وهي طريقة للتغلب على المشاكل الخطيرة المرتبطة بتطبيق قواعد بايز في الإحصاء. و قد وصف نتائجه لأول مرة في مؤتمر في معهد كاليفورنيا للتكنولوجيا في عام 1960، [7] و في تقرير في فبراير 1960، "تقرير أولي عن نظرية عامة للاستدلال الاستقرائي." [8] تم تطوير نظرية المعلومات الخوارزمية بشكل مستقل في وقت لاحق من قبل أندريه كولموغوروف ، في عام 1965 وغريغوري تشايتين ، حوالي عام 1966.
هناك عدة أشكال مختلفة لتعقيد كولموغوروف أو المعلومات الخوارزمية؛ و لعل أكثرها استخدامًا هو الذي يعتمد على برامج تحديد الذات ويرجع ذلك أساسًا إلى ليونيد ليفين (1974). كما ساهم بير مارتن لوف بشكل كبير في نظرية المعلومات الخاصة بالتسلسلات اللانهائية. كما أن تقديم نهج بديهي لنظرية المعلومات الخوارزمية يعتمد على بديهيات بلوم (بلوم 1967) بواسطة مارك بورجين في ورقة بحثية قدمها للنشر أندريه كولموغوروف (بورجين 1982). أما النهج البديهي فيشمل مناهج أخرى في نظرية المعلومات الخوارزمية. التي من الممكن معالجتها كحالات خاصة من المقاييس المحددة بديهيًا لهذا النهج. و بدلاً من إثبات نظريات مماثلة، مثل نظرية الثبات الأساسية، من الممكن استنتاج كل هذه النتائج بسهولة من نظرية واحدة مقابلة تم إثباتها في الإطار البديهي. وهذه ميزة عامة للنهج البديهي في الرياضيات. لذلك، تم تطوير النهج البديهي لنظرية المعلومات الخوارزمية في الكتاب (Burgin 2005) وتم تطبيقه على مقاييس البرمجيات (Burgin وDebnath، 2003؛ Debnath وBurgin، 2003).
تعريفات دقيقة
عدليقال أن السلسلة الثنائية عشوائية إذا كانت تعقيد كولموغوروف للسلسلة تساوي على الأقل طول السلسلة. تظهر حجة العد البسيطة أن بعض السلاسل ذات أي طول معين تكون عشوائية، وأن جميع السلاسل تقريبًا قريبة جدًا من أن تكون كذلك أيضا. نظرًا لأن تعقيد كولموغوروف يعتمد على اختيار ثابت لآلة تورينج العالمية (بشكل غير رسمي، "لغة وصف" ثابتة يتم فيها تقديم "الأوصاف")، فإن مجموعة السلاسل العشوائية تعتمد على اختيار آلة عالمية ثابتة. ومع ذلك، فإن مجموعة هذه الأخيرة، ككل، لها خصائص مماثلة بغض النظر عن الآلة الثابتة، وبالتالي يمكننا (وهذا ما يحدث في كثير من الأحيان) التحدث عن خصائص السلاسل العشوائية كمجموعة دون الحاجة إلى تحديد آلة عالمية أولاً.
يقال أن تسلسل ثنائي لانهائي عشوائي إذا كان بالنسبة لبعض الثوابت c ، ولجميع n ، فإن تعقيد كولموغوروف للجزء الأولي بطول n من التسلسل يساوي n على الأقل - ج . يمكن إثبات أن كل تسلسل تقريبًا (من وجهة نظر المقياس القياسي - "العملة العادلة" أو مقياس لوبيج - على مساحة التسلسلات الثنائية اللانهائية) عشوائي. بالإضافة إلى ذلك، بما أنه من الممكن إظهار أن تعقيد كولموغوروف بالنسبة إلى آلتين عالميتين مختلفتين يختلف بمقدار ثابت واحد على الأكثر، فإن مجموعة التسلسلات اللانهائية العشوائية لا تعتمد على اختيار الآلة العالمية (على النقيض من السلاسل المحدودة). يُطلق على هذا التعريف للعشوائية عادةً اسم عشوائية مارتن-لوف ، نسبةً إلى بير مارتن-لوف ، لتمييزها عن المفاهيم الأخرى المشابهة للعشوائية. يُطلق عليه أحيانًا أيضًا اسم العشوائية 1 لتمييزه عن المفاهيم الأقوى الأخرى للعشوائية (العشوائية 2، والعشوائية 3، وما إلى ذلك). فبالإضافة إلى مفاهيم عشوائية مارتن-لوف، هناك أيضًا عشوائية متكررة، وعشوائية شنور، وعشوائية كورتز وما إلى ذلك. أظهر يونج وانج [9] أن كل مفاهيم العشوائية هذه مختلفة تماما عن بعضها البعض.
(يمكن عمل تعريفات ذات صلة للأبجديات الأخرى غير المجموعة .)
تسلسل محدد
عدلنظرية المعلومات الخوارزمية (AIT) هي نظرية المعلومات الخاصة بالأشياء الفردية، باستخدام علوم الكمبيوتر، و تهتم بالعلاقة بين الحساب و المعلومات و العشوائية.
يمكن قياس محتوى المعلومات أو تعقيد شيء ما من خلال طول أقصر وصف له. على سبيل المثال السلسلة
"0101010101010101010101010101010101010101010101010101010101010101"
تحتوي على وصف قصير "32 تكرارًا لـ '01'"، بينما
"1100100001100001110111101110110011111010010000100101011110010110"
من المفترض أنه لا يوجد وصف بسيط بخلاف كتابة السلسلة نفسها.
بشكل أكثر رسمية، يتم تعريف التعقيد الخوارزمي (AC) لسلسلة x على أنه طول أقصر برنامج يحسب أو يخرج x ، حيث يتم تشغيل البرنامج على جهاز كمبيوتر عالمي مرجعي ثابت.
إن المفهوم المرتبط ارتباطًا وثيقًا هو احتمال أن يقوم جهاز كمبيوتر عالمي بإخراج سلسلة x عند تزويده ببرنامج تم اختياره عشوائيًا. لذلك، فإن احتمال "سولومونوف" الخوارزمي (AP) هذا هو المفتاح في معالجة المشكلة الفلسفية القديمة المتمثلة في الاستقراء بطريقة رسمية.
العيب الرئيسي لـ AC و AP هو عدم قابلية الحساب الخاصة بهما. إن التعقيد "ليفين" المحدود بالوقت يعاقب البرنامج البطيء عن طريق إضافة لوغاريتم وقت تشغيله إلى طوله. يؤدي هذا إلى متغيرات قابلة للحساب من AC وAP، ويحل البحث العالمي "ليفين" (الولايات المتحدة) جميع مشاكل العكس في الوقت الأمثل (باستثناء بعض الثوابت المضاعفة الكبيرة بشكل غير واقعي).
يسمح كل من AC وAP أيضًا بتعريف رسمي ودقيق لعشوائية السلاسل الفردية بحيث لا تعتمد على الحدس الفيزيائي أو الفلسفي حول عدم الحتمية أو الاحتمالية. تقريبًا، تكون السلسلة عشوائية خوارزمية "مارتن-لوف" (AR) إذا كانت غير قابلة للضغط. بمعنى أن تعقيدها الخوارزمي يساوي طولها.
AC وAP وAR هي التخصصات الفرعية الأساسية لـ AIT، لكن AIT تولد العديد من المجالات الأخرى. إنه بمثابة الأساس لمبدأ طول الوصف الأدنى (MDL)، و يمكنه تبسيط الأدلة في نظرية التعقيد الحسابي أيضا ، وقد تم استخدامه لتحديد مقياس التشابه العالمي بين الكائنات، وحل مشكلة ديمون ماكسويل ، وغيرها الكثير.
انظر أيضا
عدل<div style="-moz-column-count:* Algorithmic probability
- Algorithmically random sequence
- Chaitin's constant
- Computational indistinguishability
- Distribution ensemble
- Epistemology – ابستيمولوجيا
- Inductive reasoning – صفحة توضيح لويكيميديا
- Inductive probability
- Invariance theorem
- Kolmogorov complexity
- Minimum description length
- Minimum message length
- Pseudorandom ensemble
- Pseudorandom generator
- Simplicity theory
- Shannon's source coding theorem
- Solomonoff's theory of inductive inference; -webkit-column-count:* Algorithmic probability
- Algorithmically random sequence
- Chaitin's constant
- Computational indistinguishability
- Distribution ensemble
- Epistemology – ابستيمولوجيا
- Inductive reasoning – صفحة توضيح لويكيميديا
- Inductive probability
- Invariance theorem
- Kolmogorov complexity
- Minimum description length
- Minimum message length
- Pseudorandom ensemble
- Pseudorandom generator
- Simplicity theory
- Shannon's source coding theorem
- Solomonoff's theory of inductive inference; column-count:* Algorithmic probability
- Algorithmically random sequence
- Chaitin's constant
- Computational indistinguishability
- Distribution ensemble
- Epistemology – ابستيمولوجيا
- Inductive reasoning – صفحة توضيح لويكيميديا
- Inductive probability
- Invariance theorem
- Kolmogorov complexity
- Minimum description length
- Minimum message length
- Pseudorandom ensemble
- Pseudorandom generator
- Simplicity theory
- Shannon's source coding theorem
- Solomonoff's theory of inductive inference;">{{{2}}}
مراجع
عدل- ^ ا ب Chaitin 1975
- ^ or, for the mutual algorithmic information, informing the algorithmic complexity of the input along with the input itself.
- ^ ا ب 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" نسخة محفوظة 2012-06-30 at archive.md
- ^ 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.)
- ^ Wang، Yongge (1996). Randomness and Complexity (PDF) (PhD thesis). University of Heidelberg.
