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

תוכן שנמחק תוכן שנוסף
Atavory (שיחה | תרומות)
Atavory (שיחה | תרומות)
שורה 75:
התהליך משתמש ב[[w:en:dovetailing|dovetailing]], תהליך ה"הרצה במקביל" שראינו כבר במהלך הספר (לדוגמה, ב[[תורת החישוביות/מודל לבעיות הכרעה#שקילות למודל הכללי|הוכחת השקילות בין המודל הכללי למודל ההכרעה]]). מסדרים את כל התוכניות בסדר לקסיקורפי. מריצים את התוכנית הראשונה צעד אחד, לאחר מכן כ"א מ2 התוכניות הראשונות 2 צעדים, לאחר מכן כ"א מ3 התוכניות הראשונות 3 צעדים, וכו' וכו'.
 
במהלך הבניה מחזיקים רשימה של שלשותזוגות. כל שלשה מציינתזוג תוכנית שכבר הסתיימה (עם פלט כלשהו). השלשה, מורכבתומורכב מ:
# תיאור התוכנית, <math>\langle M \rangle</math>
# הפלט שאותו היא פלטה, <math>x</math>
# הצומת שאליו <math>M</math> משוייכת, אם בכלל. את הצומת בעץ אפשר לתאר בעזרת מחרוזת של המסלול (לדוגמה, המחרוזת "01" מציינת הליכה שמאלה פעם אחת, ולאחריה הליכה למטה פעם אחת; המחרוזת "222" מציינת הליכה ימינה שלוש פעמים). לא כל תוכנית שהסתיימה משוייכת לצומת. נניח שיש סימון מיוחד, נניח "-", המציין שאין שיוך.
 
במהלך הרצת הdovetailing, מדי פעם, תעצור תוכנית <math>M</math>
כלשהי עם פלט <math>x</math>
כלשהו. במצב כזה, ננסה לשייךנשייך את התוכנית לצומת בעץ. נמצא את הצומת הפנוי הראשון (משמאל לימין) ברמה
<math>| \langle M \rangle | + 1</math>,
ונשייך את <math>M</math> אליו (ב[[#התכנות בניית עץ השיוך|התכנות בניית עץ השיוך]] נוכיח שבהכרח תמיד יהיה צומת פנוי). הצומת הופך להיות משוייך. נמחק את כל הצאצאים של הצומת מהעץ, וכל צומת במסלול מהצומת לראש העץ (כולל ראש העץ) הופך להיות תפוס.
שורה 88 ⟵ 87:
[[File:KolmogorovTree 1.png|left|thumb|בניית העץ 1 - שיוך צומת ראשון לתכנית בעלת אורך תיאור 1]]
 
לדוגמה (בתרשים "בניית העץ 1" המצוייר בצד שמאל), נניח שהתוכנית הראשונה שהסתיימה היא התוכנית שתיאורה הוא "1", והפלט(נניח שהפלט שלה הוא "000111000"). בשלב זה, כל הצמתים בעץ פנויים. הצומת השמאלי ביותר ברמה
<span dir = "ltr">
2 = |"1"| + 1
שורה 95 ⟵ 94:
 
 
כעת נוסיף עוד כלל. אם הסתיימה ריצת תוכנית <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]]
 
נמשיך כך הלאה. לדוגמה (בתרשים "בניית העץ 2" המצוייר בצד שמאל), נניח שהתוכנית השלישית שהסתיימה היא התוכנית שתיאורה הוא "" (המחרוזת הריקה), (והפלט שלה הוא "011"). בשלב זה, הצומת השמאלי ביותר ברמה
<span dir = "ltr">
1 = |""| + 1
שורה 109 ⟵ 105:
[[File:KolmogorovTree 3.png|left|thumb|בניית העץ 3 - שיוך עוד מספר צמתים]]
 
נמשיך כך הלאה והלאה. לפי הdovetailing, כל תוכנית שתסתיים בסופו של דבר תישקל ואולי תשוייךותשוייך לצומת. כל מחרוזת המיוצרת ע"י תוכנית כלשהי, תשוייך לצומת כלשהו בעץ. נקבל עץ אינסופי, שרק לעליו יש שיוך (לדוגמה, בתרשים "בניית העץ 3" בצד שמאל).
 
====קידוד ופענוח====