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