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