תורת החישוביות/סיבוכיות קולמוגורוב/הסתברות אוניברסאלית: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
←התכנות בניית עץ השיוך: הרחבה |
←בניית עץ השיוך: עריכה, הגהה |
||
שורה 107:
ולכן
<center><math>
\left\lceil
\log_{3} \left( \frac{1}{\frac{1}{3}} \right)
\right\rceil
=
1
</math></center>
לכן עלינו לבחור צומת ברמה <math>1 + 1 = 2</math>. היותר שבשלב זה כל הצמתים בעץ פנויים, הצומת השמאלי ביותר ברמה 2
הופך להיות משוייך, והצמתים השמאליים ביותר ברמות 0 ו1 הופכים להיות תפוסים.
נניח שהתוכנית
<center><math>
P_U^
</math></center>
ולכן
<center><math>
\left\lceil
\log_{3} \left( \frac{1}{\frac{1}{3} + 3^{-1,000,000,000}} \right)
\right\rceil
</math></center>
שורה 141 ⟵ 140:
נמשיך כך הלאה. לדוגמה (בתרשים "בניית העץ 2" המצוייר בצד שמאל), נניח שהתוכנית השלישית שהסתיימה היא התוכנית שתיאורה הוא "" (המחרוזת הריקה), והפלט שלה הוא "011". בשלב זה,
<center><math>
P_U^3(x) = |\Sigma|^{-|\langle M_3 \rangle |} = 3^{-0} = 1
</math></center>
ולכן
שורה 149 ⟵ 148:
\log_{3} \left( \frac{1}{1} \right)
\right\rceil
=
0
</math></center>
עלינו לשייך את התוכנית לצומת ברמה <math>0 + 1 = 1</math>. היות שהצומת השמאלי ביותר ברמה זו תפוס, נשייך אותו לצומת השני משמאל ברמה
[[File:KolmogorovTree 3.png|left|thumb|בניית העץ 3 - שיוך עוד מספר צמתים]]
|