תורת החישוביות/סיבוכיות קולמוגורוב: הבדלים בין גרסאות בדף

בפרק זה נגדיר במדויק את הרעיון הנ״ל תוך שימוש ב[[תורת_החישוביות/מכונת טיורינג|מכונות טיורינג]]. ב[[#הגדרות|הגדרות]] נגדיר את [[w:{{וק|סיבוכיות קולמוגורוב|סיבוכיות הקולמוגורוב]]}} של מחרוזת כאורך הקצר ביותר של מ"ט המייצרת אותה. רעיון זה של סיבוכיות קולמוגורוב מקשר בין תחום החישוביות לתחומים אחרים, כגון [[w:{{וק|תורת האינפורמציה|תורת האינפורמציה]]}}, ויש לו מספר שימושים. ב[[#אי-חישוביות פונקציית הסיבוכיות|אי-חישוביות פונקציית הסיבוכיות]] נראה שאי אפשר לחשב אותה בעזרת מחשב. ב[[#אי-דחיסות מחרוזות|אי-דחיסות מחרוזות]] נראש שלמרות שאי אפשר לחשב את סיבוכיות הקולמוגורוב של אף מחרוזת, אפשר להראות שרוב המחרוזות אינן דחיסות, במובן זה שאין להן סיבוכיות קולמוגורוב קצרה. [[#כלל השרשרת לסיבוכיות|כלל השרשרת לסיבוכיות]] נדון בסיבוכיות המותנה של מחרוזת, דהיינו סיבוכיות תיאור מחרוזת בהנחה שמחרוזת אחרת כבר ידועה.