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

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