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