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

תוכן שנמחק תוכן שנוסף
Atavory (שיחה | תרומות)
Atavory (שיחה | תרומות)
שורה 89:
\right\rceil
</math></center>
נשים לב שבגלל העיגול כלפי מעלה, ביטוי זה שואף מלמעלה למספר שלם חיובי כלשהו אליו הוא מגיע לאחר מספר סופי של צעדים.
 
במהלך הבניה מחזיקים רשימה של זוגותשלשות. כל זוגשלשה תוכנית שכבר הסתיימה (עם פלט כלשהו), ומורכבמורכבת מ:
# תיאור התוכנית, <math>\langle MM_k \rangle</math>
# המחרוזת, <math>x_k</math>
# שערוכנו ללוגריתם ההסתברות האוניברסאלית של <math>x_k</math>, כלומר <math>n_k</math>
# הצומת שאליו <math>M</math> משוייכת, אם בכלל. את הצומת בעץ אפשר לתאר בעזרת מחרוזת של המסלול (לדוגמה, המחרוזת "01" מציינת הליכה שמאלה פעם אחת, ולאחריה הליכה למטה פעם אחת; המחרוזת "222" מציינת הליכה ימינה שלוש פעמים). לא כל תוכנית שהסתיימה משוייכת לצומת. נניח שיש סימון מיוחד, נניח "-", המציין שאין שיוך.