تاریخچه ایجاد مفهوم ابهام کولموگروف (Kolmogorov Complexity )
در ابتدای سال 1964 آقای سولومونف ( Solomonoff ) ریاضیدانی که در زمینه هوش مصنوعی تحقیقاتی را انجام میداد نتیجه گرفت که هر مسئله در اصول استنتاح ریاضی قابل مدل کردن به صورت تخمین یک دنباله باینری با طول به اندازه کافی بزرگ می باشد ، او فرض کرد که تمامی اطلاعات مورد نیاز مساله در داخل دنباله وجود دارد و سپس با این فرض احتمال زیر را برای یک رشته x تعریف کرد :
که p ها ، همه برنامه هایی هستند که رشته x را تولید می کنند .
این که این تعریف چه رابطه ای با مفهوم مساله پیدا می کند بعدها مشخص خواهد شد . مشکل آنجا بود که در بسیاری موارد این جمع واگرا بوده و قابل محاسبه نبود .
در 1965 آقای کولموگروف ریاضیدان مشهور ، که زمینه اصلی کارش تئوری اطلاعات بود با ارائه یک مقاله ابهام را با دیدی متفاوت تعریف کرده و نشان داد که چطور این تعریف از ابهام با نظریات مطرح در باب تئوری اطلاعات رابطه پیدا میکند .
اینکه اشیاء در واقعیت طبیعی به دو صورت ساده و پیچیده وجود دارند بر کسی پوشیده نیست اما سئوال این است که برای توصیف یک شیئ چه راههایی همگرا هستند . کار اصلی این دو ریاضیدان این بود که با الگو گرفتن از نظریات ریاضی الگوریتمها ، آزادی و بی قیدی این مساله را محدود کرده و با ارائه یک نعریف غیر قابل تغییر از ابهام ، راه را برای توصیف یک شی باز کردند .
شاید مهمترین مشوق کولموگروف برای کار روی این نظریه ، تلاش برای فرموله کردن یک دنباله تصادفی بود او توانست به راحتی بین تعریف خود از ابهام یک متغیر تصادفی و میزان تصادفی بودن رشته ارتباط برقرار کند و بسیاری از نظرات مطرح بالخصوص در مورد دنباله های نامحدود را پایه گذاری کند .
ایده های کولموگروف توسط دانشجویان و بقیه اساتید پیگیری شد ( در مورد تصادفی بودن ) بخصوص مارتین لوف که تصور کولموگروف را از تئوری مجموعه ها به توزیع های احتمالات تسری داد و روشن شد که اگر p یک توزیع احتمال ساده در یک مجموعه محدود A باشد ، می توانیم عنصر x عضو این مجموعه را تصادفی تعریف کنیم اگر ابهام کولموگروف که تعریف آن خواهد آمد ، خیلی نزدیک به باند بالایی خود – log p(x) باشد .
در واقع تعریف قبلی کولموگروف یک حالت خاص از این تعریف به حساب می آید که توزیع p در مجموعه A یکنواخت فرض شود .
تحقیقاتی که در ادامه نظریات کولموگروف مطرح شد و سبب تکمیل این مباحث گردید بصورت عملی به سه بخش تقسیم میشود ؛ مفهوم ابهام (Complexity) ، تصادفی بودن (Randomness) و اطلاعات ( Information) .
در بحث ابهام و در ادامه تعریف ابهام کولموگروف ، بعدها توسط آقای لوین مفهوم ، Prefix Complexity تعریف شد که دارای خصوصیات برجسته ای بود این تعریف برای غلبه و حل بعضی مسائل تکنیکی در تئوری اطلاعات معرفی شد و بطور مثال فقدان تقارن در تعریف اطلاعات ( به مفهوم کولموگروف ) و تئوری تصادفی بودن الگوریتمی را تصحیح و تکامل داد .