تعقيد كولموگوروف

هذه الصورة توضح جزءاً من مجموعة ماندلبرو. إن تخزين لون كل بكسل ذي الـ24 بت سيتطلب 1.62 مليون بتة، ولكن يمكن لبرنامج حاسوب صغير أن يولد ملايين البتات باستخدام تعريف مجموعة ماندلبرو. فتعقيد كولموگوروف لهذه المجموعة يتعلق بالملف الذي يولد المجموعة، وهو أقل بكثير من 1.62 مليوناً.

في نظرية المعلومات الخوارزمية، تعقيد كولموگوروف لكائن ما، نص مثلاً، هو قياس الموارد التحسيبية اللازمة لتحديد هذا الكائن.

يعرف تعقيد كولموگوروف بمصطلحات أخرى مثل التعقيد الوصفي descriptive complexity ، تعقيد كولموگوروف-شاتان Kolmogorov-Chaitin ، complexity، stochastic complexity، ، algorithmic entropy، program-size complexity.

مثال: ليكن لدينا السلسلتين النصيتين الآتيتين حيث طول كل منهما هو 64 محرفاً، ولا تضم سوى أحرفاً، وأرقاماً، وفراغات:

abababababababababababababababababababababababababababababababab
4c1j5b2p0cv4w1x8rx2y39umgw5q85s7uraqbjfdppa0q7nieieqe9noc4cvafzf

فيمكن وصف السلسلة الأولى ببساطة بسلسلة أخرى هي "ab 32 مرة"، والتي تضم تسعة محارف فقط. أما بالنسبة للسلسلة الثانية فلا يوجد وصف بسيط (باستخدام مجموعة المحارف نفسها) سوى كتابة السلسلة نفسها، والتي تضم 64 محرفاً.

بشكل أكثر صورية، إن تعقيد سلسلة نصية ما هو أقصر وصف باستخدام لغة وصفية كونية ثابتة.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

 انظر أيضاً

• Data compression
• Inductive inference
• Kolmogorov structure function
• Important publications in algorithmic information theory
• Levenshtein distance
• Grammar induction

 مراجع

• Blum, M. (1967), "On the Size of Machines", Information and Control, v. 11, pp. 257-265.
• Burgin, M. (1982), "Generalized Kolmogorov complexity and duality in theory of computations", Notices of the Russian Academy of Sciences, v.25, No. 3, pp. 19-23.
• Mark Burgin (2005), Super-recursive algorithms, Monographs in computer science, Springer.
• Burgin, M. and Debnath, N. "Hardship of Program Utilization and User-Friendly Software", in Proceedings of the International Conference “Computer Applications in Industry and Engineering”, Las Vegas, Nevada, 2003, pp. 314-317.
• Cover, Thomas M. and Thomas, Joy A., Elements of information theory, 1st Edition. New York: Wiley-Interscience, 1991. ISBN 0-471-06259-6. 2nd Edition. New York: Wiley-Interscience, 2006. ISBN 0-471-24195-4.
• Debnath, N.C. and Burgin, M. (2003), "Software Metrics from the Algorithmic Perspective", in Proceedings of the ISCA 18th International Conference “Computers and their Applications”, Honolulu, Hawaii, pp. 279-282.
• Kolmogorov, Andrei N. (1963). "On Tables of Random Numbers". Sankhyā Ser. A. 25: 369–375. قالب:MR
• Kolmogorov, Andrei N. (1963). "On Tables of Random Numbers". Theoretical Computer Science. 207 (2): 387--395. doi:10.1016/S0304-3975(98)00075-9. {{cite journal}}: Unknown parameter |DUPLICATE DATA: year= ignored (help) قالب:MR
• Lajos, Rónyai and Gábor, Ivanyos and Réka, Szabó, Algoritmusok. TypoTeX, 1999. ISBN 963-2790-14-6
• Solomonoff, Ray, "A Preliminary Report on a General Theory of Inductive Inference", Report V-131, Zator Co., Cambridge, Ma. Feb 4, 1960, revision, Nov., 1960.
• Solomonoff, Ray, "A Formal Theory of Inductive Inference", Information and Control, Part I, Vol 7, No. 1 pp 1-22, March 1964 and Part II, Vol 7, No. 2 pp 224-254, June 1964.
• Li, Ming and Vitányi, Paul, An Introduction to Kolmogorov Complexity and Its Applications, Springer, 1997. Introduction chapter full-text.
• Yu Manin, A Course in Mathematical Logic, Springer-Verlag, 1977.
• Sipser, Michael, Introduction to the Theory of Computation, PWS Publishing Company, 1997. ISBN 0-534-95097-3.
• Wallace, C. S. and Dowe, D. L., Minimum Message Length and Kolmogorov Complexity, Computer Journal, Vol. 42, No. 4, 1999).

 روابط خارجية

• The Legacy of Andrei Nikolaevich Kolmogorov
• Chaitin's online publications
• Solomonoff's IDSIA page
• Generalizations of algorithmic information by J. Schmidhuber
• Ming Li and Paul Vitanyi, An Introduction to Kolmogorov Complexity and Its Applications, 2nd Edition, Springer Verlag, 1997.
• Tromp's lambda calculus computer model offers a concrete definition of K()
• Universal AI based on Kolmogorov Complexity ISBN 3-540-22139-5 by M. Hutter: ISBN 3-540-22139-5
• David Dowe's Minimum Message Length (MML) and Occam's razor pages.
• P. Grunwald, M. A. Pitt and I. J. Myung (ed.), Advances in Minimum Description Length: Theory and Applications, M.I.T. Press, April 2005, ISBN 0-262-07262-9.