نظریه الگوریتمی اطلاعات

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

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