نظریه الگوریتمی اطلاعات
از ویکیپدیا، دانشنامهٔ آزاد
 |
در متن این مقاله از هیچ منبع و مأخذی نام برده نشدهاست. شما میتوانید با افزودن منابع بر طبق اصول اثباتپذیری و شیوهنامهٔ ارجاع به منابع، به ویکیپدیا کمک کنید. مطالب بیمنبع احتمالاً در آینده حذف خواهند شد. |
نظریهٔ الگوریتمی اطلاعات، بخشی از علوم رایانه است که سعی دارد با استفاده از ابزارهایی انتخاب شده از حوزهٔ علم رایانه نظری مفهوم پیچیدگی را تحت کنترل خود درآورده و قابل فهم سازد. ایدهٔ اصلی این رشته تعریف نمودن پیچیدگی (پیچیدگی توصیفی، پیچیدگی کولموگوروف و یا پیچیدگی کولموگوروف-چیتین) یک رشته به عنوان طول کوتاهترین برنامهای که آن رشته را نتیجه دهد، است. رشتههایی که از برنامههای کوتاه حاصل میشوند، معمولاً خیلی پیچیده نیستند. این نظریه بطور شگفتآوری عمیق است و از آن میتوان برای شرح و اثبات نتایج امکانناپذیری وابسته به نظریهٔ ناتمامیت گودل و مسألهٔ توقف استفاده نمود.
