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

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

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

הגדרות

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

הגדרה: הסתברות אוניברסאלית של מחרוזת ההסתברות האוניברסאלית של מחרוזת $x$ היא $P_{u}(x)=\sum _{M\;|\;M(\epsilon )=x}\left|\Sigma \right|^{-\left|\langle M\rangle \right|}.$

נגדיר גם את הסתברות הקולמוגורוב של מחרוזת ע"י ביטוי אלגברי דומה (שלו קשה יותר למצוא מוטיווציה):

הגדרה: הסתברות אוניברסאלית של מחרוזת הסתברות הקולמוגורוב של מחרוזת $x$ היא $P_{K}(x)=\left|\Sigma \right|^{-K(x)}.$

בהקשר בין הסתברות אוניברסאלית להסתברות קולמוגורוב נראה ששתי הסתברויות אלו שוות עד כדי קבוע לא-טריוויאלי.

הקשר בין הסתברות אוניברסאלית להסתברות קולמוגורוב

משפט: שקילות הסתברות אוניברסאלית והסתברות קולמוגורוב קיים קבוע $c>0$ עבורו $\forall _{x}P_{K}(x)\leq P_{u}(x)\leq cP_{K}(x)$, ובאופן שקול, קיים קבוע $c'>0$ שעבורו $\forall _{x}K(x)-c'\leq \log \left({\frac {1}{P_{u}(x)}}\right)\leq K(x)).$

בשאר החלק נוכיח את שני הכוונים של משפט זה.

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

סיבוכיות קולמוגורוב היא לכל הפחות סיבוכיות אוניברסאלית

כוון זה קל להוכיח. הדבר נובע למעשה מההגדרה. נניח ש-$M_{x}^{K}$ היא התוכנית הקצרה ביותר המייצרת את $x$. אז

$P_{K}(x)=\left|\Sigma \right|^{-K(x)}=\left|\Sigma \right|^{-\left|\langle M_{x}^{K}\rangle \right|}\leq \sum _{M\;|\;M(\epsilon )=x}\left|\Sigma \right|^{-\left|\langle M\rangle \right|}=P_{u}(x).$

סיבוכיות קולמוגורוב היא לכל היותר סיבוכיות אוניברסאלית (עד כדי קבוע)

כדי להראות כוון זה, נשתמש בניסוח (המתמטי) השני של המשפט, דהיינו נראה כי קיים קבוע $c'>0$ שעבורו

$\forall _{x}K(x)-c'\leq \log \left({\frac {1}{P_{u}(x)}}\right).$

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

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

בניית עץ השיוך

בניית העץ 0 - עץ קידוד התחלתי

עץ השיוך הוא עץ אינסופי שלחלק מצמתיו משוייכות תוכניות המסתיימות (עם פלט כלשהו). תהליך בנייתו הוא אינסופי, ותיאור התהליך מורכב מעט. מתחילים עם עץ שבו לכל צומת יש $|\Sigma |$ ילדים (התרשים "בניית העץ 0" מצוייר בצד שמאל עבור א"ב בגודל 3). כל צומת נמצא באחד משלושה מצבים:

1. פנוי
2. משוייך
3. תפוס

בתחילה כל הצמתים נמצאים במצב פנוי.

התהליך משתמש בdovetailing, תהליך ה"הרצה במקביל" שראינו כבר במהלך הספר (לדוגמה, בהוכחת השקילות בין המודל הכללי למודל ההכרעה). מסדרים את כל התוכניות בסדר לקסיקורפי. מריצים את התוכנית הראשונה צעד אחד, לאחר מכן כ"א מ2 התוכניות הראשונות 2 צעדים, לאחר מכן כ"א מ3 התוכניות הראשונות 3 צעדים, וכו' וכו'.

במהלך הרצת הdovetailing, מדי פעם, תעצור תוכנית כלשהי עם פלט כלשהו. נסמן את התוכנית ה-$k$ שעוצרת כ-$M_{k}$ ואת המחרוזת שהיא מייצרת כ-$x_{k}$. בנוסף, נגדיר את שערוכנו להסתברות האוניברסלית של $x_{k}$ עד כה:

$P_{U}^{k}(x)=\sum _{i=1,\ldots k\;|\;x_{i}=x_{k}}|\Sigma |^{-|\langle M_{k}\rangle |}.$

קל לראות כי הביטוי שואף מלמטה להסתברות האוניברסאלית:

1. $\forall _{k}P_{U}^{k}(x)\leq P_{U}(x)$
2. $\lim _{k}P_{U}^{k}(x)=P_{U}(x)$

נסמן את שיערוכנו גם ללוגריתם ביטוי זה:

$n_{k}=\left\lceil \log _{|\Sigma |}\left({\frac {1}{P_{U}^{k}(x)}}\right)\right\rceil$

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

כשעוצרת תוכנית $M_{k}$, נחליט האם לשייכה לעץ בעזרת רשימה של שלשות שנחזיק בצד המתארות את התוכניות שעצרו כבר. השלשה המתאימה לתוכנית ה-$j$ שעצרה, מורכבת מ:

1. המחרוזת, $x_{j}$
2. אורך תיאור התוכנית, $l_{j}=l_{j}(x)=|\langle M_{j}\rangle |$
3. הצומת שאליו $M$ משוייכת, אם בכלל. את הצומת בעץ אפשר לתאר בעזרת מחרוזת של המסלול (לדוגמה, המחרוזת "01" מציינת הליכה שמאלה פעם אחת, ולאחריה הליכה למטה פעם אחת; המחרוזת "222" מציינת הליכה ימינה שלוש פעמים). לא כל תוכנית שהסתיימה משוייכת לצומת. נניח שיש סימון מיוחד, נניח "-", המציין שאין שיוך.

נחליט את שיוך $M_{k}$ לצומת כך:

בניית העץ 1 - שיוך צומת ראשון לתכנית בעלת אורך תיאור 1

1. נחפש ברשימה את האינדקסים בהם הופיעה המחרוזת בעבר: $J_{k}=\left\{j:x_{j}=x_{k}\right\}$ (אם עדיין לא סיימה תוכנית המייצרת את $x_{k}$, זו סדרה ריקה).
2. נבנה את סדרת ההערכות ללוגריתם: $n_{j}=n_{j}(x)\;|\;j\in J_{k}$, ונחליט לשייך את התוכנית לצומת כלשהו רק אם $n_{k}$ נמוך יותר מהערכים הקודמים (היות שמעגלים את הלוגריתם כלפי מעלה, לא בכל פעם בהכרח זה יקרה).
3. אם החלטנו לשייך, נמצא את הצומת הפנוי הראשון (משמאל לימין) ברמה $n_{k}+1$, ונשייך את $M$ אליו (בהתכנות בניית עץ השיוך נוכיח שבהכרח תמיד יהיה צומת פנוי). הצומת הופך להיות משוייך. נמחק את כל הצאצאים של הצומת מהעץ, וכל צומת במסלול מהצומת לראש העץ (כולל ראש העץ) הופך להיות תפוס.

לדוגמה (בתרשים "בניית העץ 1" המצוייר בצד שמאל), נניח שהתוכנית הראשונה שהסתיימה היא התוכנית שתיאורה הוא "1", והפלט שלה הוא "000111000". בשלב זה,

$|\Sigma |^{-|\langle M_{1}\rangle |}=3^{-1}={\frac {1}{3}}$

ולכן

$n_{1}(x_{1})=\left\lceil \log _{3}\left({\frac {1}{\frac {1}{3}}}\right)\right\rceil =1$

לכן עלינו לבחור צומת ברמה $1+1=2$. היותר שבשלב זה כל הצמתים בעץ פנויים, הצומת השמאלי ביותר ברמה 2 הופך להיות משוייך, והצמתים השמאליים ביותר ברמות 0 ו1 הופכים להיות תפוסים.

נניח שהתוכנית השניה שהסתיימה היא התוכנית שתיאורה הוא באורך מיליארד, והפלט שלה הוא שוב "000111000". בשלב זה,

$P_{U}^{2}(x_{2})=P_{U}^{2}(x_{1})=|\Sigma |^{-|\langle M_{2}\rangle |}=3^{-1,000,000,000}$

ולכן

$n_{2}(x_{2})=\left\lceil \log _{3}\left({\frac {1}{{\frac {1}{3}}+3^{-1,000,000,000}}}\right)\right\rceil =1$

(ולכן הוא לא השתנה). אמנם הרמה המתאימה היא 2, אך היות שברמה זו כבר יש צומת המשוייך לתוכנית המציירת מחרוזת זו, לא נשייך את התוכנית לצומת.

בניית העץ 2 - שיוך צומת שני לתכנית בעלת אורך תיאור 0

נמשיך כך הלאה. לדוגמה (בתרשים "בניית העץ 2" המצוייר בצד שמאל), נניח שהתוכנית השלישית שהסתיימה היא התוכנית שתיאורה הוא "" (המחרוזת הריקה), והפלט שלה הוא "011". בשלב זה,

$P_{U}^{3}(x_{3})=|\Sigma |^{-|\langle M_{3}\rangle |}=3^{-0}=1$

ולכן

$n_{3}(x_{3})=\left\lceil \log _{3}\left({\frac {1}{1}}\right)\right\rceil =0$

עלינו לשייך את התוכנית לצומת ברמה $0+1=1$. היות שהצומת השמאלי ביותר ברמה זו תפוס, נשייך אותו לצומת השני משמאל ברמה 1.

בניית העץ 3 - שיוך עוד מספר צמתים

נמשיך כך הלאה והלאה. לפי הdovetailing, כל תוכנית שתסתיים בסופו של דבר תישקל ותשוייך לצומת. כל מחרוזת המיוצרת ע"י תוכנית כלשהי, תשוייך לצומת כלשהו בעץ. נקבל עץ אינסופי, שרק לעליו יש שיוך (לדוגמה, בתרשים "בניית העץ 3" בצד שמאל).

קידוד ופענוח

עבור מחרוזת $x$ כלשהי, נניח ש-$M_{1},M_{2},\ldots$ הן התוכניות שיסתיימו ויפלטו את $x$. נניח ש-$h$ הוא הגובה הנמוך ביותר אליו יוחלט לשייך אחת מתוכניות אלו בעץ החיפוש (כלומר, מסתיימת תוכנית בעלת אורך $h-1$ המייצרת את $x$, ומשייכים תוכנית זו לצומת פנוי ברמה $h$). נשים לב לשתי נקודות:

1. $h$ מוגדרת היטב.
2. $h$ איננה נתנת לחישוב (ראינו כבר שפונקציית הסיבוכיות איננה נתנת לחישוב).

נניח שיש לנו אוראקל, עם זאת, המגלה לנו את $h$. במקרה זה, נוכל לחזור על תהליך בניית העץ, ונעצור ברגע שמשוייכת תוכנית המייצרת את $x$ לצומת בגובה $h$.

קידוד $x$ יורכב מתיאור סכמת בניית עץ השיוך, ותיאור המסלול לאותו צומת בגובה $h$.

אורך הקידוד, לכן, הוא

$O(1)+h=O(1)+\min _{k}\{n_{k}(x)+1\}=O(1)+\left\lceil \log _{|\Sigma |}\left({\frac {1}{P_{U}(x)}}\right)\right\rceil \leq \log _{|\Sigma |}\left({\frac {1}{P_{U}(x)}}\right)+O(1).$

כנדרש.

סכמת הפענוח פשוטה מאד: בהנתן סכמת בניית עץ השיוך, ותיאור המסלול, מריצים את בניית עץ השיוך עד שהצומת המתאים משוייך לתוכנית $M$. מריצים את $M$ עד לקבלת $x$.

התכנות בניית עץ השיוך

בבניית עץ השיוך הנחנו שאם אנו בונים את העץ לפי הכללים, אז בכל פעם שמסתיימת תוכנית $M_{k}$, אם $n_{k}$ התעדכן כלפי מטה, אז יש צומת פנוי ברמה $n_{k}+1$. מדוע זה נכון?

ראשית נוכיח את המשפט הבא:

משפט: עבור מחרוזת $x$, נניח ש-$J(x)$ היא קבוצת האינדקסים בהם $n_{j}(x)$ התעדכן כלפי מטה. אז $\forall _{x}\sum _{j\;|\;j\in J(x)}|\Sigma |^{-(n_{j}(x)+1)}\leq P_{U}(x)$

הוכחה: עפ"י ההגדרה,

$min_{j\in J}|\Sigma |^{-(n_{j}(x)+1)}\leq |\Sigma |^{\left\lfloor \log _{|\Sigma |}(P_{U}(x)\right\rfloor -1)}$

היות שאף תוכנית איננה מופיעה פעמיים באותה רמה בעץ, אז כל ה-$n_{j}$ נפרדים. לכן נקבל:

$\forall _{x}\sum _{j\;|\;j\in J(x)}|\Sigma |^{-(n_{j}(x)+1)}\leq \sum _{j=0,1,2,\ldots }|\Sigma |^{\left\lfloor \log _{|\Sigma |}(P_{U}(x)\right\rfloor -j-1}$

נפשט את הטור האינסופי:

$\sum _{j=0,1,2,\ldots }|\Sigma |^{\left\lfloor \log _{|\Sigma |}(P_{U}(x)\right\rfloor -j-1}=|\Sigma |^{\left\lfloor \log _{|\Sigma |}(P_{U}(x)\right\rfloor -1}\sum _{j=0,1,2,\ldots }|\Sigma |^{-j}={\frac {|\Sigma |^{\left\lfloor \log _{|\Sigma |}(P_{U}(x)\right\rfloor }}{|\Sigma |-1}}\leq P_{U}(x).$

נשים לב ש-$\sum _{x\in \Sigma ^{*}}P_{U}(x)\leq 1$. אם נחבר זאת למשפט הקודם, נקבל את המשפט הבא.

משפט: עבור מחרוזת $x$, נניח ש-$J(x)$ היא קבוצת האינדקסים בהם $n_{j}(x)$ התעדכן כלפי מטה. אז $\sum _{x\in \Sigma ^{*}}\sum _{j\;|\;j\in J(x)}|\Sigma |^{-(n_{j}(x)+1)}\leq 1$

המשפט האחרון מראה כי ערכי ה-$n_{k}$ אשר משוייכים לצמתים, ממלאים את אי-שוויון קראפט. אפשר לראות שאלגוריתם השיוך המקוון החמדני שכאן אכן מצליח לשייך במקרה זה.

תער אוקאם

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

לפלס חשב על הבעיה הבאה: נניח שכל מה שידוע לנו על השמש היא שהיא זרחה מדי יום במהלך אלפי השנים האחרונות. מדוע, למעשה, אנו חושבים שהיא תזרח גם מחר?

הסברו המקורי התבסס על חוק בייס. נניח שהשמש זורחת מדי יום בהתפלגות ברנולי עם פרמטר ברנולי לא ידוע $\phi$ המתפלג יוניפורמית בין 0 ל1, ונניח שכל מה שידוע הוא שהשמש זרחה בכ"א מ-$n$ הימים האחרונים. כלומר, נניח שזריחת השמש ביום $i$ הוא משתנה ברנולי בלתי תלוי $X_{i}\sim b(\phi )$. לפי חוק בייס,

$P(X_{n+1}=1|(X_{1},\ldots ,X_{n})=(1,\ldots 1))={\frac {P((X_{1},\ldots ,X_{n},X_{n+1})=(1,\ldots 1,1))}{P((X_{1},\ldots ,X_{n})=(1,\ldots 1,1))}}={\frac {\int _{0}^{1}\phi ^{n+1}d\phi }{\int _{0}^{1}\phi ^{n}d\phi }}={\frac {n+1}{n+2}}$

לפיכך, ההסתברות שהשמש לא תזרח מחר היא בקירוב ${\frac {1}{n}}$. במילים אחרות, ההסתברות שהשמש לא תזרח מחר דועכת לינארית.

נראה מדוע תוצאה דומה נובעת מסיבוכיות קולמוגורוב והסתברות אוניברסאלית של מחרוזות. נתבונן במחרוזת $1^{n}0y$ שהיא המחרוזת המתאימה לכך שהשמש זורחת (כלומר, יש ערך 1) במשך $n$ פעמים, לאחריה לא זורחת (הערך 0), ולאחריה זורחת או לא (מחרוזת $y$ כלשהו). שוב, לפי חוק בייס,

$P_{U}(1^{n}0y|1^{n})={\frac {\sum _{y}P_{U}(1^{n}0y)}{\sum _{y}P_{U}(1^{n}0y)+\sum _{y}P_{U}(1^{n}1y)}}.$

לפי מה שראינו בחלק הקודם, נוכל לשערך כל הסתברות אוניברסאלית בהסתברות קולמוגורוב:

$P_{U}(1^{n}0y|1^{n})\simeq P_{K}(1^{n}0y|1^{n})={\frac {\sum _{y}P_{K}(1^{n}0y)}{\sum _{y}P_{K}(1^{n}0y)+\sum _{y}P_{K}(1^{n}1y)}}.$

נשערך ביטויים אלה. ראשית, נשים לב שעבור קבוע $c_{1}>0$ כלשהו,

$\sum _{y}P_{K}(1^{n}y)\simeq P_{K}(1^{\infty })=c_{1},$

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

$\sum _{y}P_{K}(1^{n}1y)\simeq c_{1}.$

באופן דומה, סביר להניח שהתוכנית הקצרה ביותר המדפיסה $n$ אחדות ולאחריהן אפס, אומרת "הדפס $n$ אחדות ולאחריהן אינסוף אפסים". אורך תוכנית זו נקבע כנראה בעיקר ע"י תיאור $n$, ולכן הוא בערך

$\log _{\left|\Sigma \right|}(n)+c_{2},$

שממנו נובע

$\sum _{y}P_{K}(1^{n}0y)\simeq P_{K}(1^{n}0y)\simeq \left|\Sigma \right|^{-(\log _{\left|\Sigma \right|}(n)+c_{2})}=c_{3}n,$

עבור

$c_{3}=\left|\Sigma \right|^{-c_{2}}>0.$

נציב זאת בנוסחת בייס מקודם, ונקבל

$P_{K}(1^{n}0y|1^{n})={\frac {\sum _{y}P_{K}(1^{n}0y)}{\sum _{y}P_{K}(1^{n}0y)+\sum _{y}P_{K}(1^{n}1y)}}\simeq {\frac {c_{1}}{c_{1}+c_{3}n}}={\frac {1}{1+{\frac {c_{3}}{c_{1}}}n}}.$

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

הפרק הקודם: יישומי אי-דחיסות

הסתברות אוניברסאלית

הפרק הבא: בעיות זיהוי ובעיות חיפוש