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

תוכן שנמחק תוכן שנוסף
Atavory (שיחה | תרומות)
Atavory (שיחה | תרומות)
שורה 195:
עפ"י ההגדרה,
<center><math>
min_{j \in J} |\Sigma|^{-(n_j(x) + 1)} =\leq |\Sigma|^{-\left\lfloor \log_{|\Sigma|}(P_U(x) +\right\rfloor - 1)}
</math></center>
היות שאף תוכנית איננה מופיעה פעמיים באותה רמה בעץ, אז כל ה-<math>n_j</math> נפרדים. לכן נקבל:
שורה 201:
\forall_x \sum_{j \;|\; j \in J(x)}|\Sigma|^{-(n_j(x) + 1)}
\leq
\sum_{j = 0, 1, 2, \ldots}|\Sigma|^{-\left\lfloor \log_{|\Sigma|}(P_U(x) +\right\rfloor - j +- 1)}</math></center>
נפשט את הטור האינסופי:
<center><math>
\sum_{j = 0, 1, 2, \ldots}|\Sigma|^{-\left\lfloor \log_{|\Sigma|}(P_U(x) +\right\rfloor - j +- 1)}
=
|\Sigma|^{-\left\lfloor \log_{|\Sigma|}(P_U(x) +\right\rfloor - 1)} \sum_{j = 0, 1, 2, \ldots}|\Sigma|^{-j}
=
\frac{|\Sigma|1}{|\Sigma| - 1} |\Sigma|^{-\left\lfloor \log_{|\Sigma|}(P_U(x) +\right\rfloor 1)}
\leq
|\Sigma|^{-P_U(x)}
.
</math></center>