תורת החישוביות/סיבוכיות קולמוגורוב/הסתברות אוניברסאלית: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
שורה 54:
</math></center>
===סיבוכיות קולמוגורוב היא לכל
כדי להראות כוון זה, נשתמש בניסוח (המתמטי) השני של המשפט, דהיינו נראה כי קיים קבוע <math>c' > 0</math> שעבורו
<center><math>\forall_x K(x) - c' \leq \log\left( \frac{1}{P_u(x)} \right).</math></center>
מטרתנו להראות כי לכל מחרוזת יש תיאור שאינו ארוך יותר (עד כדי קבוע) מהביטוי הכולל את הסיבוכיות האוניברסאלית. נשים לב כי לצורך כך, עלינו רק להראות שקיים תיאור כזה, ולא להצביע על פונקציה נתנת לחישוב הבונה אותו. מצד שני, לפי הגדרת "תיאור", חייבת להיות תוכנית נתנת לחישוב אשר בהנתן התיאור, משחזרת את המחרוזת.
נעשה זאת ע"י הרעיון של '''עץ שיוך''' המשייך חלק מהתוכניות העוצרות עם פלט כלשהו לצמתים בעץ. ב[[#בניית עץ השיוך|בניית עץ השיוך]] נתאר את התהליך (האינסופי) הבונה עץ זה. ב[[#קידוד ופענוח|קידוד ופענוח]] נראה שאפשר להשתמש בתהליך זה כדי להראות שקיים תיאור קצר למחרוזת המאפשר לשחזר אותו. ב[[#התכנות בניית עץ השיוך|התכנות בניית עץ השיוך]] נראה נקודה טכנית יחסית לגבי יכולת המשכת התהליך הבונה את עץ השיוך.
{{להשלים}}
שורה 80 ⟵ 86:
כלשהו. במצב כזה, ננסה לשייך את התוכנית לצומת בעץ. נמצא את הצומת הפנוי הראשון (משמאל לימין) ברמה
<math>| \langle M \rangle | + 1</math>,
ונשייך את <math>M</math> אליו (
[[File:KolmogorovTree 1.png|left|thumb|בניית העץ 1 - שיוך צומת ראשון לתכנית בעלת אורך תיאור 1]]
שורה 106 ⟵ 112:
נמשיך כך הלאה והלאה. לפי הdovetailing, כל תוכנית שתסתיים בסופו של דבר תישקל ואולי תשוייך לצומת. כל מחרוזת המיוצרת ע"י תוכנית כלשהי, תשוייך לצומת כלשהו בעץ. נקבל עץ אינסופי, שרק לעליו יש שיוך (לדוגמה, בתרשים "בניית העץ 3" בצד שמאל).
====התכנות בניית עץ השיוך====▼
נניח שבצעד <math>n</math> מסתיימת תוכנית <math>M</math> ואין מקום פנוי ברמה▼
<math>|\langle M \rangle|</math>.▼
<math>x</math>▼
<math>▼
\sum_{x \;|\; \exists} | \Sigma |^{- |\langle M(x) \rangle|} \geq 1▼
</math>▼
====קידוד ופענוח====
שורה 131 ⟵ 126:
<center><math>h + O(1) = K(x) + 1 + O(1) = K(x) + O(1).</math></center>
נשים לב כי,
<center><math>
K(x)
שורה 137 ⟵ 133:
\left(
\frac{1}{\left| \Sigma \right|^{-K(x)}}
\right)
\leq
\log_{\left| \Sigma \right|}
\left(
\frac{1}{\sum_{M \;|\; M(\epsilon) = x} \left| \Sigma \right|^{- \left| \langle M \rangle \right|} }
\right)
=
\log_{\left| \Sigma \right|}
\left(
\frac{1}{ P_U(x) }
\right)
</math></center>
סכמת הפענוח פשוטה מאד: בהנתן סכמת בניית עץ השיוך, ותיאור המסלול, מריצים את בניית עץ השיוך עד שהצומת המתאים משוייך למכונה <math>M</math>. מריצים את <math>M</math> עד לקבלת <math>x</math>.
<br />
▲====התכנות בניית עץ השיוך====
▲נניח שבצעד <math>n</math> מסתיימת תוכנית <math>M</math> ואין מקום פנוי ברמה
▲<math>|\langle M \rangle|</math>.
▲<math>x</math>
▲<math>
▲ \sum_{x \;|\; \exists} | \Sigma |^{- |\langle M(x) \rangle|} \geq 1
▲</math>
\right)
\leq
| |||