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

{{תורת החישוביות}}

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

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

==הגדרות==

ה'''הסתברות האוניברסאלית''' של מחרוזת <math>x</math> היא הסיכוי שהיא תווצר ע"י תוכנית שבעצמה מיוצרת ע"י תהליך אקראי. נניח שאנו מייצרים מחרוזות ע"י תהליך בו כל תו מוגרל ב[[w:התפלגות אחידה|התפלגות אחידה]] עפנ"י <math>\Sigma</math>. חלק מהמחרוזות הנוצרות יהיו תיאורים חוקיים של תוכנית. חלק מתוכנית אלה אכן ייצרו את <math>x</math> בהנתן המחרוזת הריקה. ההסתברות האוניברסאלית של המחרוזת נקבעת עפ"י זאת.

{{הגדרה|שם=הסתברות אוניברסאלית של מחרוזת|תוכן=
ה'''הסתברות האוניברסאלית''' של מחרוזת <math>x</math> היא
<center><math>
P_u(x) = \sum_{M \;|\; M(\epsilon) = x} \left| \Sigma \right|^{- \left| \langle M \rangle \right|}.
</math></center>
}}

נגדיר גם את '''הסתברות הקולמוגורוב''' של מחרוזת ע"י ביטוי אלגברי דומה (שלו קשה יותר למצוא מוטיווציה):
{{הגדרה|שם=הסתברות אוניברסאלית של מחרוזת|תוכן=
'''הסתברות הקולמוגורוב''' של מחרוזת <math>x</math> היא
<center><math>
P_K(x) = \left| \Sigma \right|^{- K(x)}.
</math></center>
}}

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

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

{{משפט|שם=שקילות הסתברות אוניברסאלית והסתברות קולמוגורוב|תוכן=
קיים קבוע
<math>c > 0</math> 
עבורו
<center><math>\forall_x P_K(x)  \leq P_u(x) \leq  c P_K(x)</math></center>,
ובאופן שקול, קיים קבוע <math>c' > 0</math> שעבורו
<center><math>\forall_x K(x) - c' \leq \log\left( \frac{1}{P_u(x)} \right) \leq K(x)).</math></center>
}}


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

{{שקול לדלג|סיבה=שאר ההוכחה מורכבת למדי, ואפשר לוותר עליה.}}

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

כוון זה קל להוכיח. הדבר נובע למעשה מההגדרה. נניח ש-<math>M_x^K</math> היא התוכנית הקצרה ביותר המייצרת את <math>x</math>. אז
<center><math>
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).
</math></center>

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

כדי להראות כוון זה, נשתמש בניסוח (המתמטי) השני של המשפט, דהיינו נראה כי קיים קבוע <math>c' > 0</math> שעבורו
<center><math>\forall_x K(x) - c' \leq \log\left( \frac{1}{P_u(x)} \right).</math></center>

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

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

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

[[File:KlomogorovTree 0.png|left|thumb|בניית העץ 0 - עץ קידוד התחלתי]]

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

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

במהלך הרצת הdovetailing, מדי פעם, תעצור תוכנית כלשהי עם פלט כלשהו. נסמן את התוכנית ה-<math>k</math> שעוצרת  כ-<math>M_k</math> ואת המחרוזת שהיא מייצרת כ-<math>x_k</math>. בנוסף, נגדיר את שערוכנו להסתברות האוניברסלית של <math>x_k</math> עד כה:
<center><math>
P_U^k(x) = \sum_{i = 1, \ldots k \;|\; x_i = x_k} |\Sigma|^{-|\langle M_k \rangle|}.
</math></center>
קל לראות כי הביטוי שואף מלמטה להסתברות האוניברסאלית:
# <math>\forall_k P_U^k(x) \leq P_U(x)</math>
# <math>\lim_k P_U^k(x) = P_U(x)</math>
נסמן את שיערוכנו גם ללוגריתם ביטוי זה:
<center><math> 
n_k = 
\left\lceil 
\log_{|\Sigma|} \left( \frac{1}{P_U^k(x)} \right)
\right\rceil
</math></center>
נשים לב שבגלל העיגול כלפי מעלה, ביטוי זה שואף מלמעלה למספר שלם חיובי כלשהו אליו הוא מגיע לאחר מספר סופי של צעדים.

כשעוצרת תוכנית <math>M_k</math>, נחליט האם לשייכה לעץ בעזרת רשימה של שלשות שנחזיק בצד המתארות את התוכניות שעצרו כבר. השלשה המתאימה לתוכנית ה-<math>j</math> שעצרה, מורכבת מ:
# המחרוזת, <math>x_j</math>
# אורך תיאור התוכנית, <math>l_j = l_j(x) = |\langle M_j \rangle|</math>
# הצומת שאליו <math>M</math> משוייכת, אם בכלל. את הצומת בעץ אפשר לתאר בעזרת מחרוזת של המסלול (לדוגמה, המחרוזת "01" מציינת הליכה שמאלה פעם אחת, ולאחריה הליכה למטה פעם אחת; המחרוזת "222" מציינת הליכה ימינה שלוש פעמים). לא כל תוכנית שהסתיימה משוייכת לצומת. נניח שיש סימון מיוחד, נניח "-", המציין שאין שיוך.
נחליט את שיוך <math>M_k</math> לצומת כך: 
[[File:KolmogorovTree 1.png|left|thumb|בניית העץ 1 - שיוך צומת ראשון לתכנית בעלת אורך תיאור 1]]
#נחפש ברשימה את האינדקסים בהם הופיעה המחרוזת בעבר: <math>J_k = \left\{j : x_j = x_k \right\}</math> (אם עדיין לא סיימה תוכנית המייצרת את <math>x_k</math>, זו סדרה ריקה).
#נבנה את סדרת ההערכות ללוגריתם: <math>n_j = n_j(x) \;|\; j \in J_k</math>, ונחליט לשייך את התוכנית לצומת כלשהו רק אם <math>n_k</math> נמוך יותר מהערכים הקודמים (היות שמעגלים את הלוגריתם כלפי מעלה, לא בכל פעם בהכרח זה יקרה).
#אם החלטנו לשייך, נמצא את הצומת הפנוי הראשון (משמאל לימין) ברמה <math>n_k + 1</math>, ונשייך את <math>M</math> אליו (ב[[#התכנות בניית עץ השיוך|התכנות בניית עץ השיוך]] נוכיח שבהכרח תמיד יהיה צומת פנוי). הצומת הופך להיות משוייך. נמחק את כל הצאצאים של הצומת מהעץ, וכל צומת במסלול מהצומת לראש העץ (כולל ראש העץ) הופך להיות תפוס.

לדוגמה (בתרשים "בניית העץ 1" המצוייר בצד שמאל), נניח שהתוכנית הראשונה שהסתיימה היא התוכנית שתיאורה הוא "1", והפלט שלה הוא "000111000". בשלב זה,
<center><math>
|\Sigma|^{-|\langle M_1 \rangle |} = 3^{-1} = \frac{1}{3}
</math></center>
ולכן
<center><math>
n_1(x_1) = 
\left\lceil 
\log_{3} \left( \frac{1}{\frac{1}{3}} \right)
\right\rceil
=
1
</math></center>

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



נניח שהתוכנית השניה שהסתיימה היא התוכנית שתיאורה הוא באורך מיליארד, והפלט שלה הוא שוב "000111000". בשלב זה,
<center><math>
P_U^2(x_2) = P_U^2(x_1) = |\Sigma|^{-|\langle M_2 \rangle |} = 3^{-1,000,000,000}
</math></center>
ולכן
<center><math>
n_2(x_2) = 
\left\lceil 
\log_{3} \left( \frac{1}{\frac{1}{3} + 3^{-1,000,000,000}} \right)
\right\rceil
= 1
</math></center>

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


[[File:KolmogorovTree 2.png|left|thumb|בניית העץ 2 - שיוך צומת שני לתכנית בעלת אורך תיאור 0]]

נמשיך כך הלאה. לדוגמה (בתרשים "בניית העץ 2" המצוייר בצד שמאל), נניח שהתוכנית השלישית שהסתיימה היא התוכנית שתיאורה הוא "" (המחרוזת הריקה), והפלט שלה הוא "011". בשלב זה,
<center><math>
P_U^3(x_3)  = |\Sigma|^{-|\langle M_3 \rangle |} = 3^{-0} = 1
</math></center>
ולכן
<center><math>
n_3(x_3) = 
\left\lceil 
\log_{3} \left( \frac{1}{1} \right)
\right\rceil
= 
0
</math></center>
עלינו לשייך את התוכנית לצומת ברמה <math>0 + 1 = 1</math>. היות שהצומת השמאלי ביותר ברמה זו תפוס, נשייך אותו לצומת השני משמאל ברמה 1.

[[File:KolmogorovTree 3.png|left|thumb|בניית העץ 3 - שיוך עוד מספר צמתים]]

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

====קידוד ופענוח====

עבור מחרוזת <math>x</math> כלשהי, נניח ש-<math>M_1, M_2, \ldots</math> הן התוכניות שיסתיימו ויפלטו את <math>x</math>. נניח ש-<math>h</math> הוא הגובה הנמוך ביותר אליו יוחלט לשייך אחת מתוכניות אלו בעץ החיפוש (כלומר, מסתיימת תוכנית בעלת אורך <math>h - 1</math> המייצרת את <math>x</math>, ומשייכים תוכנית זו לצומת פנוי ברמה <math>h</math>). נשים לב לשתי נקודות:
# <math>h</math> מוגדרת היטב.
# <math>h</math> איננה נתנת לחישוב (ראינו כבר ש[[תורת החישוביות/סיבוכיות קולמוגורוב#אי-חישוביות פונקציית הסיבוכיות|פונקציית הסיבוכיות איננה נתנת לחישוב]]).


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

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

אורך הקידוד, לכן, הוא
<center><math>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).</math></center>
כנדרש.


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

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

ב[[#בניית עץ השיוך|בניית עץ השיוך]] הנחנו שאם אנו בונים את העץ לפי הכללים, אז בכל פעם שמסתיימת תוכנית <math>M_k</math>, אם <math>n_k</math> התעדכן כלפי מטה, אז יש צומת פנוי ברמה <math>n_k + 1</math>. מדוע זה נכון?

ראשית נוכיח את המשפט הבא:
{{משפט|תוכן=
עבור מחרוזת <math>x</math>, נניח ש-<math>J(x)</math> היא קבוצת האינדקסים בהם <math>n_j(x)</math> התעדכן כלפי מטה. אז

<center><math> \forall_x \sum_{j \;|\; j \in J(x)}|\Sigma|^{-(n_j(x) + 1)} \leq P_U(x) </math></center>

}}

{{הוכחה|1=
עפ"י ההגדרה, 
<center><math>
min_{j \in J} |\Sigma|^{-(n_j(x) + 1)} \leq |\Sigma|^{\left\lfloor \log_{|\Sigma|}(P_U(x) \right\rfloor - 1)}
</math></center>
היות שאף תוכנית איננה מופיעה פעמיים באותה רמה בעץ, אז כל ה-<math>n_j</math> נפרדים. לכן נקבל:
<center><math> 
	\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}</math></center>
נפשט את הטור האינסופי:
<center><math> 
	\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)
	.
</math></center>
}}

נשים לב ש-<math>\sum_{x \in \Sigma^*} P_U(x) \leq 1</math>. אם נחבר זאת למשפט הקודם, נקבל את המשפט הבא.
{{משפט|תוכן=
עבור מחרוזת <math>x</math>, נניח ש-<math>J(x)</math> היא קבוצת האינדקסים בהם <math>n_j(x)</math> התעדכן כלפי מטה. אז

<center><math> \sum_{x \in \Sigma^*} \sum_{j \;|\; j \in J(x)}|\Sigma|^{-(n_j(x) + 1)} \leq 1 </math></center>

}}

המשפט האחרון מראה כי ערכי ה-<math>n_k</math> אשר משוייכים לצמתים, ממלאים את [[w:אי-שוויון קראפט|אי-שוויון קראפט]]. אפשר לראות שאלגוריתם השיוך המקוון החמדני שכאן אכן מצליח לשייך במקרה זה.

==תער אוקאם==

עקרון [[#תער אוקאם|תער אוקאם]], לפחות באחת ממשמעויותיו המקובלת כיום, גורס כי בהנתן מספר הסברים שונים לתופעה, נעדיף את ההסבר הפשוט יותר. נראה את הקשר לסיבוכיות קולמוגורוב דרך [[w:en:sunrise problem|בעיית זריחת השמש של לפלס]]. 

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

הסברו המקורי התבסס על [[w:חוק בייס|חוק בייס]]. נניח שהשמש זורחת מדי יום ב[[w:התפלגות ברנולי|התפלגות ברנולי]]
עם פרמטר ברנולי לא ידוע
<math>\phi</math>
[[w:התפלגות יוניפורמית|המתפלג יוניפורמית]] בין
0 ל1, ונניח שכל מה שידוע הוא שהשמש זרחה בכ"א מ-<math>n</math> הימים האחרונים. כלומר, נניח שזריחת השמש ביום <math>i</math> הוא משתנה ברנולי בלתי תלוי
<math>X_i \sim b(\phi)</math>. לפי חוק בייס,
<center><math>
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
}
</math></center>
לפיכך, ההסתברות שהשמש לא תזרח מחר היא בקירוב
<math>\frac
{
	1}
{
	n
}
</math>.
במילים אחרות, ההסתברות שהשמש לא תזרח מחר דועכת לינארית.

נראה מדוע תוצאה דומה נובעת מסיבוכיות קולמוגורוב והסתברות אוניברסאלית של מחרוזות. נתבונן במחרוזת
<math>1^n0y</math>
שהיא המחרוזת המתאימה לכך שהשמש זורחת (כלומר, יש ערך 1) במשך <math>n</math> פעמים, לאחריה לא זורחת (הערך 0), ולאחריה זורחת או לא (מחרוזת <math>y</math> כלשהו). שוב, לפי חוק בייס, 
<center><math>P_U(1^n0y|1^n) = \frac{\sum_y P_U(1^n0y)}{\sum_y P_U(1^n0y) + \sum_y P_U(1^n1y)}.</math></center>
לפי מה שראינו בחלק הקודם, נוכל לשערך כל הסתברות אוניברסאלית בהסתברות קולמוגורוב:
<center><math>P_U(1^n0y|1^n) \simeq P_K(1^n0y|1^n) = \frac{\sum_y P_K(1^n0y)}{\sum_y P_K(1^n0y) + \sum_y P_K(1^n1y)}.</math></center>

נשערך ביטויים אלה.
ראשית, נשים לב שעבור קבוע <math>c_1 > 0</math> כלשהו,
<center><math>\sum_y P_K(1^ny) \simeq P_K(1^{\infty}) = c_1,</math></center>
מפני שסביר שהתוכנית שפשוט מדפיסה אחדות בלי הגבלה היא בעלת אורך תיאור קצר ביותר. כמובן שמאותה סיבה גם נקבל
<center><math>\sum_y P_K(1^n1y) \simeq c_1.</math></center>
באופן דומה, סביר להניח שהתוכנית הקצרה ביותר המדפיסה <math>n</math> אחדות ולאחריהן אפס, אומרת "הדפס <math>n</math> אחדות ולאחריהן אינסוף אפסים". אורך תוכנית זו נקבע כנראה בעיקר ע"י תיאור <math>n</math>, ולכן הוא בערך
<center><math>\log_{\left| \Sigma \right|}(n) + c_2,</math></center>
שממנו נובע
<center><math>\sum_y P_K(1^n0y) \simeq P_K(1^n0y) \simeq \left| \Sigma \right|^{-( \log_{\left| \Sigma \right|}(n) + c_2)} = c_3 n,</math></center>
עבור 
<center><math>c_3 = \left| \Sigma \right|^{-c_2} > 0.</math></center>
נציב זאת בנוסחת בייס מקודם, ונקבל
<center><math>P_K(1^n0y|1^n) = \frac{\sum_y P_K(1^n0y)}{\sum_y P_K(1^n0y) + \sum_y P_K(1^n1y)} \simeq \frac{c_1}{c_1 + c_3 n} = \frac{1}{1 + 
\frac{c_3}{c_1}n}.</math></center>

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

[[קטגוריה:תורת החישוביות]]

{{תורת החישוביות|מוגבל}}