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

<math>| \langle M \rangle | + 1</math>,

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

 

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

הופך להיות משוייך, והצמתים השמאליים ביותר ברמות 0 ו1 הופכים להיות תפוסים.

 

כעת נוסיף עוד כלל. אם הסתיימה ריצת תוכנית <math>M</math> המייצרת <math>x</math>, בעבר הסתיימה ריצת תוכנית <math>M'</math> שגם ייצרה <math>x</math>, ו-<math>|\langle M \rangle | = |\langle M' \rangle |</math>, אז לא משייכים את <math>M</math> לאף צומת. כך יוצא שלכל מחרוזת <math>x</math>, יש לכל היותר תוכנית אחת משוייכת בכל רמה בעץ.

 

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

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

 

</span>

הוא תפוס. לכן נשייך את התוכנית לצומת השני משמאל ברמה 1.

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

 

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