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