תורת החישוביות/סיבוכיות קולמוגורוב/הסתברות אוניברסאלית: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
שורה 74:
התהליך משתמש ב[[w:en:dovetailing|dovetailing]], תהליך ה"הרצה במקביל" שראינו כבר במהלך הספר (לדוגמה, ב[[תורת החישוביות/מודל לבעיות הכרעה#שקילות למודל הכללי|הוכחת השקילות בין המודל הכללי למודל ההכרעה]]). מסדרים את כל התוכניות בסדר לקסיקורפי. מריצים את התוכנית הראשונה צעד אחד, לאחר מכן כ"א מ2 התוכניות הראשונות 2 צעדים, לאחר מכן כ"א מ3 התוכניות הראשונות 3 צעדים, וכו' וכו'.
במהלך הרצת הdovetailing, מדי פעם, תעצור תוכנית כלשהי עם פלט כלשהו. נסמן, בפעם ה-<math>k</math> שתוכנית עוצרת, את התוכנית כ-<math>M_k</math> ואת המחרוזת שהיא מייצרת כ-<math>x_k</math>. נגדיר את שערוכנו להסתברות האוניברסלית של <math>x_k</math> עד כה:
<center><math>
P_U^k(x) = \sum_{i = 1, \ldots k \;|\; x_i = x_k} |\Sigma|^{-|\langle M_k \rangle|}.
</math></center>
קל לראות כי הביטוי שואף מלמטה להסתברות האוניברסאלית:
# <math>\forall_k P_U^k(x) \leq P_U(x)</math>
# <math>\lim_k P_U^k(x) = P_U(x)</math>
נסמן את שיערוכנו גם ללוגריתם ביטוי זה:
<center><math>
n_k =
\left\lceil
\log_{|\Sigma|} \left( \frac{1}{P_U^k(x)} \right)
\right\rceil
</math></center>
במהלך הבניה מחזיקים רשימה של זוגות. כל זוג תוכנית שכבר הסתיימה (עם פלט כלשהו), ומורכב מ:
| |||