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

תוכן שנמחק תוכן שנוסף
Atavory (שיחה | תרומות)
Atavory (שיחה | תרומות)
שורה 117:
עבור מחרוזת <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>h</math>. במקרה זה, נוכל לחזור על תהליך בניית העץ, ונעצור ברגע שמשוייכת תוכנית המייצרת את <math>x</math> לצומת בגובה <math>h</math>.
שורה 137 ⟵ 138:
\log_{\left| \Sigma \right|}
\left(
\frac{1}{\sum_{Mi \;|\; MM_i(\epsilon) = x} \left| \Sigma \right|^{- \left| \langle MM_i \rangle \right|} }
\right)
=
שורה 144 ⟵ 145:
\frac{1}{ P_U(x) }
\right)
,
</math></center>
ולכן
<center><math>
K(x)
 
\leq
\log_{\left| \Sigma \right|}
\left(
\frac{1}{ P_U(x) }
\right)
+
O(1)
</math></center>
כנדרש.
 
 
סכמת הפענוח פשוטה מאד: בהנתן סכמת בניית עץ השיוך, ותיאור המסלול, מריצים את בניית עץ השיוך עד שהצומת המתאים משוייך למכונהלתוכנית <math>M</math>. מריצים את <math>M</math> עד לקבלת <math>x</math>.
<br />