תורת החישוביות/סיבוכיות קולמוגורוב

כיצד מחליטים האם מחרוזת היא אקראית או נתונה לפי חוקיות מסויימת? נתבונן בשתי המחרוזות הבאות:

1. 0101010101010101010101010101010101010101
2. 0011010010001000010111011110101010100101

אינטואיטיבית, המחרוזת הראשונה בעלת חוקיות ברורה ואילו השניה נראית "אקראית" וחסרת חוקיות, אולם כיצד אפשר להגדיר זאת בצורה מדוייקת? נשים לב שאפשר לתאר כיצד לייצר את המחרוזת הראשונה בצורה קצרה: "כתוב את הרצף '01' 20 פעמים", אך את ייצור המחרוזת השנייה כנראה שנצטרך לתאר פחות-או-יותר בעזרת תוכנה: "כתוב את הרצף 0011010010001000010111011110101010100101".

בפרק זה נגדיר במדויק את הרעיון הנ״ל תוך שימוש במכונות טיורינג. בהגדרות נגדיר את סיבוכיות הקולמוגורוב של מחרוזת כאורך הקצר ביותר של תוכנית המייצרת אותה. רעיון זה של סיבוכיות קולמוגורוב מקשר בין תחום החישוביות לתחומים אחרים, כגון תורת האינפורמציה, ויש לו מספר שימושים. באי-חישוביות פונקציית הסיבוכיות נראה שאי אפשר לחשב אותה בעזרת מחשב. באי-דחיסות מחרוזות נראה שלמרות שאי אפשר לחשב את סיבוכיות הקולמוגורוב של אף מחרוזת, אפשר להראות שרוב המחרוזות אינן דחיסות, במובן זה שאין להן סיבוכיות קולמוגורוב קצרה. כלל השרשרת לסיבוכיות נדון בסיבוכיות המותנה של מחרוזת, דהיינו סיבוכיות תיאור מחרוזת בהנחה שמחרוזת אחרת כבר ידועה.

בפרק יישומי אי-דחיסות נראה יישום של סיבוכיות קולמוגורוב. כאמור, אפשר להראות שלרוב המחרוזות אין סיבוכיות קולמוגורוב קצרה, ונראה יישומים קומבינטוריים שונים של רעיון זה. בפרק הסתברות אוניברסאלית נבסס הלאה את סיבוכיות קולמוגורוב כמדד לסיבוכיות מחרוזות, ונראה כיצד אפשר להשתמש בו כדי להגדיר הסתברות "אובייקטיווית" להווצרות מחרוזות.

הגדרות

לסיבוכיות קולמוגורוב מספר הגדרות, אשר אינן נבדלות ביניהן באופן מהותי, אלא במידת הדיוק והגמישות. נראה כעת שלוש הגדרות לסיבוכיות זו. בחלק זה נשתמש בהגדרה השלישית מביניהן.

עם זאת, בפרק זה נשתמש בהגדרה גמישה יותר (ומדוייקת פחות), התופסת יותר את רוח הדברים.

ראשית, נניח שיש לנו שפת תכנות אוניברסאלית $U$ כלשהי, דהיינו שפה שבעזרתה אפשר לכתוב כל שפת תכנות אחרת. (לפי תזת צ'רץ'-טיורינג, כל שפה כזו שקולה בעוצמתה למ"ט.) כדוגמה לשפה כזו, אפשר לחשוב על פייתון, שפת C, או כל שפת תכנות כללית אחרת. בהנתן תוכנית $M$ נכתוב $M_U(w)$ כדי לתאר את תוצאת ריצתה של התוכנית $M$ על קלט $w$, כאשר מפרשים אותה כתוכנית בשפה $U$.

תבנית:מבנה תבנית

נשים לב שאם יש לנו שתי שפות אוניברסאליות, נניח $U$ ו$U^{\prime }$, אז סיבוכיות הקולמוגורוב של מחרוזות לא יכול להיות שונה מדי תחת שתי השפות. ככלות הכל, נניח שיש מחרוזת בעלת תוכנית קצרה מאד בפייתון המייצרת אותה, ואילו כל תוכנית בשפת C המתארת אותה ארוכה מאד. היות ששפת C היא שפה אוניברסאלית, נוכל לתאר את המחרוזת בשפת C בעזרת שילוב תיאור של שפת פייתון עצמה (בשפת C), ותיאור התכנית בשפת פייתון המייצרת את המחרוזת.

הדבר מוביל אותנו לאבחנה הבאה:

בעקבות משפט זה, ברור שאפשר להחליט שרירותית על שפה אוניברסאלית $U$ כלשהי, ולהגדיר את סיבוכיות קולמוגורוב בעזרתה. כל הגדרה בעזרת שפה אחרת, תיבדל ממנה לכל היותר בקבוע חיבורי כלשהו. נגדיר לכן את ההגדרה האחרונה, בה נשתמש בחלק זה:

לעתים המחרוזת $x$ כבר ידועה, ואנו רוצים לתאר מחרוזת נוספת, $y$. בהנחה ש$x$ ו$y$ מתארים דברים דומים, ייתכן שניתן להשתמש בתיאור של $x$ שנתון לנו, על־מנת לתאר את $y$ בצורה יותר פשוטה. לדוגמה, נניח ש$x$ ו$y$ מתארות כיצד לייצר את דגליהן של אירלנד ובלגיה (תמונות בצד). לאחר שנסביר מהו מלבן, מהו בד, ושאר הדברים שצריך כדי לתאר איך לייצר את דגל אירלנד, אפשר אולי לתאר את ייצור דגל בלגיה באמירה שהוא דומה לדגל אירלנד אלא שצבעיו הם כך וכך.

Flag of Ireland

Flag of Belgium

אי-חישוביות פונקציית הסיבוכיות

למרבה הצער, אין אפשרות לחשב את סיבוכיות קולמוגורוב. תבנית:משפט תבנית:הוכחה

אי-דחיסות מחרוזות

למרות שלא קיים אלגוריתם (מ״ט) שמחשב את סיבוכיות הקולמוגורוב של כל מחרוזת נתונה, קיימים מספר חסמים על סיבוכיות זו. קל לראות, שהסיבוכיות של מחרוזת $x$ לא תהיה גדולה בהרבה מאורך המחרוזת עצמה. תבנית:טענה

בנוסף, קיימות מחרוזות שסיבוכיות הקולמוגורוב שלהן איננה קטנה יותר מארכן. תבנית:משפט

יתרה מזאת, רוב המחרוזות אינן דחיסות באופן משמעותי. תבנית:משפט (הוכחת המשפט נמצאת בתרגיל: רוב המחרוזות אינן דחיסות במיוחד.) נשים לב שמשמעות הביטוי היא ש99.9% מהמחרוזות אינן דחיסות ביותר מ10 תווים!

כלל השרשרת לסיבוכיות

נניח שברשותנו שתי מחרוזות, $x$ ו$y$, וברצוננו למצוא את סיבוכיות הקולמוגורוב של שרשורן הנתן להפרדה - $x,y$ - כלומר $x$ ו$y$, כך שיודעים היכן מסתיים $x$ ומתחיל $y$.