תורת החישוביות/סיבוכיות קולמוגורוב/הסתברות אוניברסאלית: הבדלים בין גרסאות בדף

}}

 

 

נניח ש-<math>M_K(x)</math> היא התוכנית הקצרה ביותר המייצרת את <math>x</math>. אז

 

<center><math>

P_K(x) = \left| \Sigma \right|^{- K(x)} = \left| \Sigma \right|^{- \left| \langle M_K(x) \right|} \leq

P_u(x).

</math></center>

 

{{להשלים}}

 

 

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

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

 

 

 

</math>

 

 

עבור מחרוזת <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>M</math>. מריצים את <math>M</math> עד לקבלת <math>x</math>.

 

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